LCOV - code coverage report
Current view: top level - src/backend/optimizer/plan - initsplan.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 1042 1073 97.1 %
Date: 2025-04-01 23:17:00 Functions: 34 34 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * initsplan.c
       4             :  *    Target list, group by, qualification, joininfo initialization routines
       5             :  *
       6             :  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/optimizer/plan/initsplan.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : #include "postgres.h"
      16             : 
      17             : #include "catalog/pg_constraint.h"
      18             : #include "catalog/pg_type.h"
      19             : #include "nodes/makefuncs.h"
      20             : #include "nodes/nodeFuncs.h"
      21             : #include "optimizer/clauses.h"
      22             : #include "optimizer/cost.h"
      23             : #include "optimizer/inherit.h"
      24             : #include "optimizer/joininfo.h"
      25             : #include "optimizer/optimizer.h"
      26             : #include "optimizer/pathnode.h"
      27             : #include "optimizer/paths.h"
      28             : #include "optimizer/placeholder.h"
      29             : #include "optimizer/planmain.h"
      30             : #include "optimizer/planner.h"
      31             : #include "optimizer/restrictinfo.h"
      32             : #include "parser/analyze.h"
      33             : #include "rewrite/rewriteManip.h"
      34             : #include "utils/lsyscache.h"
      35             : #include "utils/rel.h"
      36             : #include "utils/typcache.h"
      37             : 
      38             : /* These parameters are set by GUC */
      39             : int         from_collapse_limit;
      40             : int         join_collapse_limit;
      41             : 
      42             : 
      43             : /*
      44             :  * deconstruct_jointree requires multiple passes over the join tree, because we
      45             :  * need to finish computing JoinDomains before we start distributing quals.
      46             :  * As long as we have to do that, other information such as the relevant
      47             :  * qualscopes might as well be computed in the first pass too.
      48             :  *
      49             :  * deconstruct_recurse recursively examines the join tree and builds a List
      50             :  * (in depth-first traversal order) of JoinTreeItem structs, which are then
      51             :  * processed iteratively by deconstruct_distribute.  If there are outer
      52             :  * joins, non-degenerate outer join clauses are processed in a third pass
      53             :  * deconstruct_distribute_oj_quals.
      54             :  *
      55             :  * The JoinTreeItem structs themselves can be freed at the end of
      56             :  * deconstruct_jointree, but do not modify or free their substructure,
      57             :  * as the relid sets may also be pointed to by RestrictInfo and
      58             :  * SpecialJoinInfo nodes.
      59             :  */
      60             : typedef struct JoinTreeItem
      61             : {
      62             :     /* Fields filled during deconstruct_recurse: */
      63             :     Node       *jtnode;         /* jointree node to examine */
      64             :     JoinDomain *jdomain;        /* join domain for its ON/WHERE clauses */
      65             :     struct JoinTreeItem *jti_parent;    /* JoinTreeItem for this node's
      66             :                                          * parent, or NULL if it's the top */
      67             :     Relids      qualscope;      /* base+OJ Relids syntactically included in
      68             :                                  * this jointree node */
      69             :     Relids      inner_join_rels;    /* base+OJ Relids syntactically included
      70             :                                      * in inner joins appearing at or below
      71             :                                      * this jointree node */
      72             :     Relids      left_rels;      /* if join node, Relids of the left side */
      73             :     Relids      right_rels;     /* if join node, Relids of the right side */
      74             :     Relids      nonnullable_rels;   /* if outer join, Relids of the
      75             :                                      * non-nullable side */
      76             :     /* Fields filled during deconstruct_distribute: */
      77             :     SpecialJoinInfo *sjinfo;    /* if outer join, its SpecialJoinInfo */
      78             :     List       *oj_joinclauses; /* outer join quals not yet distributed */
      79             :     List       *lateral_clauses;    /* quals postponed from children due to
      80             :                                      * lateral references */
      81             : } JoinTreeItem;
      82             : 
      83             : 
      84             : static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
      85             :                                        Index rtindex);
      86             : static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
      87             :                                  JoinDomain *parent_domain,
      88             :                                  JoinTreeItem *parent_jtitem,
      89             :                                  List **item_list);
      90             : static void deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem);
      91             : static void process_security_barrier_quals(PlannerInfo *root,
      92             :                                            int rti, JoinTreeItem *jtitem);
      93             : static void mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
      94             :                                      Relids lower_rels);
      95             : static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
      96             :                                            Relids left_rels, Relids right_rels,
      97             :                                            Relids inner_join_rels,
      98             :                                            JoinType jointype, Index ojrelid,
      99             :                                            List *clause);
     100             : static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo,
     101             :                                   List *clause);
     102             : static void deconstruct_distribute_oj_quals(PlannerInfo *root,
     103             :                                             List *jtitems,
     104             :                                             JoinTreeItem *jtitem);
     105             : static void distribute_quals_to_rels(PlannerInfo *root, List *clauses,
     106             :                                      JoinTreeItem *jtitem,
     107             :                                      SpecialJoinInfo *sjinfo,
     108             :                                      Index security_level,
     109             :                                      Relids qualscope,
     110             :                                      Relids ojscope,
     111             :                                      Relids outerjoin_nonnullable,
     112             :                                      Relids incompatible_relids,
     113             :                                      bool allow_equivalence,
     114             :                                      bool has_clone,
     115             :                                      bool is_clone,
     116             :                                      List **postponed_oj_qual_list);
     117             : static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
     118             :                                     JoinTreeItem *jtitem,
     119             :                                     SpecialJoinInfo *sjinfo,
     120             :                                     Index security_level,
     121             :                                     Relids qualscope,
     122             :                                     Relids ojscope,
     123             :                                     Relids outerjoin_nonnullable,
     124             :                                     Relids incompatible_relids,
     125             :                                     bool allow_equivalence,
     126             :                                     bool has_clone,
     127             :                                     bool is_clone,
     128             :                                     List **postponed_oj_qual_list);
     129             : static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
     130             : static Relids get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids);
     131             : static void check_mergejoinable(RestrictInfo *restrictinfo);
     132             : static void check_hashjoinable(RestrictInfo *restrictinfo);
     133             : static void check_memoizable(RestrictInfo *restrictinfo);
     134             : 
     135             : 
     136             : /*****************************************************************************
     137             :  *
     138             :  *   JOIN TREES
     139             :  *
     140             :  *****************************************************************************/
     141             : 
     142             : /*
     143             :  * add_base_rels_to_query
     144             :  *
     145             :  *    Scan the query's jointree and create baserel RelOptInfos for all
     146             :  *    the base relations (e.g., table, subquery, and function RTEs)
     147             :  *    appearing in the jointree.
     148             :  *
     149             :  * The initial invocation must pass root->parse->jointree as the value of
     150             :  * jtnode.  Internally, the function recurses through the jointree.
     151             :  *
     152             :  * At the end of this process, there should be one baserel RelOptInfo for
     153             :  * every non-join RTE that is used in the query.  Some of the baserels
     154             :  * may be appendrel parents, which will require additional "otherrel"
     155             :  * RelOptInfos for their member rels, but those are added later.
     156             :  */
     157             : void
     158      866946 : add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
     159             : {
     160      866946 :     if (jtnode == NULL)
     161           0 :         return;
     162      866946 :     if (IsA(jtnode, RangeTblRef))
     163             :     {
     164      453648 :         int         varno = ((RangeTblRef *) jtnode)->rtindex;
     165             : 
     166      453648 :         (void) build_simple_rel(root, varno, NULL);
     167             :     }
     168      413298 :     else if (IsA(jtnode, FromExpr))
     169             :     {
     170      323792 :         FromExpr   *f = (FromExpr *) jtnode;
     171             :         ListCell   *l;
     172             : 
     173      697054 :         foreach(l, f->fromlist)
     174      373280 :             add_base_rels_to_query(root, lfirst(l));
     175             :     }
     176       89506 :     else if (IsA(jtnode, JoinExpr))
     177             :     {
     178       89506 :         JoinExpr   *j = (JoinExpr *) jtnode;
     179             : 
     180       89506 :         add_base_rels_to_query(root, j->larg);
     181       89506 :         add_base_rels_to_query(root, j->rarg);
     182             :     }
     183             :     else
     184           0 :         elog(ERROR, "unrecognized node type: %d",
     185             :              (int) nodeTag(jtnode));
     186             : }
     187             : 
     188             : /*
     189             :  * add_other_rels_to_query
     190             :  *    create "otherrel" RelOptInfos for the children of appendrel baserels
     191             :  *
     192             :  * At the end of this process, there should be RelOptInfos for all relations
     193             :  * that will be scanned by the query.
     194             :  */
     195             : void
     196      314636 : add_other_rels_to_query(PlannerInfo *root)
     197             : {
     198             :     int         rti;
     199             : 
     200      951660 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     201             :     {
     202      637026 :         RelOptInfo *rel = root->simple_rel_array[rti];
     203      637026 :         RangeTblEntry *rte = root->simple_rte_array[rti];
     204             : 
     205             :         /* there may be empty slots corresponding to non-baserel RTEs */
     206      637026 :         if (rel == NULL)
     207      149266 :             continue;
     208             : 
     209             :         /* Ignore any "otherrels" that were already added. */
     210      487760 :         if (rel->reloptkind != RELOPT_BASEREL)
     211       44958 :             continue;
     212             : 
     213             :         /* If it's marked as inheritable, look for children. */
     214      442802 :         if (rte->inh)
     215       18000 :             expand_inherited_rtentry(root, rel, rte, rti);
     216             :     }
     217      314634 : }
     218             : 
     219             : 
     220             : /*****************************************************************************
     221             :  *
     222             :  *   TARGET LISTS
     223             :  *
     224             :  *****************************************************************************/
     225             : 
     226             : /*
     227             :  * build_base_rel_tlists
     228             :  *    Add targetlist entries for each var needed in the query's final tlist
     229             :  *    (and HAVING clause, if any) to the appropriate base relations.
     230             :  *
     231             :  * We mark such vars as needed by "relation 0" to ensure that they will
     232             :  * propagate up through all join plan steps.
     233             :  */
     234             : void
     235      314666 : build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
     236             : {
     237      314666 :     List       *tlist_vars = pull_var_clause((Node *) final_tlist,
     238             :                                              PVC_RECURSE_AGGREGATES |
     239             :                                              PVC_RECURSE_WINDOWFUNCS |
     240             :                                              PVC_INCLUDE_PLACEHOLDERS);
     241             : 
     242      314666 :     if (tlist_vars != NIL)
     243             :     {
     244      297724 :         add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
     245      297724 :         list_free(tlist_vars);
     246             :     }
     247             : 
     248             :     /*
     249             :      * If there's a HAVING clause, we'll need the Vars it uses, too.  Note
     250             :      * that HAVING can contain Aggrefs but not WindowFuncs.
     251             :      */
     252      314666 :     if (root->parse->havingQual)
     253             :     {
     254         858 :         List       *having_vars = pull_var_clause(root->parse->havingQual,
     255             :                                                   PVC_RECURSE_AGGREGATES |
     256             :                                                   PVC_INCLUDE_PLACEHOLDERS);
     257             : 
     258         858 :         if (having_vars != NIL)
     259             :         {
     260         762 :             add_vars_to_targetlist(root, having_vars,
     261             :                                    bms_make_singleton(0));
     262         762 :             list_free(having_vars);
     263             :         }
     264             :     }
     265      314666 : }
     266             : 
     267             : /*
     268             :  * add_vars_to_targetlist
     269             :  *    For each variable appearing in the list, add it to the owning
     270             :  *    relation's targetlist if not already present, and mark the variable
     271             :  *    as being needed for the indicated join (or for final output if
     272             :  *    where_needed includes "relation 0").
     273             :  *
     274             :  *    The list may also contain PlaceHolderVars.  These don't necessarily
     275             :  *    have a single owning relation; we keep their attr_needed info in
     276             :  *    root->placeholder_list instead.  Find or create the associated
     277             :  *    PlaceHolderInfo entry, and update its ph_needed.
     278             :  *
     279             :  *    See also add_vars_to_attr_needed.
     280             :  */
     281             : void
     282      586424 : add_vars_to_targetlist(PlannerInfo *root, List *vars,
     283             :                        Relids where_needed)
     284             : {
     285             :     ListCell   *temp;
     286             : 
     287             :     Assert(!bms_is_empty(where_needed));
     288             : 
     289     2174882 :     foreach(temp, vars)
     290             :     {
     291     1588458 :         Node       *node = (Node *) lfirst(temp);
     292             : 
     293     1588458 :         if (IsA(node, Var))
     294             :         {
     295     1585434 :             Var        *var = (Var *) node;
     296     1585434 :             RelOptInfo *rel = find_base_rel(root, var->varno);
     297     1585434 :             int         attno = var->varattno;
     298             : 
     299     1585434 :             if (bms_is_subset(where_needed, rel->relids))
     300        1366 :                 continue;
     301             :             Assert(attno >= rel->min_attr && attno <= rel->max_attr);
     302     1584068 :             attno -= rel->min_attr;
     303     1584068 :             if (rel->attr_needed[attno] == NULL)
     304             :             {
     305             :                 /*
     306             :                  * Variable not yet requested, so add to rel's targetlist.
     307             :                  *
     308             :                  * The value available at the rel's scan level has not been
     309             :                  * nulled by any outer join, so drop its varnullingrels.
     310             :                  * (We'll put those back as we climb up the join tree.)
     311             :                  */
     312     1161516 :                 var = copyObject(var);
     313     1161516 :                 var->varnullingrels = NULL;
     314     1161516 :                 rel->reltarget->exprs = lappend(rel->reltarget->exprs, var);
     315             :                 /* reltarget cost and width will be computed later */
     316             :             }
     317     1584068 :             rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
     318             :                                                       where_needed);
     319             :         }
     320        3024 :         else if (IsA(node, PlaceHolderVar))
     321             :         {
     322        3024 :             PlaceHolderVar *phv = (PlaceHolderVar *) node;
     323        3024 :             PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
     324             : 
     325        3024 :             phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
     326             :                                                 where_needed);
     327             :         }
     328             :         else
     329           0 :             elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
     330             :     }
     331      586424 : }
     332             : 
     333             : /*
     334             :  * add_vars_to_attr_needed
     335             :  *    This does a subset of what add_vars_to_targetlist does: it just
     336             :  *    updates attr_needed for Vars and ph_needed for PlaceHolderVars.
     337             :  *    We assume the Vars are already in their relations' targetlists.
     338             :  *
     339             :  *    This is used to rebuild attr_needed/ph_needed sets after removal
     340             :  *    of a useless outer join.  The removed join clause might have been
     341             :  *    the only upper-level use of some other relation's Var, in which
     342             :  *    case we can reduce that Var's attr_needed and thereby possibly
     343             :  *    open the door to further join removals.  But we can't tell that
     344             :  *    without tedious reconstruction of the attr_needed data.
     345             :  *
     346             :  *    Note that if a Var's attr_needed is successfully reduced to empty,
     347             :  *    it will still be in the relation's targetlist even though we do
     348             :  *    not really need the scan plan node to emit it.  The extra plan
     349             :  *    inefficiency seems tiny enough to not be worth spending planner
     350             :  *    cycles to get rid of it.
     351             :  */
     352             : void
     353       12560 : add_vars_to_attr_needed(PlannerInfo *root, List *vars,
     354             :                         Relids where_needed)
     355             : {
     356             :     ListCell   *temp;
     357             : 
     358             :     Assert(!bms_is_empty(where_needed));
     359             : 
     360       29268 :     foreach(temp, vars)
     361             :     {
     362       16708 :         Node       *node = (Node *) lfirst(temp);
     363             : 
     364       16708 :         if (IsA(node, Var))
     365             :         {
     366       16618 :             Var        *var = (Var *) node;
     367       16618 :             RelOptInfo *rel = find_base_rel(root, var->varno);
     368       16618 :             int         attno = var->varattno;
     369             : 
     370       16618 :             if (bms_is_subset(where_needed, rel->relids))
     371         844 :                 continue;
     372             :             Assert(attno >= rel->min_attr && attno <= rel->max_attr);
     373       15774 :             attno -= rel->min_attr;
     374       15774 :             rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
     375             :                                                       where_needed);
     376             :         }
     377          90 :         else if (IsA(node, PlaceHolderVar))
     378             :         {
     379          90 :             PlaceHolderVar *phv = (PlaceHolderVar *) node;
     380          90 :             PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
     381             : 
     382          90 :             phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
     383             :                                                 where_needed);
     384             :         }
     385             :         else
     386           0 :             elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
     387             :     }
     388       12560 : }
     389             : 
     390             : /*****************************************************************************
     391             :  *
     392             :  *    GROUP BY
     393             :  *
     394             :  *****************************************************************************/
     395             : 
     396             : /*
     397             :  * remove_useless_groupby_columns
     398             :  *      Remove any columns in the GROUP BY clause that are redundant due to
     399             :  *      being functionally dependent on other GROUP BY columns.
     400             :  *
     401             :  * Since some other DBMSes do not allow references to ungrouped columns, it's
     402             :  * not unusual to find all columns listed in GROUP BY even though listing the
     403             :  * primary-key columns, or columns of a unique constraint would be sufficient.
     404             :  * Deleting such excess columns avoids redundant sorting or hashing work, so
     405             :  * it's worth doing.
     406             :  *
     407             :  * Relcache invalidations will ensure that cached plans become invalidated
     408             :  * when the underlying supporting indexes are dropped or if a column's NOT
     409             :  * NULL attribute is removed.
     410             :  */
     411             : void
     412      314636 : remove_useless_groupby_columns(PlannerInfo *root)
     413             : {
     414      314636 :     Query      *parse = root->parse;
     415             :     Bitmapset **groupbyattnos;
     416             :     Bitmapset **surplusvars;
     417      314636 :     bool        tryremove = false;
     418             :     ListCell   *lc;
     419             :     int         relid;
     420             : 
     421             :     /* No chance to do anything if there are less than two GROUP BY items */
     422      314636 :     if (list_length(root->processed_groupClause) < 2)
     423      312654 :         return;
     424             : 
     425             :     /* Don't fiddle with the GROUP BY clause if the query has grouping sets */
     426        1982 :     if (parse->groupingSets)
     427         662 :         return;
     428             : 
     429             :     /*
     430             :      * Scan the GROUP BY clause to find GROUP BY items that are simple Vars.
     431             :      * Fill groupbyattnos[k] with a bitmapset of the column attnos of RTE k
     432             :      * that are GROUP BY items.
     433             :      */
     434        1320 :     groupbyattnos = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
     435        1320 :                                            (list_length(parse->rtable) + 1));
     436        4736 :     foreach(lc, root->processed_groupClause)
     437             :     {
     438        3416 :         SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
     439        3416 :         TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
     440        3416 :         Var        *var = (Var *) tle->expr;
     441             : 
     442             :         /*
     443             :          * Ignore non-Vars and Vars from other query levels.
     444             :          *
     445             :          * XXX in principle, stable expressions containing Vars could also be
     446             :          * removed, if all the Vars are functionally dependent on other GROUP
     447             :          * BY items.  But it's not clear that such cases occur often enough to
     448             :          * be worth troubling over.
     449             :          */
     450        3416 :         if (!IsA(var, Var) ||
     451        2606 :             var->varlevelsup > 0)
     452         810 :             continue;
     453             : 
     454             :         /* OK, remember we have this Var */
     455        2606 :         relid = var->varno;
     456             :         Assert(relid <= list_length(parse->rtable));
     457             : 
     458             :         /*
     459             :          * If this isn't the first column for this relation then we now have
     460             :          * multiple columns.  That means there might be some that can be
     461             :          * removed.
     462             :          */
     463        2606 :         tryremove |= !bms_is_empty(groupbyattnos[relid]);
     464        2606 :         groupbyattnos[relid] = bms_add_member(groupbyattnos[relid],
     465        2606 :                                               var->varattno - FirstLowInvalidHeapAttributeNumber);
     466             :     }
     467             : 
     468             :     /*
     469             :      * No Vars or didn't find multiple Vars for any relation in the GROUP BY?
     470             :      * If so, nothing can be removed, so don't waste more effort trying.
     471             :      */
     472        1320 :     if (!tryremove)
     473         452 :         return;
     474             : 
     475             :     /*
     476             :      * Consider each relation and see if it is possible to remove some of its
     477             :      * Vars from GROUP BY.  For simplicity and speed, we do the actual removal
     478             :      * in a separate pass.  Here, we just fill surplusvars[k] with a bitmapset
     479             :      * of the column attnos of RTE k that are removable GROUP BY items.
     480             :      */
     481         868 :     surplusvars = NULL;         /* don't allocate array unless required */
     482         868 :     relid = 0;
     483        3342 :     foreach(lc, parse->rtable)
     484             :     {
     485        2474 :         RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
     486             :         RelOptInfo *rel;
     487             :         Bitmapset  *relattnos;
     488        2474 :         Bitmapset  *best_keycolumns = NULL;
     489        2474 :         int32       best_nkeycolumns = PG_INT32_MAX;
     490             : 
     491        2474 :         relid++;
     492             : 
     493             :         /* Only plain relations could have primary-key constraints */
     494        2474 :         if (rte->rtekind != RTE_RELATION)
     495        1264 :             continue;
     496             : 
     497             :         /*
     498             :          * We must skip inheritance parent tables as some of the child rels
     499             :          * may cause duplicate rows.  This cannot happen with partitioned
     500             :          * tables, however.
     501             :          */
     502        1210 :         if (rte->inh && rte->relkind != RELKIND_PARTITIONED_TABLE)
     503          18 :             continue;
     504             : 
     505             :         /* Nothing to do unless this rel has multiple Vars in GROUP BY */
     506        1192 :         relattnos = groupbyattnos[relid];
     507        1192 :         if (bms_membership(relattnos) != BMS_MULTIPLE)
     508         360 :             continue;
     509             : 
     510         832 :         rel = root->simple_rel_array[relid];
     511             : 
     512             :         /*
     513             :          * Now check each index for this relation to see if there are any with
     514             :          * columns which are a proper subset of the grouping columns for this
     515             :          * relation.
     516             :          */
     517        2380 :         foreach_node(IndexOptInfo, index, rel->indexlist)
     518             :         {
     519             :             Bitmapset  *ind_attnos;
     520             :             bool        nulls_check_ok;
     521             : 
     522             :             /*
     523             :              * Skip any non-unique and deferrable indexes.  Predicate indexes
     524             :              * have not been checked yet, so we must skip those too as the
     525             :              * predOK check that's done later might fail.
     526             :              */
     527         716 :             if (!index->unique || !index->immediate || index->indpred != NIL)
     528         300 :                 continue;
     529             : 
     530             :             /* For simplicity, we currently don't support expression indexes */
     531         416 :             if (index->indexprs != NIL)
     532           0 :                 continue;
     533             : 
     534         416 :             ind_attnos = NULL;
     535         416 :             nulls_check_ok = true;
     536        1054 :             for (int i = 0; i < index->nkeycolumns; i++)
     537             :             {
     538             :                 /*
     539             :                  * We must insist that the index columns are all defined NOT
     540             :                  * NULL otherwise duplicate NULLs could exist.  However, we
     541             :                  * can relax this check when the index is defined with NULLS
     542             :                  * NOT DISTINCT as there can only be 1 NULL row, therefore
     543             :                  * functional dependency on the unique columns is maintained,
     544             :                  * despite the NULL.
     545             :                  */
     546         644 :                 if (!index->nullsnotdistinct &&
     547         638 :                     !bms_is_member(index->indexkeys[i],
     548         638 :                                    rel->notnullattnums))
     549             :                 {
     550           6 :                     nulls_check_ok = false;
     551           6 :                     break;
     552             :                 }
     553             : 
     554             :                 ind_attnos =
     555         638 :                     bms_add_member(ind_attnos,
     556         638 :                                    index->indexkeys[i] -
     557             :                                    FirstLowInvalidHeapAttributeNumber);
     558             :             }
     559             : 
     560         416 :             if (!nulls_check_ok)
     561           6 :                 continue;
     562             : 
     563             :             /*
     564             :              * Skip any indexes where the indexed columns aren't a proper
     565             :              * subset of the GROUP BY.
     566             :              */
     567         410 :             if (bms_subset_compare(ind_attnos, relattnos) != BMS_SUBSET1)
     568         180 :                 continue;
     569             : 
     570             :             /*
     571             :              * Record the attribute numbers from the index with the fewest
     572             :              * columns.  This allows the largest number of columns to be
     573             :              * removed from the GROUP BY clause.  In the future, we may wish
     574             :              * to consider using the narrowest set of columns and looking at
     575             :              * pg_statistic.stawidth as it might be better to use an index
     576             :              * with, say two INT4s, rather than, say, one long varlena column.
     577             :              */
     578         230 :             if (index->nkeycolumns < best_nkeycolumns)
     579             :             {
     580         212 :                 best_keycolumns = ind_attnos;
     581         212 :                 best_nkeycolumns = index->nkeycolumns;
     582             :             }
     583             :         }
     584             : 
     585             :         /* Did we find a suitable index? */
     586         832 :         if (!bms_is_empty(best_keycolumns))
     587             :         {
     588             :             /*
     589             :              * To easily remember whether we've found anything to do, we don't
     590             :              * allocate the surplusvars[] array until we find something.
     591             :              */
     592         212 :             if (surplusvars == NULL)
     593         206 :                 surplusvars = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
     594         206 :                                                      (list_length(parse->rtable) + 1));
     595             : 
     596             :             /* Remember the attnos of the removable columns */
     597         212 :             surplusvars[relid] = bms_difference(relattnos, best_keycolumns);
     598             :         }
     599             :     }
     600             : 
     601             :     /*
     602             :      * If we found any surplus Vars, build a new GROUP BY clause without them.
     603             :      * (Note: this may leave some TLEs with unreferenced ressortgroupref
     604             :      * markings, but that's harmless.)
     605             :      */
     606         868 :     if (surplusvars != NULL)
     607             :     {
     608         206 :         List       *new_groupby = NIL;
     609             : 
     610         858 :         foreach(lc, root->processed_groupClause)
     611             :         {
     612         652 :             SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
     613         652 :             TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
     614         652 :             Var        *var = (Var *) tle->expr;
     615             : 
     616             :             /*
     617             :              * New list must include non-Vars, outer Vars, and anything not
     618             :              * marked as surplus.
     619             :              */
     620         652 :             if (!IsA(var, Var) ||
     621         652 :                 var->varlevelsup > 0 ||
     622         652 :                 !bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber,
     623         652 :                                surplusvars[var->varno]))
     624         398 :                 new_groupby = lappend(new_groupby, sgc);
     625             :         }
     626             : 
     627         206 :         root->processed_groupClause = new_groupby;
     628             :     }
     629             : }
     630             : 
     631             : /*****************************************************************************
     632             :  *
     633             :  *    LATERAL REFERENCES
     634             :  *
     635             :  *****************************************************************************/
     636             : 
     637             : /*
     638             :  * find_lateral_references
     639             :  *    For each LATERAL subquery, extract all its references to Vars and
     640             :  *    PlaceHolderVars of the current query level, and make sure those values
     641             :  *    will be available for evaluation of the subquery.
     642             :  *
     643             :  * While later planning steps ensure that the Var/PHV source rels are on the
     644             :  * outside of nestloops relative to the LATERAL subquery, we also need to
     645             :  * ensure that the Vars/PHVs propagate up to the nestloop join level; this
     646             :  * means setting suitable where_needed values for them.
     647             :  *
     648             :  * Note that this only deals with lateral references in unflattened LATERAL
     649             :  * subqueries.  When we flatten a LATERAL subquery, its lateral references
     650             :  * become plain Vars in the parent query, but they may have to be wrapped in
     651             :  * PlaceHolderVars if they need to be forced NULL by outer joins that don't
     652             :  * also null the LATERAL subquery.  That's all handled elsewhere.
     653             :  *
     654             :  * This has to run before deconstruct_jointree, since it might result in
     655             :  * creation of PlaceHolderInfos.
     656             :  */
     657             : void
     658      314636 : find_lateral_references(PlannerInfo *root)
     659             : {
     660             :     Index       rti;
     661             : 
     662             :     /* We need do nothing if the query contains no LATERAL RTEs */
     663      314636 :     if (!root->hasLateralRTEs)
     664      304370 :         return;
     665             : 
     666             :     /*
     667             :      * Examine all baserels (the rel array has been set up by now).
     668             :      */
     669       38138 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     670             :     {
     671       27872 :         RelOptInfo *brel = root->simple_rel_array[rti];
     672             : 
     673             :         /* there may be empty slots corresponding to non-baserel RTEs */
     674       27872 :         if (brel == NULL)
     675        5560 :             continue;
     676             : 
     677             :         Assert(brel->relid == rti); /* sanity check on array */
     678             : 
     679             :         /*
     680             :          * This bit is less obvious than it might look.  We ignore appendrel
     681             :          * otherrels and consider only their parent baserels.  In a case where
     682             :          * a LATERAL-containing UNION ALL subquery was pulled up, it is the
     683             :          * otherrel that is actually going to be in the plan.  However, we
     684             :          * want to mark all its lateral references as needed by the parent,
     685             :          * because it is the parent's relid that will be used for join
     686             :          * planning purposes.  And the parent's RTE will contain all the
     687             :          * lateral references we need to know, since the pulled-up member is
     688             :          * nothing but a copy of parts of the original RTE's subquery.  We
     689             :          * could visit the parent's children instead and transform their
     690             :          * references back to the parent's relid, but it would be much more
     691             :          * complicated for no real gain.  (Important here is that the child
     692             :          * members have not yet received any processing beyond being pulled
     693             :          * up.)  Similarly, in appendrels created by inheritance expansion,
     694             :          * it's sufficient to look at the parent relation.
     695             :          */
     696             : 
     697             :         /* ignore RTEs that are "other rels" */
     698       22312 :         if (brel->reloptkind != RELOPT_BASEREL)
     699           0 :             continue;
     700             : 
     701       22312 :         extract_lateral_references(root, brel, rti);
     702             :     }
     703             : }
     704             : 
     705             : static void
     706       22312 : extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
     707             : {
     708       22312 :     RangeTblEntry *rte = root->simple_rte_array[rtindex];
     709             :     List       *vars;
     710             :     List       *newvars;
     711             :     Relids      where_needed;
     712             :     ListCell   *lc;
     713             : 
     714             :     /* No cross-references are possible if it's not LATERAL */
     715       22312 :     if (!rte->lateral)
     716       12752 :         return;
     717             : 
     718             :     /* Fetch the appropriate variables */
     719        9560 :     if (rte->rtekind == RTE_RELATION)
     720          36 :         vars = pull_vars_of_level((Node *) rte->tablesample, 0);
     721        9524 :     else if (rte->rtekind == RTE_SUBQUERY)
     722         584 :         vars = pull_vars_of_level((Node *) rte->subquery, 1);
     723        8940 :     else if (rte->rtekind == RTE_FUNCTION)
     724        8652 :         vars = pull_vars_of_level((Node *) rte->functions, 0);
     725         288 :     else if (rte->rtekind == RTE_TABLEFUNC)
     726         234 :         vars = pull_vars_of_level((Node *) rte->tablefunc, 0);
     727          54 :     else if (rte->rtekind == RTE_VALUES)
     728          54 :         vars = pull_vars_of_level((Node *) rte->values_lists, 0);
     729             :     else
     730             :     {
     731             :         Assert(false);
     732           0 :         return;                 /* keep compiler quiet */
     733             :     }
     734             : 
     735        9560 :     if (vars == NIL)
     736          94 :         return;                 /* nothing to do */
     737             : 
     738             :     /* Copy each Var (or PlaceHolderVar) and adjust it to match our level */
     739        9466 :     newvars = NIL;
     740       19822 :     foreach(lc, vars)
     741             :     {
     742       10356 :         Node       *node = (Node *) lfirst(lc);
     743             : 
     744       10356 :         node = copyObject(node);
     745       10356 :         if (IsA(node, Var))
     746             :         {
     747       10248 :             Var        *var = (Var *) node;
     748             : 
     749             :             /* Adjustment is easy since it's just one node */
     750       10248 :             var->varlevelsup = 0;
     751             :         }
     752         108 :         else if (IsA(node, PlaceHolderVar))
     753             :         {
     754         108 :             PlaceHolderVar *phv = (PlaceHolderVar *) node;
     755         108 :             int         levelsup = phv->phlevelsup;
     756             : 
     757             :             /* Have to work harder to adjust the contained expression too */
     758         108 :             if (levelsup != 0)
     759          72 :                 IncrementVarSublevelsUp(node, -levelsup, 0);
     760             : 
     761             :             /*
     762             :              * If we pulled the PHV out of a subquery RTE, its expression
     763             :              * needs to be preprocessed.  subquery_planner() already did this
     764             :              * for level-zero PHVs in function and values RTEs, though.
     765             :              */
     766         108 :             if (levelsup > 0)
     767          72 :                 phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
     768             :         }
     769             :         else
     770             :             Assert(false);
     771       10356 :         newvars = lappend(newvars, node);
     772             :     }
     773             : 
     774        9466 :     list_free(vars);
     775             : 
     776             :     /*
     777             :      * We mark the Vars as being "needed" at the LATERAL RTE.  This is a bit
     778             :      * of a cheat: a more formal approach would be to mark each one as needed
     779             :      * at the join of the LATERAL RTE with its source RTE.  But it will work,
     780             :      * and it's much less tedious than computing a separate where_needed for
     781             :      * each Var.
     782             :      */
     783        9466 :     where_needed = bms_make_singleton(rtindex);
     784             : 
     785             :     /*
     786             :      * Push Vars into their source relations' targetlists, and PHVs into
     787             :      * root->placeholder_list.
     788             :      */
     789        9466 :     add_vars_to_targetlist(root, newvars, where_needed);
     790             : 
     791             :     /*
     792             :      * Remember the lateral references for rebuild_lateral_attr_needed and
     793             :      * create_lateral_join_info.
     794             :      */
     795        9466 :     brel->lateral_vars = newvars;
     796             : }
     797             : 
     798             : /*
     799             :  * rebuild_lateral_attr_needed
     800             :  *    Put back attr_needed bits for Vars/PHVs needed for lateral references.
     801             :  *
     802             :  * This is used to rebuild attr_needed/ph_needed sets after removal of a
     803             :  * useless outer join.  It should match what find_lateral_references did,
     804             :  * except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
     805             :  */
     806             : void
     807       10828 : rebuild_lateral_attr_needed(PlannerInfo *root)
     808             : {
     809             :     Index       rti;
     810             : 
     811             :     /* We need do nothing if the query contains no LATERAL RTEs */
     812       10828 :     if (!root->hasLateralRTEs)
     813       10480 :         return;
     814             : 
     815             :     /* Examine the same baserels that find_lateral_references did */
     816        3272 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     817             :     {
     818        2924 :         RelOptInfo *brel = root->simple_rel_array[rti];
     819             :         Relids      where_needed;
     820             : 
     821        2924 :         if (brel == NULL)
     822        2068 :             continue;
     823         856 :         if (brel->reloptkind != RELOPT_BASEREL)
     824           0 :             continue;
     825             : 
     826             :         /*
     827             :          * We don't need to repeat all of extract_lateral_references, since it
     828             :          * kindly saved the extracted Vars/PHVs in lateral_vars.
     829             :          */
     830         856 :         if (brel->lateral_vars == NIL)
     831         734 :             continue;
     832             : 
     833         122 :         where_needed = bms_make_singleton(rti);
     834             : 
     835         122 :         add_vars_to_attr_needed(root, brel->lateral_vars, where_needed);
     836             :     }
     837             : }
     838             : 
     839             : /*
     840             :  * create_lateral_join_info
     841             :  *    Fill in the per-base-relation direct_lateral_relids, lateral_relids
     842             :  *    and lateral_referencers sets.
     843             :  */
     844             : void
     845      314636 : create_lateral_join_info(PlannerInfo *root)
     846             : {
     847      314636 :     bool        found_laterals = false;
     848             :     Index       rti;
     849             :     ListCell   *lc;
     850             : 
     851             :     /* We need do nothing if the query contains no LATERAL RTEs */
     852      314636 :     if (!root->hasLateralRTEs)
     853      304370 :         return;
     854             : 
     855             :     /* We'll need to have the ph_eval_at values for PlaceHolderVars */
     856             :     Assert(root->placeholdersFrozen);
     857             : 
     858             :     /*
     859             :      * Examine all baserels (the rel array has been set up by now).
     860             :      */
     861       38138 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     862             :     {
     863       27872 :         RelOptInfo *brel = root->simple_rel_array[rti];
     864             :         Relids      lateral_relids;
     865             : 
     866             :         /* there may be empty slots corresponding to non-baserel RTEs */
     867       27872 :         if (brel == NULL)
     868        5908 :             continue;
     869             : 
     870             :         Assert(brel->relid == rti); /* sanity check on array */
     871             : 
     872             :         /* ignore RTEs that are "other rels" */
     873       21964 :         if (brel->reloptkind != RELOPT_BASEREL)
     874           0 :             continue;
     875             : 
     876       21964 :         lateral_relids = NULL;
     877             : 
     878             :         /* consider each laterally-referenced Var or PHV */
     879       32296 :         foreach(lc, brel->lateral_vars)
     880             :         {
     881       10332 :             Node       *node = (Node *) lfirst(lc);
     882             : 
     883       10332 :             if (IsA(node, Var))
     884             :             {
     885       10224 :                 Var        *var = (Var *) node;
     886             : 
     887       10224 :                 found_laterals = true;
     888       10224 :                 lateral_relids = bms_add_member(lateral_relids,
     889             :                                                 var->varno);
     890             :             }
     891         108 :             else if (IsA(node, PlaceHolderVar))
     892             :             {
     893         108 :                 PlaceHolderVar *phv = (PlaceHolderVar *) node;
     894         108 :                 PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
     895             : 
     896         108 :                 found_laterals = true;
     897         108 :                 lateral_relids = bms_add_members(lateral_relids,
     898         108 :                                                  phinfo->ph_eval_at);
     899             :             }
     900             :             else
     901             :                 Assert(false);
     902             :         }
     903             : 
     904             :         /* We now have all the simple lateral refs from this rel */
     905       21964 :         brel->direct_lateral_relids = lateral_relids;
     906       21964 :         brel->lateral_relids = bms_copy(lateral_relids);
     907             :     }
     908             : 
     909             :     /*
     910             :      * Now check for lateral references within PlaceHolderVars, and mark their
     911             :      * eval_at rels as having lateral references to the source rels.
     912             :      *
     913             :      * For a PHV that is due to be evaluated at a baserel, mark its source(s)
     914             :      * as direct lateral dependencies of the baserel (adding onto the ones
     915             :      * recorded above).  If it's due to be evaluated at a join, mark its
     916             :      * source(s) as indirect lateral dependencies of each baserel in the join,
     917             :      * ie put them into lateral_relids but not direct_lateral_relids.  This is
     918             :      * appropriate because we can't put any such baserel on the outside of a
     919             :      * join to one of the PHV's lateral dependencies, but on the other hand we
     920             :      * also can't yet join it directly to the dependency.
     921             :      */
     922       10814 :     foreach(lc, root->placeholder_list)
     923             :     {
     924         548 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
     925         548 :         Relids      eval_at = phinfo->ph_eval_at;
     926             :         Relids      lateral_refs;
     927             :         int         varno;
     928             : 
     929         548 :         if (phinfo->ph_lateral == NULL)
     930         286 :             continue;           /* PHV is uninteresting if no lateral refs */
     931             : 
     932         262 :         found_laterals = true;
     933             : 
     934             :         /*
     935             :          * Include only baserels not outer joins in the evaluation sites'
     936             :          * lateral relids.  This avoids problems when outer join order gets
     937             :          * rearranged, and it should still ensure that the lateral values are
     938             :          * available when needed.
     939             :          */
     940         262 :         lateral_refs = bms_intersect(phinfo->ph_lateral, root->all_baserels);
     941             :         Assert(!bms_is_empty(lateral_refs));
     942             : 
     943         262 :         if (bms_get_singleton_member(eval_at, &varno))
     944             :         {
     945             :             /* Evaluation site is a baserel */
     946         196 :             RelOptInfo *brel = find_base_rel(root, varno);
     947             : 
     948         196 :             brel->direct_lateral_relids =
     949         196 :                 bms_add_members(brel->direct_lateral_relids,
     950             :                                 lateral_refs);
     951         196 :             brel->lateral_relids =
     952         196 :                 bms_add_members(brel->lateral_relids,
     953             :                                 lateral_refs);
     954             :         }
     955             :         else
     956             :         {
     957             :             /* Evaluation site is a join */
     958          66 :             varno = -1;
     959         198 :             while ((varno = bms_next_member(eval_at, varno)) >= 0)
     960             :             {
     961         132 :                 RelOptInfo *brel = find_base_rel_ignore_join(root, varno);
     962             : 
     963         132 :                 if (brel == NULL)
     964           0 :                     continue;   /* ignore outer joins in eval_at */
     965         132 :                 brel->lateral_relids = bms_add_members(brel->lateral_relids,
     966             :                                                        lateral_refs);
     967             :             }
     968             :         }
     969             :     }
     970             : 
     971             :     /*
     972             :      * If we found no actual lateral references, we're done; but reset the
     973             :      * hasLateralRTEs flag to avoid useless work later.
     974             :      */
     975       10266 :     if (!found_laterals)
     976             :     {
     977         646 :         root->hasLateralRTEs = false;
     978         646 :         return;
     979             :     }
     980             : 
     981             :     /*
     982             :      * Calculate the transitive closure of the lateral_relids sets, so that
     983             :      * they describe both direct and indirect lateral references.  If relation
     984             :      * X references Y laterally, and Y references Z laterally, then we will
     985             :      * have to scan X on the inside of a nestloop with Z, so for all intents
     986             :      * and purposes X is laterally dependent on Z too.
     987             :      *
     988             :      * This code is essentially Warshall's algorithm for transitive closure.
     989             :      * The outer loop considers each baserel, and propagates its lateral
     990             :      * dependencies to those baserels that have a lateral dependency on it.
     991             :      */
     992       33570 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     993             :     {
     994       23950 :         RelOptInfo *brel = root->simple_rel_array[rti];
     995             :         Relids      outer_lateral_relids;
     996             :         Index       rti2;
     997             : 
     998       23950 :         if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
     999        3358 :             continue;
    1000             : 
    1001             :         /* need not consider baserel further if it has no lateral refs */
    1002       20592 :         outer_lateral_relids = brel->lateral_relids;
    1003       20592 :         if (outer_lateral_relids == NULL)
    1004       10822 :             continue;
    1005             : 
    1006             :         /* else scan all baserels */
    1007       34650 :         for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
    1008             :         {
    1009       24880 :             RelOptInfo *brel2 = root->simple_rel_array[rti2];
    1010             : 
    1011       24880 :             if (brel2 == NULL || brel2->reloptkind != RELOPT_BASEREL)
    1012        3742 :                 continue;
    1013             : 
    1014             :             /* if brel2 has lateral ref to brel, propagate brel's refs */
    1015       21138 :             if (bms_is_member(rti, brel2->lateral_relids))
    1016          66 :                 brel2->lateral_relids = bms_add_members(brel2->lateral_relids,
    1017             :                                                         outer_lateral_relids);
    1018             :         }
    1019             :     }
    1020             : 
    1021             :     /*
    1022             :      * Now that we've identified all lateral references, mark each baserel
    1023             :      * with the set of relids of rels that reference it laterally (possibly
    1024             :      * indirectly) --- that is, the inverse mapping of lateral_relids.
    1025             :      */
    1026       33570 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
    1027             :     {
    1028       23950 :         RelOptInfo *brel = root->simple_rel_array[rti];
    1029             :         Relids      lateral_relids;
    1030             :         int         rti2;
    1031             : 
    1032       23950 :         if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
    1033        3358 :             continue;
    1034             : 
    1035             :         /* Nothing to do at rels with no lateral refs */
    1036       20592 :         lateral_relids = brel->lateral_relids;
    1037       20592 :         if (bms_is_empty(lateral_relids))
    1038       10822 :             continue;
    1039             : 
    1040             :         /* No rel should have a lateral dependency on itself */
    1041             :         Assert(!bms_is_member(rti, lateral_relids));
    1042             : 
    1043             :         /* Mark this rel's referencees */
    1044        9770 :         rti2 = -1;
    1045       19768 :         while ((rti2 = bms_next_member(lateral_relids, rti2)) >= 0)
    1046             :         {
    1047        9998 :             RelOptInfo *brel2 = root->simple_rel_array[rti2];
    1048             : 
    1049        9998 :             if (brel2 == NULL)
    1050          12 :                 continue;       /* must be an OJ */
    1051             : 
    1052             :             Assert(brel2->reloptkind == RELOPT_BASEREL);
    1053        9986 :             brel2->lateral_referencers =
    1054        9986 :                 bms_add_member(brel2->lateral_referencers, rti);
    1055             :         }
    1056             :     }
    1057             : }
    1058             : 
    1059             : 
    1060             : /*****************************************************************************
    1061             :  *
    1062             :  *    JOIN TREE PROCESSING
    1063             :  *
    1064             :  *****************************************************************************/
    1065             : 
    1066             : /*
    1067             :  * deconstruct_jointree
    1068             :  *    Recursively scan the query's join tree for WHERE and JOIN/ON qual
    1069             :  *    clauses, and add these to the appropriate restrictinfo and joininfo
    1070             :  *    lists belonging to base RelOptInfos.  Also, add SpecialJoinInfo nodes
    1071             :  *    to root->join_info_list for any outer joins appearing in the query tree.
    1072             :  *    Return a "joinlist" data structure showing the join order decisions
    1073             :  *    that need to be made by make_one_rel().
    1074             :  *
    1075             :  * The "joinlist" result is a list of items that are either RangeTblRef
    1076             :  * jointree nodes or sub-joinlists.  All the items at the same level of
    1077             :  * joinlist must be joined in an order to be determined by make_one_rel()
    1078             :  * (note that legal orders may be constrained by SpecialJoinInfo nodes).
    1079             :  * A sub-joinlist represents a subproblem to be planned separately. Currently
    1080             :  * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
    1081             :  * subproblems is stopped by join_collapse_limit or from_collapse_limit.
    1082             :  */
    1083             : List *
    1084      314636 : deconstruct_jointree(PlannerInfo *root)
    1085             : {
    1086             :     List       *result;
    1087             :     JoinDomain *top_jdomain;
    1088      314636 :     List       *item_list = NIL;
    1089             :     ListCell   *lc;
    1090             : 
    1091             :     /*
    1092             :      * After this point, no more PlaceHolderInfos may be made, because
    1093             :      * make_outerjoininfo requires all active placeholders to be present in
    1094             :      * root->placeholder_list while we crawl up the join tree.
    1095             :      */
    1096      314636 :     root->placeholdersFrozen = true;
    1097             : 
    1098             :     /* Fetch the already-created top-level join domain for the query */
    1099      314636 :     top_jdomain = linitial_node(JoinDomain, root->join_domains);
    1100      314636 :     top_jdomain->jd_relids = NULL;   /* filled during deconstruct_recurse */
    1101             : 
    1102             :     /* Start recursion at top of jointree */
    1103             :     Assert(root->parse->jointree != NULL &&
    1104             :            IsA(root->parse->jointree, FromExpr));
    1105             : 
    1106             :     /* These are filled as we scan the jointree */
    1107      314636 :     root->all_baserels = NULL;
    1108      314636 :     root->outer_join_rels = NULL;
    1109             : 
    1110             :     /* Perform the initial scan of the jointree */
    1111      314636 :     result = deconstruct_recurse(root, (Node *) root->parse->jointree,
    1112             :                                  top_jdomain, NULL,
    1113             :                                  &item_list);
    1114             : 
    1115             :     /* Now we can form the value of all_query_rels, too */
    1116      314636 :     root->all_query_rels = bms_union(root->all_baserels, root->outer_join_rels);
    1117             : 
    1118             :     /* ... which should match what we computed for the top join domain */
    1119             :     Assert(bms_equal(root->all_query_rels, top_jdomain->jd_relids));
    1120             : 
    1121             :     /* Now scan all the jointree nodes again, and distribute quals */
    1122     1181546 :     foreach(lc, item_list)
    1123             :     {
    1124      866910 :         JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);
    1125             : 
    1126      866910 :         deconstruct_distribute(root, jtitem);
    1127             :     }
    1128             : 
    1129             :     /*
    1130             :      * If there were any special joins then we may have some postponed LEFT
    1131             :      * JOIN clauses to deal with.
    1132             :      */
    1133      314636 :     if (root->join_info_list)
    1134             :     {
    1135      233388 :         foreach(lc, item_list)
    1136             :         {
    1137      197966 :             JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);
    1138             : 
    1139      197966 :             if (jtitem->oj_joinclauses != NIL)
    1140       40672 :                 deconstruct_distribute_oj_quals(root, item_list, jtitem);
    1141             :         }
    1142             :     }
    1143             : 
    1144             :     /* Don't need the JoinTreeItems any more */
    1145      314636 :     list_free_deep(item_list);
    1146             : 
    1147      314636 :     return result;
    1148             : }
    1149             : 
    1150             : /*
    1151             :  * deconstruct_recurse
    1152             :  *    One recursion level of deconstruct_jointree's initial jointree scan.
    1153             :  *
    1154             :  * jtnode is the jointree node to examine, and parent_domain is the
    1155             :  * enclosing join domain.  (We must add all base+OJ relids appearing
    1156             :  * here or below to parent_domain.)  parent_jtitem is the JoinTreeItem
    1157             :  * for the parent jointree node, or NULL at the top of the recursion.
    1158             :  *
    1159             :  * item_list is an in/out parameter: we add a JoinTreeItem struct to
    1160             :  * that list for each jointree node, in depth-first traversal order.
    1161             :  * (Hence, after each call, the last list item corresponds to its jtnode.)
    1162             :  *
    1163             :  * Return value is the appropriate joinlist for this jointree node.
    1164             :  */
    1165             : static List *
    1166      866910 : deconstruct_recurse(PlannerInfo *root, Node *jtnode,
    1167             :                     JoinDomain *parent_domain,
    1168             :                     JoinTreeItem *parent_jtitem,
    1169             :                     List **item_list)
    1170             : {
    1171             :     List       *joinlist;
    1172             :     JoinTreeItem *jtitem;
    1173             : 
    1174             :     Assert(jtnode != NULL);
    1175             : 
    1176             :     /* Make the new JoinTreeItem, but don't add it to item_list yet */
    1177      866910 :     jtitem = palloc0_object(JoinTreeItem);
    1178      866910 :     jtitem->jtnode = jtnode;
    1179      866910 :     jtitem->jti_parent = parent_jtitem;
    1180             : 
    1181      866910 :     if (IsA(jtnode, RangeTblRef))
    1182             :     {
    1183      453630 :         int         varno = ((RangeTblRef *) jtnode)->rtindex;
    1184             : 
    1185             :         /* Fill all_baserels as we encounter baserel jointree nodes */
    1186      453630 :         root->all_baserels = bms_add_member(root->all_baserels, varno);
    1187             :         /* This node belongs to parent_domain */
    1188      453630 :         jtitem->jdomain = parent_domain;
    1189      453630 :         parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
    1190             :                                                   varno);
    1191             :         /* qualscope is just the one RTE */
    1192      453630 :         jtitem->qualscope = bms_make_singleton(varno);
    1193             :         /* A single baserel does not create an inner join */
    1194      453630 :         jtitem->inner_join_rels = NULL;
    1195      453630 :         joinlist = list_make1(jtnode);
    1196             :     }
    1197      413280 :     else if (IsA(jtnode, FromExpr))
    1198             :     {
    1199      323774 :         FromExpr   *f = (FromExpr *) jtnode;
    1200             :         int         remaining;
    1201             :         ListCell   *l;
    1202             : 
    1203             :         /* This node belongs to parent_domain, as do its children */
    1204      323774 :         jtitem->jdomain = parent_domain;
    1205             : 
    1206             :         /*
    1207             :          * Recurse to handle child nodes, and compute output joinlist.  We
    1208             :          * collapse subproblems into a single joinlist whenever the resulting
    1209             :          * joinlist wouldn't exceed from_collapse_limit members.  Also, always
    1210             :          * collapse one-element subproblems, since that won't lengthen the
    1211             :          * joinlist anyway.
    1212             :          */
    1213      323774 :         jtitem->qualscope = NULL;
    1214      323774 :         jtitem->inner_join_rels = NULL;
    1215      323774 :         joinlist = NIL;
    1216      323774 :         remaining = list_length(f->fromlist);
    1217      697036 :         foreach(l, f->fromlist)
    1218             :         {
    1219             :             JoinTreeItem *sub_item;
    1220             :             List       *sub_joinlist;
    1221             :             int         sub_members;
    1222             : 
    1223      373262 :             sub_joinlist = deconstruct_recurse(root, lfirst(l),
    1224             :                                                parent_domain,
    1225             :                                                jtitem,
    1226             :                                                item_list);
    1227      373262 :             sub_item = (JoinTreeItem *) llast(*item_list);
    1228      746524 :             jtitem->qualscope = bms_add_members(jtitem->qualscope,
    1229      373262 :                                                 sub_item->qualscope);
    1230      373262 :             jtitem->inner_join_rels = sub_item->inner_join_rels;
    1231      373262 :             sub_members = list_length(sub_joinlist);
    1232      373262 :             remaining--;
    1233      373262 :             if (sub_members <= 1 ||
    1234       55676 :                 list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
    1235      373262 :                 joinlist = list_concat(joinlist, sub_joinlist);
    1236             :             else
    1237           0 :                 joinlist = lappend(joinlist, sub_joinlist);
    1238             :         }
    1239             : 
    1240             :         /*
    1241             :          * A FROM with more than one list element is an inner join subsuming
    1242             :          * all below it, so we should report inner_join_rels = qualscope. If
    1243             :          * there was exactly one element, we should (and already did) report
    1244             :          * whatever its inner_join_rels were.  If there were no elements (is
    1245             :          * that still possible?) the initialization before the loop fixed it.
    1246             :          */
    1247      323774 :         if (list_length(f->fromlist) > 1)
    1248       45028 :             jtitem->inner_join_rels = jtitem->qualscope;
    1249             :     }
    1250       89506 :     else if (IsA(jtnode, JoinExpr))
    1251             :     {
    1252       89506 :         JoinExpr   *j = (JoinExpr *) jtnode;
    1253             :         JoinDomain *child_domain,
    1254             :                    *fj_domain;
    1255             :         JoinTreeItem *left_item,
    1256             :                    *right_item;
    1257             :         List       *leftjoinlist,
    1258             :                    *rightjoinlist;
    1259             : 
    1260       89506 :         switch (j->jointype)
    1261             :         {
    1262       40294 :             case JOIN_INNER:
    1263             :                 /* This node belongs to parent_domain, as do its children */
    1264       40294 :                 jtitem->jdomain = parent_domain;
    1265             :                 /* Recurse */
    1266       40294 :                 leftjoinlist = deconstruct_recurse(root, j->larg,
    1267             :                                                    parent_domain,
    1268             :                                                    jtitem,
    1269             :                                                    item_list);
    1270       40294 :                 left_item = (JoinTreeItem *) llast(*item_list);
    1271       40294 :                 rightjoinlist = deconstruct_recurse(root, j->rarg,
    1272             :                                                     parent_domain,
    1273             :                                                     jtitem,
    1274             :                                                     item_list);
    1275       40294 :                 right_item = (JoinTreeItem *) llast(*item_list);
    1276             :                 /* Compute qualscope etc */
    1277       80588 :                 jtitem->qualscope = bms_union(left_item->qualscope,
    1278       40294 :                                               right_item->qualscope);
    1279       40294 :                 jtitem->inner_join_rels = jtitem->qualscope;
    1280       40294 :                 jtitem->left_rels = left_item->qualscope;
    1281       40294 :                 jtitem->right_rels = right_item->qualscope;
    1282             :                 /* Inner join adds no restrictions for quals */
    1283       40294 :                 jtitem->nonnullable_rels = NULL;
    1284       40294 :                 break;
    1285       45976 :             case JOIN_LEFT:
    1286             :             case JOIN_ANTI:
    1287             :                 /* Make new join domain for my quals and the RHS */
    1288       45976 :                 child_domain = makeNode(JoinDomain);
    1289       45976 :                 child_domain->jd_relids = NULL; /* filled by recursion */
    1290       45976 :                 root->join_domains = lappend(root->join_domains, child_domain);
    1291       45976 :                 jtitem->jdomain = child_domain;
    1292             :                 /* Recurse */
    1293       45976 :                 leftjoinlist = deconstruct_recurse(root, j->larg,
    1294             :                                                    parent_domain,
    1295             :                                                    jtitem,
    1296             :                                                    item_list);
    1297       45976 :                 left_item = (JoinTreeItem *) llast(*item_list);
    1298       45976 :                 rightjoinlist = deconstruct_recurse(root, j->rarg,
    1299             :                                                     child_domain,
    1300             :                                                     jtitem,
    1301             :                                                     item_list);
    1302       45976 :                 right_item = (JoinTreeItem *) llast(*item_list);
    1303             :                 /* Compute join domain contents, qualscope etc */
    1304       45976 :                 parent_domain->jd_relids =
    1305       45976 :                     bms_add_members(parent_domain->jd_relids,
    1306       45976 :                                     child_domain->jd_relids);
    1307       91952 :                 jtitem->qualscope = bms_union(left_item->qualscope,
    1308       45976 :                                               right_item->qualscope);
    1309             :                 /* caution: ANTI join derived from SEMI will lack rtindex */
    1310       45976 :                 if (j->rtindex != 0)
    1311             :                 {
    1312       43276 :                     parent_domain->jd_relids =
    1313       43276 :                         bms_add_member(parent_domain->jd_relids,
    1314             :                                        j->rtindex);
    1315       43276 :                     jtitem->qualscope = bms_add_member(jtitem->qualscope,
    1316             :                                                        j->rtindex);
    1317       43276 :                     root->outer_join_rels = bms_add_member(root->outer_join_rels,
    1318             :                                                            j->rtindex);
    1319       43276 :                     mark_rels_nulled_by_join(root, j->rtindex,
    1320             :                                              right_item->qualscope);
    1321             :                 }
    1322       91952 :                 jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
    1323       45976 :                                                     right_item->inner_join_rels);
    1324       45976 :                 jtitem->left_rels = left_item->qualscope;
    1325       45976 :                 jtitem->right_rels = right_item->qualscope;
    1326       45976 :                 jtitem->nonnullable_rels = left_item->qualscope;
    1327       45976 :                 break;
    1328        2208 :             case JOIN_SEMI:
    1329             :                 /* This node belongs to parent_domain, as do its children */
    1330        2208 :                 jtitem->jdomain = parent_domain;
    1331             :                 /* Recurse */
    1332        2208 :                 leftjoinlist = deconstruct_recurse(root, j->larg,
    1333             :                                                    parent_domain,
    1334             :                                                    jtitem,
    1335             :                                                    item_list);
    1336        2208 :                 left_item = (JoinTreeItem *) llast(*item_list);
    1337        2208 :                 rightjoinlist = deconstruct_recurse(root, j->rarg,
    1338             :                                                     parent_domain,
    1339             :                                                     jtitem,
    1340             :                                                     item_list);
    1341        2208 :                 right_item = (JoinTreeItem *) llast(*item_list);
    1342             :                 /* Compute qualscope etc */
    1343        4416 :                 jtitem->qualscope = bms_union(left_item->qualscope,
    1344        2208 :                                               right_item->qualscope);
    1345             :                 /* SEMI join never has rtindex, so don't add to anything */
    1346             :                 Assert(j->rtindex == 0);
    1347        4416 :                 jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
    1348        2208 :                                                     right_item->inner_join_rels);
    1349        2208 :                 jtitem->left_rels = left_item->qualscope;
    1350        2208 :                 jtitem->right_rels = right_item->qualscope;
    1351             :                 /* Semi join adds no restrictions for quals */
    1352        2208 :                 jtitem->nonnullable_rels = NULL;
    1353        2208 :                 break;
    1354        1028 :             case JOIN_FULL:
    1355             :                 /* The FULL JOIN's quals need their very own domain */
    1356        1028 :                 fj_domain = makeNode(JoinDomain);
    1357        1028 :                 root->join_domains = lappend(root->join_domains, fj_domain);
    1358        1028 :                 jtitem->jdomain = fj_domain;
    1359             :                 /* Recurse, giving each side its own join domain */
    1360        1028 :                 child_domain = makeNode(JoinDomain);
    1361        1028 :                 child_domain->jd_relids = NULL; /* filled by recursion */
    1362        1028 :                 root->join_domains = lappend(root->join_domains, child_domain);
    1363        1028 :                 leftjoinlist = deconstruct_recurse(root, j->larg,
    1364             :                                                    child_domain,
    1365             :                                                    jtitem,
    1366             :                                                    item_list);
    1367        1028 :                 left_item = (JoinTreeItem *) llast(*item_list);
    1368        1028 :                 fj_domain->jd_relids = bms_copy(child_domain->jd_relids);
    1369        1028 :                 child_domain = makeNode(JoinDomain);
    1370        1028 :                 child_domain->jd_relids = NULL; /* filled by recursion */
    1371        1028 :                 root->join_domains = lappend(root->join_domains, child_domain);
    1372        1028 :                 rightjoinlist = deconstruct_recurse(root, j->rarg,
    1373             :                                                     child_domain,
    1374             :                                                     jtitem,
    1375             :                                                     item_list);
    1376        1028 :                 right_item = (JoinTreeItem *) llast(*item_list);
    1377             :                 /* Compute qualscope etc */
    1378        2056 :                 fj_domain->jd_relids = bms_add_members(fj_domain->jd_relids,
    1379        1028 :                                                        child_domain->jd_relids);
    1380        2056 :                 parent_domain->jd_relids = bms_add_members(parent_domain->jd_relids,
    1381        1028 :                                                            fj_domain->jd_relids);
    1382        2056 :                 jtitem->qualscope = bms_union(left_item->qualscope,
    1383        1028 :                                               right_item->qualscope);
    1384             :                 Assert(j->rtindex != 0);
    1385        1028 :                 parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
    1386             :                                                           j->rtindex);
    1387        1028 :                 jtitem->qualscope = bms_add_member(jtitem->qualscope,
    1388             :                                                    j->rtindex);
    1389        1028 :                 root->outer_join_rels = bms_add_member(root->outer_join_rels,
    1390             :                                                        j->rtindex);
    1391        1028 :                 mark_rels_nulled_by_join(root, j->rtindex,
    1392             :                                          left_item->qualscope);
    1393        1028 :                 mark_rels_nulled_by_join(root, j->rtindex,
    1394             :                                          right_item->qualscope);
    1395        2056 :                 jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
    1396        1028 :                                                     right_item->inner_join_rels);
    1397        1028 :                 jtitem->left_rels = left_item->qualscope;
    1398        1028 :                 jtitem->right_rels = right_item->qualscope;
    1399             :                 /* each side is both outer and inner */
    1400        1028 :                 jtitem->nonnullable_rels = jtitem->qualscope;
    1401        1028 :                 break;
    1402           0 :             default:
    1403             :                 /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
    1404           0 :                 elog(ERROR, "unrecognized join type: %d",
    1405             :                      (int) j->jointype);
    1406             :                 leftjoinlist = rightjoinlist = NIL; /* keep compiler quiet */
    1407             :                 break;
    1408             :         }
    1409             : 
    1410             :         /*
    1411             :          * Compute the output joinlist.  We fold subproblems together except
    1412             :          * at a FULL JOIN or where join_collapse_limit would be exceeded.
    1413             :          */
    1414       89506 :         if (j->jointype == JOIN_FULL)
    1415             :         {
    1416             :             /* force the join order exactly at this node */
    1417        1028 :             joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
    1418             :         }
    1419       88478 :         else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
    1420             :                  join_collapse_limit)
    1421             :         {
    1422             :             /* OK to combine subproblems */
    1423       88310 :             joinlist = list_concat(leftjoinlist, rightjoinlist);
    1424             :         }
    1425             :         else
    1426             :         {
    1427             :             /* can't combine, but needn't force join order above here */
    1428             :             Node       *leftpart,
    1429             :                        *rightpart;
    1430             : 
    1431             :             /* avoid creating useless 1-element sublists */
    1432         168 :             if (list_length(leftjoinlist) == 1)
    1433          30 :                 leftpart = (Node *) linitial(leftjoinlist);
    1434             :             else
    1435         138 :                 leftpart = (Node *) leftjoinlist;
    1436         168 :             if (list_length(rightjoinlist) == 1)
    1437          24 :                 rightpart = (Node *) linitial(rightjoinlist);
    1438             :             else
    1439         144 :                 rightpart = (Node *) rightjoinlist;
    1440         168 :             joinlist = list_make2(leftpart, rightpart);
    1441             :         }
    1442             :     }
    1443             :     else
    1444             :     {
    1445           0 :         elog(ERROR, "unrecognized node type: %d",
    1446             :              (int) nodeTag(jtnode));
    1447             :         joinlist = NIL;         /* keep compiler quiet */
    1448             :     }
    1449             : 
    1450             :     /* Finally, we can add the new JoinTreeItem to item_list */
    1451      866910 :     *item_list = lappend(*item_list, jtitem);
    1452             : 
    1453      866910 :     return joinlist;
    1454             : }
    1455             : 
    1456             : /*
    1457             :  * deconstruct_distribute
    1458             :  *    Process one jointree node in phase 2 of deconstruct_jointree processing.
    1459             :  *
    1460             :  * Distribute quals of the node to appropriate restriction and join lists.
    1461             :  * In addition, entries will be added to root->join_info_list for outer joins.
    1462             :  */
    1463             : static void
    1464      866910 : deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem)
    1465             : {
    1466      866910 :     Node       *jtnode = jtitem->jtnode;
    1467             : 
    1468      866910 :     if (IsA(jtnode, RangeTblRef))
    1469             :     {
    1470      453630 :         int         varno = ((RangeTblRef *) jtnode)->rtindex;
    1471             : 
    1472             :         /* Deal with any securityQuals attached to the RTE */
    1473      453630 :         if (root->qual_security_level > 0)
    1474        2688 :             process_security_barrier_quals(root,
    1475             :                                            varno,
    1476             :                                            jtitem);
    1477             :     }
    1478      413280 :     else if (IsA(jtnode, FromExpr))
    1479             :     {
    1480      323774 :         FromExpr   *f = (FromExpr *) jtnode;
    1481             : 
    1482             :         /*
    1483             :          * Process any lateral-referencing quals that were postponed to this
    1484             :          * level by children.
    1485             :          */
    1486      323774 :         distribute_quals_to_rels(root, jtitem->lateral_clauses,
    1487             :                                  jtitem,
    1488             :                                  NULL,
    1489             :                                  root->qual_security_level,
    1490             :                                  jtitem->qualscope,
    1491             :                                  NULL, NULL, NULL,
    1492             :                                  true, false, false,
    1493             :                                  NULL);
    1494             : 
    1495             :         /*
    1496             :          * Now process the top-level quals.
    1497             :          */
    1498      323774 :         distribute_quals_to_rels(root, (List *) f->quals,
    1499             :                                  jtitem,
    1500             :                                  NULL,
    1501             :                                  root->qual_security_level,
    1502             :                                  jtitem->qualscope,
    1503             :                                  NULL, NULL, NULL,
    1504             :                                  true, false, false,
    1505             :                                  NULL);
    1506             :     }
    1507       89506 :     else if (IsA(jtnode, JoinExpr))
    1508             :     {
    1509       89506 :         JoinExpr   *j = (JoinExpr *) jtnode;
    1510             :         Relids      ojscope;
    1511             :         List       *my_quals;
    1512             :         SpecialJoinInfo *sjinfo;
    1513             :         List      **postponed_oj_qual_list;
    1514             : 
    1515             :         /*
    1516             :          * Include lateral-referencing quals postponed from children in
    1517             :          * my_quals, so that they'll be handled properly in
    1518             :          * make_outerjoininfo.  (This is destructive to
    1519             :          * jtitem->lateral_clauses, but we won't use that again.)
    1520             :          */
    1521       89506 :         my_quals = list_concat(jtitem->lateral_clauses,
    1522       89506 :                                (List *) j->quals);
    1523             : 
    1524             :         /*
    1525             :          * For an OJ, form the SpecialJoinInfo now, so that we can pass it to
    1526             :          * distribute_qual_to_rels.  We must compute its ojscope too.
    1527             :          *
    1528             :          * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
    1529             :          * want ojscope = NULL for distribute_qual_to_rels.
    1530             :          */
    1531       89506 :         if (j->jointype != JOIN_INNER)
    1532             :         {
    1533       49212 :             sjinfo = make_outerjoininfo(root,
    1534             :                                         jtitem->left_rels,
    1535             :                                         jtitem->right_rels,
    1536             :                                         jtitem->inner_join_rels,
    1537             :                                         j->jointype,
    1538       49212 :                                         j->rtindex,
    1539             :                                         my_quals);
    1540       49212 :             jtitem->sjinfo = sjinfo;
    1541       49212 :             if (j->jointype == JOIN_SEMI)
    1542        2208 :                 ojscope = NULL;
    1543             :             else
    1544       47004 :                 ojscope = bms_union(sjinfo->min_lefthand,
    1545       47004 :                                     sjinfo->min_righthand);
    1546             :         }
    1547             :         else
    1548             :         {
    1549       40294 :             sjinfo = NULL;
    1550       40294 :             ojscope = NULL;
    1551             :         }
    1552             : 
    1553             :         /*
    1554             :          * If it's a left join with a join clause that is strict for the LHS,
    1555             :          * then we need to postpone handling of any non-degenerate join
    1556             :          * clauses, in case the join is able to commute with another left join
    1557             :          * per identity 3.  (Degenerate clauses need not be postponed, since
    1558             :          * they will drop down below this join anyway.)
    1559             :          */
    1560       89506 :         if (j->jointype == JOIN_LEFT && sjinfo->lhs_strict)
    1561             :         {
    1562       40672 :             postponed_oj_qual_list = &jtitem->oj_joinclauses;
    1563             : 
    1564             :             /*
    1565             :              * Add back any commutable lower OJ relids that were removed from
    1566             :              * min_lefthand or min_righthand, else the ojscope cross-check in
    1567             :              * distribute_qual_to_rels will complain.  Since we are postponing
    1568             :              * processing of non-degenerate clauses, this addition doesn't
    1569             :              * affect anything except that cross-check.  Real clause
    1570             :              * positioning decisions will be made later, when we revisit the
    1571             :              * postponed clauses.
    1572             :              */
    1573       40672 :             ojscope = bms_add_members(ojscope, sjinfo->commute_below_l);
    1574       40672 :             ojscope = bms_add_members(ojscope, sjinfo->commute_below_r);
    1575             :         }
    1576             :         else
    1577       48834 :             postponed_oj_qual_list = NULL;
    1578             : 
    1579             :         /* Process the JOIN's qual clauses */
    1580       89506 :         distribute_quals_to_rels(root, my_quals,
    1581             :                                  jtitem,
    1582             :                                  sjinfo,
    1583             :                                  root->qual_security_level,
    1584             :                                  jtitem->qualscope,
    1585             :                                  ojscope, jtitem->nonnullable_rels,
    1586             :                                  NULL,  /* incompatible_relids */
    1587             :                                  true,  /* allow_equivalence */
    1588             :                                  false, false,  /* not clones */
    1589             :                                  postponed_oj_qual_list);
    1590             : 
    1591             :         /* And add the SpecialJoinInfo to join_info_list */
    1592       89506 :         if (sjinfo)
    1593       49212 :             root->join_info_list = lappend(root->join_info_list, sjinfo);
    1594             :     }
    1595             :     else
    1596             :     {
    1597           0 :         elog(ERROR, "unrecognized node type: %d",
    1598             :              (int) nodeTag(jtnode));
    1599             :     }
    1600      866910 : }
    1601             : 
    1602             : /*
    1603             :  * process_security_barrier_quals
    1604             :  *    Transfer security-barrier quals into relation's baserestrictinfo list.
    1605             :  *
    1606             :  * The rewriter put any relevant security-barrier conditions into the RTE's
    1607             :  * securityQuals field, but it's now time to copy them into the rel's
    1608             :  * baserestrictinfo.
    1609             :  *
    1610             :  * In inheritance cases, we only consider quals attached to the parent rel
    1611             :  * here; they will be valid for all children too, so it's okay to consider
    1612             :  * them for purposes like equivalence class creation.  Quals attached to
    1613             :  * individual child rels will be dealt with during path creation.
    1614             :  */
    1615             : static void
    1616        2688 : process_security_barrier_quals(PlannerInfo *root,
    1617             :                                int rti, JoinTreeItem *jtitem)
    1618             : {
    1619        2688 :     RangeTblEntry *rte = root->simple_rte_array[rti];
    1620        2688 :     Index       security_level = 0;
    1621             :     ListCell   *lc;
    1622             : 
    1623             :     /*
    1624             :      * Each element of the securityQuals list has been preprocessed into an
    1625             :      * implicitly-ANDed list of clauses.  All the clauses in a given sublist
    1626             :      * should get the same security level, but successive sublists get higher
    1627             :      * levels.
    1628             :      */
    1629        5506 :     foreach(lc, rte->securityQuals)
    1630             :     {
    1631        2818 :         List       *qualset = (List *) lfirst(lc);
    1632             : 
    1633             :         /*
    1634             :          * We cheat to the extent of passing ojscope = qualscope rather than
    1635             :          * its more logical value of NULL.  The only effect this has is to
    1636             :          * force a Var-free qual to be evaluated at the rel rather than being
    1637             :          * pushed up to top of tree, which we don't want.
    1638             :          */
    1639        2818 :         distribute_quals_to_rels(root, qualset,
    1640             :                                  jtitem,
    1641             :                                  NULL,
    1642             :                                  security_level,
    1643             :                                  jtitem->qualscope,
    1644             :                                  jtitem->qualscope,
    1645             :                                  NULL,
    1646             :                                  NULL,
    1647             :                                  true,
    1648             :                                  false, false,  /* not clones */
    1649             :                                  NULL);
    1650        2818 :         security_level++;
    1651             :     }
    1652             : 
    1653             :     /* Assert that qual_security_level is higher than anything we just used */
    1654             :     Assert(security_level <= root->qual_security_level);
    1655        2688 : }
    1656             : 
    1657             : /*
    1658             :  * mark_rels_nulled_by_join
    1659             :  *    Fill RelOptInfo.nulling_relids of baserels nulled by this outer join
    1660             :  *
    1661             :  * Inputs:
    1662             :  *  ojrelid: RT index of the join RTE (must not be 0)
    1663             :  *  lower_rels: the base+OJ Relids syntactically below nullable side of join
    1664             :  */
    1665             : static void
    1666       45332 : mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
    1667             :                          Relids lower_rels)
    1668             : {
    1669       45332 :     int         relid = -1;
    1670             : 
    1671       93446 :     while ((relid = bms_next_member(lower_rels, relid)) > 0)
    1672             :     {
    1673       48114 :         RelOptInfo *rel = root->simple_rel_array[relid];
    1674             : 
    1675             :         /* ignore the RTE_GROUP RTE */
    1676       48114 :         if (relid == root->group_rtindex)
    1677           0 :             continue;
    1678             : 
    1679       48114 :         if (rel == NULL)        /* must be an outer join */
    1680             :         {
    1681             :             Assert(bms_is_member(relid, root->outer_join_rels));
    1682         794 :             continue;
    1683             :         }
    1684       47320 :         rel->nulling_relids = bms_add_member(rel->nulling_relids, ojrelid);
    1685             :     }
    1686       45332 : }
    1687             : 
    1688             : /*
    1689             :  * make_outerjoininfo
    1690             :  *    Build a SpecialJoinInfo for the current outer join
    1691             :  *
    1692             :  * Inputs:
    1693             :  *  left_rels: the base+OJ Relids syntactically on outer side of join
    1694             :  *  right_rels: the base+OJ Relids syntactically on inner side of join
    1695             :  *  inner_join_rels: base+OJ Relids participating in inner joins below this one
    1696             :  *  jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
    1697             :  *  ojrelid: RT index of the join RTE (0 for SEMI, which isn't in the RT list)
    1698             :  *  clause: the outer join's join condition (in implicit-AND format)
    1699             :  *
    1700             :  * The node should eventually be appended to root->join_info_list, but we
    1701             :  * do not do that here.
    1702             :  *
    1703             :  * Note: we assume that this function is invoked bottom-up, so that
    1704             :  * root->join_info_list already contains entries for all outer joins that are
    1705             :  * syntactically below this one.
    1706             :  */
    1707             : static SpecialJoinInfo *
    1708       49212 : make_outerjoininfo(PlannerInfo *root,
    1709             :                    Relids left_rels, Relids right_rels,
    1710             :                    Relids inner_join_rels,
    1711             :                    JoinType jointype, Index ojrelid,
    1712             :                    List *clause)
    1713             : {
    1714       49212 :     SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
    1715             :     Relids      clause_relids;
    1716             :     Relids      strict_relids;
    1717             :     Relids      min_lefthand;
    1718             :     Relids      min_righthand;
    1719             :     Relids      commute_below_l;
    1720             :     Relids      commute_below_r;
    1721             :     ListCell   *l;
    1722             : 
    1723             :     /*
    1724             :      * We should not see RIGHT JOIN here because left/right were switched
    1725             :      * earlier
    1726             :      */
    1727             :     Assert(jointype != JOIN_INNER);
    1728             :     Assert(jointype != JOIN_RIGHT);
    1729             : 
    1730             :     /*
    1731             :      * Presently the executor cannot support FOR [KEY] UPDATE/SHARE marking of
    1732             :      * rels appearing on the nullable side of an outer join. (It's somewhat
    1733             :      * unclear what that would mean, anyway: what should we mark when a result
    1734             :      * row is generated from no element of the nullable relation?)  So,
    1735             :      * complain if any nullable rel is FOR [KEY] UPDATE/SHARE.
    1736             :      *
    1737             :      * You might be wondering why this test isn't made far upstream in the
    1738             :      * parser.  It's because the parser hasn't got enough info --- consider
    1739             :      * FOR UPDATE applied to a view.  Only after rewriting and flattening do
    1740             :      * we know whether the view contains an outer join.
    1741             :      *
    1742             :      * We use the original RowMarkClause list here; the PlanRowMark list would
    1743             :      * list everything.
    1744             :      */
    1745       49256 :     foreach(l, root->parse->rowMarks)
    1746             :     {
    1747          44 :         RowMarkClause *rc = (RowMarkClause *) lfirst(l);
    1748             : 
    1749          44 :         if (bms_is_member(rc->rti, right_rels) ||
    1750           8 :             (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
    1751           0 :             ereport(ERROR,
    1752             :                     (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
    1753             :             /*------
    1754             :              translator: %s is a SQL row locking clause such as FOR UPDATE */
    1755             :                      errmsg("%s cannot be applied to the nullable side of an outer join",
    1756             :                             LCS_asString(rc->strength))));
    1757             :     }
    1758             : 
    1759       49212 :     sjinfo->syn_lefthand = left_rels;
    1760       49212 :     sjinfo->syn_righthand = right_rels;
    1761       49212 :     sjinfo->jointype = jointype;
    1762       49212 :     sjinfo->ojrelid = ojrelid;
    1763             :     /* these fields may get added to later: */
    1764       49212 :     sjinfo->commute_above_l = NULL;
    1765       49212 :     sjinfo->commute_above_r = NULL;
    1766       49212 :     sjinfo->commute_below_l = NULL;
    1767       49212 :     sjinfo->commute_below_r = NULL;
    1768             : 
    1769       49212 :     compute_semijoin_info(root, sjinfo, clause);
    1770             : 
    1771             :     /* If it's a full join, no need to be very smart */
    1772       49212 :     if (jointype == JOIN_FULL)
    1773             :     {
    1774        1028 :         sjinfo->min_lefthand = bms_copy(left_rels);
    1775        1028 :         sjinfo->min_righthand = bms_copy(right_rels);
    1776        1028 :         sjinfo->lhs_strict = false; /* don't care about this */
    1777        1028 :         return sjinfo;
    1778             :     }
    1779             : 
    1780             :     /*
    1781             :      * Retrieve all relids mentioned within the join clause.
    1782             :      */
    1783       48184 :     clause_relids = pull_varnos(root, (Node *) clause);
    1784             : 
    1785             :     /*
    1786             :      * For which relids is the clause strict, ie, it cannot succeed if the
    1787             :      * rel's columns are all NULL?
    1788             :      */
    1789       48184 :     strict_relids = find_nonnullable_rels((Node *) clause);
    1790             : 
    1791             :     /* Remember whether the clause is strict for any LHS relations */
    1792       48184 :     sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
    1793             : 
    1794             :     /*
    1795             :      * Required LHS always includes the LHS rels mentioned in the clause. We
    1796             :      * may have to add more rels based on lower outer joins; see below.
    1797             :      */
    1798       48184 :     min_lefthand = bms_intersect(clause_relids, left_rels);
    1799             : 
    1800             :     /*
    1801             :      * Similarly for required RHS.  But here, we must also include any lower
    1802             :      * inner joins, to ensure we don't try to commute with any of them.
    1803             :      */
    1804       48184 :     min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
    1805             :                                     right_rels);
    1806             : 
    1807             :     /*
    1808             :      * Now check previous outer joins for ordering restrictions.
    1809             :      *
    1810             :      * commute_below_l and commute_below_r accumulate the relids of lower
    1811             :      * outer joins that we think this one can commute with.  These decisions
    1812             :      * are just tentative within this loop, since we might find an
    1813             :      * intermediate outer join that prevents commutation.  Surviving relids
    1814             :      * will get merged into the SpecialJoinInfo structs afterwards.
    1815             :      */
    1816       48184 :     commute_below_l = commute_below_r = NULL;
    1817       64282 :     foreach(l, root->join_info_list)
    1818             :     {
    1819       16098 :         SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
    1820             :         bool        have_unsafe_phvs;
    1821             : 
    1822             :         /*
    1823             :          * A full join is an optimization barrier: we can't associate into or
    1824             :          * out of it.  Hence, if it overlaps either LHS or RHS of the current
    1825             :          * rel, expand that side's min relset to cover the whole full join.
    1826             :          */
    1827       16098 :         if (otherinfo->jointype == JOIN_FULL)
    1828             :         {
    1829             :             Assert(otherinfo->ojrelid != 0);
    1830          94 :             if (bms_overlap(left_rels, otherinfo->syn_lefthand) ||
    1831          30 :                 bms_overlap(left_rels, otherinfo->syn_righthand))
    1832             :             {
    1833          34 :                 min_lefthand = bms_add_members(min_lefthand,
    1834          34 :                                                otherinfo->syn_lefthand);
    1835          34 :                 min_lefthand = bms_add_members(min_lefthand,
    1836          34 :                                                otherinfo->syn_righthand);
    1837          34 :                 min_lefthand = bms_add_member(min_lefthand,
    1838          34 :                                               otherinfo->ojrelid);
    1839             :             }
    1840          98 :             if (bms_overlap(right_rels, otherinfo->syn_lefthand) ||
    1841          34 :                 bms_overlap(right_rels, otherinfo->syn_righthand))
    1842             :             {
    1843          30 :                 min_righthand = bms_add_members(min_righthand,
    1844          30 :                                                 otherinfo->syn_lefthand);
    1845          30 :                 min_righthand = bms_add_members(min_righthand,
    1846          30 :                                                 otherinfo->syn_righthand);
    1847          30 :                 min_righthand = bms_add_member(min_righthand,
    1848          30 :                                                otherinfo->ojrelid);
    1849             :             }
    1850             :             /* Needn't do anything else with the full join */
    1851          64 :             continue;
    1852             :         }
    1853             : 
    1854             :         /*
    1855             :          * If our join condition contains any PlaceHolderVars that need to be
    1856             :          * evaluated above the lower OJ, then we can't commute with it.
    1857             :          */
    1858       16034 :         if (otherinfo->ojrelid != 0)
    1859             :             have_unsafe_phvs =
    1860       15692 :                 contain_placeholder_references_to(root,
    1861             :                                                   (Node *) clause,
    1862       15692 :                                                   otherinfo->ojrelid);
    1863             :         else
    1864         342 :             have_unsafe_phvs = false;
    1865             : 
    1866             :         /*
    1867             :          * For a lower OJ in our LHS, if our join condition uses the lower
    1868             :          * join's RHS and is not strict for that rel, we must preserve the
    1869             :          * ordering of the two OJs, so add lower OJ's full syntactic relset to
    1870             :          * min_lefthand.  (We must use its full syntactic relset, not just its
    1871             :          * min_lefthand + min_righthand.  This is because there might be other
    1872             :          * OJs below this one that this one can commute with, but we cannot
    1873             :          * commute with them if we don't with this one.)  Also, if we have
    1874             :          * unsafe PHVs or the current join is a semijoin or antijoin, we must
    1875             :          * preserve ordering regardless of strictness.
    1876             :          *
    1877             :          * Note: I believe we have to insist on being strict for at least one
    1878             :          * rel in the lower OJ's min_righthand, not its whole syn_righthand.
    1879             :          *
    1880             :          * When we don't need to preserve ordering, check to see if outer join
    1881             :          * identity 3 applies, and if so, remove the lower OJ's ojrelid from
    1882             :          * our min_lefthand so that commutation is allowed.
    1883             :          */
    1884       16034 :         if (bms_overlap(left_rels, otherinfo->syn_righthand))
    1885             :         {
    1886       15164 :             if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
    1887        4596 :                 (have_unsafe_phvs ||
    1888        4596 :                  jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
    1889        4596 :                  !bms_overlap(strict_relids, otherinfo->min_righthand)))
    1890             :             {
    1891             :                 /* Preserve ordering */
    1892          42 :                 min_lefthand = bms_add_members(min_lefthand,
    1893          42 :                                                otherinfo->syn_lefthand);
    1894          42 :                 min_lefthand = bms_add_members(min_lefthand,
    1895          42 :                                                otherinfo->syn_righthand);
    1896          42 :                 if (otherinfo->ojrelid != 0)
    1897          42 :                     min_lefthand = bms_add_member(min_lefthand,
    1898          42 :                                                   otherinfo->ojrelid);
    1899             :             }
    1900       15122 :             else if (jointype == JOIN_LEFT &&
    1901       29044 :                      otherinfo->jointype == JOIN_LEFT &&
    1902       14520 :                      bms_overlap(strict_relids, otherinfo->min_righthand) &&
    1903        4566 :                      !bms_overlap(clause_relids, otherinfo->syn_lefthand))
    1904             :             {
    1905             :                 /* Identity 3 applies, so remove the ordering restriction */
    1906        4506 :                 min_lefthand = bms_del_member(min_lefthand, otherinfo->ojrelid);
    1907             :                 /* Record the (still tentative) commutability relationship */
    1908             :                 commute_below_l =
    1909        4506 :                     bms_add_member(commute_below_l, otherinfo->ojrelid);
    1910             :             }
    1911             :         }
    1912             : 
    1913             :         /*
    1914             :          * For a lower OJ in our RHS, if our join condition does not use the
    1915             :          * lower join's RHS and the lower OJ's join condition is strict, we
    1916             :          * can interchange the ordering of the two OJs; otherwise we must add
    1917             :          * the lower OJ's full syntactic relset to min_righthand.
    1918             :          *
    1919             :          * Also, if our join condition does not use the lower join's LHS
    1920             :          * either, force the ordering to be preserved.  Otherwise we can end
    1921             :          * up with SpecialJoinInfos with identical min_righthands, which can
    1922             :          * confuse join_is_legal (see discussion in backend/optimizer/README).
    1923             :          *
    1924             :          * Also, we must preserve ordering anyway if we have unsafe PHVs, or
    1925             :          * if either this join or the lower OJ is a semijoin or antijoin.
    1926             :          *
    1927             :          * When we don't need to preserve ordering, check to see if outer join
    1928             :          * identity 3 applies, and if so, remove the lower OJ's ojrelid from
    1929             :          * our min_righthand so that commutation is allowed.
    1930             :          */
    1931       16034 :         if (bms_overlap(right_rels, otherinfo->syn_righthand))
    1932             :         {
    1933         784 :             if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
    1934         736 :                 !bms_overlap(clause_relids, otherinfo->min_lefthand) ||
    1935         424 :                 have_unsafe_phvs ||
    1936         334 :                 jointype == JOIN_SEMI ||
    1937         328 :                 jointype == JOIN_ANTI ||
    1938         328 :                 otherinfo->jointype == JOIN_SEMI ||
    1939         268 :                 otherinfo->jointype == JOIN_ANTI ||
    1940         268 :                 !otherinfo->lhs_strict)
    1941             :             {
    1942             :                 /* Preserve ordering */
    1943         540 :                 min_righthand = bms_add_members(min_righthand,
    1944         540 :                                                 otherinfo->syn_lefthand);
    1945         540 :                 min_righthand = bms_add_members(min_righthand,
    1946         540 :                                                 otherinfo->syn_righthand);
    1947         540 :                 if (otherinfo->ojrelid != 0)
    1948         390 :                     min_righthand = bms_add_member(min_righthand,
    1949         390 :                                                    otherinfo->ojrelid);
    1950             :             }
    1951         244 :             else if (jointype == JOIN_LEFT &&
    1952         244 :                      otherinfo->jointype == JOIN_LEFT &&
    1953         244 :                      otherinfo->lhs_strict)
    1954             :             {
    1955             :                 /* Identity 3 applies, so remove the ordering restriction */
    1956         244 :                 min_righthand = bms_del_member(min_righthand,
    1957         244 :                                                otherinfo->ojrelid);
    1958             :                 /* Record the (still tentative) commutability relationship */
    1959             :                 commute_below_r =
    1960         244 :                     bms_add_member(commute_below_r, otherinfo->ojrelid);
    1961             :             }
    1962             :         }
    1963             :     }
    1964             : 
    1965             :     /*
    1966             :      * Examine PlaceHolderVars.  If a PHV is supposed to be evaluated within
    1967             :      * this join's nullable side, then ensure that min_righthand contains the
    1968             :      * full eval_at set of the PHV.  This ensures that the PHV actually can be
    1969             :      * evaluated within the RHS.  Note that this works only because we should
    1970             :      * already have determined the final eval_at level for any PHV
    1971             :      * syntactically within this join.
    1972             :      */
    1973       49572 :     foreach(l, root->placeholder_list)
    1974             :     {
    1975        1388 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
    1976        1388 :         Relids      ph_syn_level = phinfo->ph_var->phrels;
    1977             : 
    1978             :         /* Ignore placeholder if it didn't syntactically come from RHS */
    1979        1388 :         if (!bms_is_subset(ph_syn_level, right_rels))
    1980         496 :             continue;
    1981             : 
    1982             :         /* Else, prevent join from being formed before we eval the PHV */
    1983         892 :         min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
    1984             :     }
    1985             : 
    1986             :     /*
    1987             :      * If we found nothing to put in min_lefthand, punt and make it the full
    1988             :      * LHS, to avoid having an empty min_lefthand which will confuse later
    1989             :      * processing. (We don't try to be smart about such cases, just correct.)
    1990             :      * Likewise for min_righthand.
    1991             :      */
    1992       48184 :     if (bms_is_empty(min_lefthand))
    1993        1366 :         min_lefthand = bms_copy(left_rels);
    1994       48184 :     if (bms_is_empty(min_righthand))
    1995         500 :         min_righthand = bms_copy(right_rels);
    1996             : 
    1997             :     /* Now they'd better be nonempty */
    1998             :     Assert(!bms_is_empty(min_lefthand));
    1999             :     Assert(!bms_is_empty(min_righthand));
    2000             :     /* Shouldn't overlap either */
    2001             :     Assert(!bms_overlap(min_lefthand, min_righthand));
    2002             : 
    2003       48184 :     sjinfo->min_lefthand = min_lefthand;
    2004       48184 :     sjinfo->min_righthand = min_righthand;
    2005             : 
    2006             :     /*
    2007             :      * Now that we've identified the correct min_lefthand and min_righthand,
    2008             :      * any commute_below_l or commute_below_r relids that have not gotten
    2009             :      * added back into those sets (due to intervening outer joins) are indeed
    2010             :      * commutable with this one.
    2011             :      *
    2012             :      * First, delete any subsequently-added-back relids (this is easier than
    2013             :      * maintaining commute_below_l/r precisely through all the above).
    2014             :      */
    2015       48184 :     commute_below_l = bms_del_members(commute_below_l, min_lefthand);
    2016       48184 :     commute_below_r = bms_del_members(commute_below_r, min_righthand);
    2017             : 
    2018             :     /* Anything left? */
    2019       48184 :     if (commute_below_l || commute_below_r)
    2020             :     {
    2021             :         /* Yup, so we must update the derived data in the SpecialJoinInfos */
    2022        4672 :         sjinfo->commute_below_l = commute_below_l;
    2023        4672 :         sjinfo->commute_below_r = commute_below_r;
    2024        9864 :         foreach(l, root->join_info_list)
    2025             :         {
    2026        5192 :             SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
    2027             : 
    2028        5192 :             if (bms_is_member(otherinfo->ojrelid, commute_below_l))
    2029        4506 :                 otherinfo->commute_above_l =
    2030        4506 :                     bms_add_member(otherinfo->commute_above_l, ojrelid);
    2031         686 :             else if (bms_is_member(otherinfo->ojrelid, commute_below_r))
    2032         214 :                 otherinfo->commute_above_r =
    2033         214 :                     bms_add_member(otherinfo->commute_above_r, ojrelid);
    2034             :         }
    2035             :     }
    2036             : 
    2037       48184 :     return sjinfo;
    2038             : }
    2039             : 
    2040             : /*
    2041             :  * compute_semijoin_info
    2042             :  *    Fill semijoin-related fields of a new SpecialJoinInfo
    2043             :  *
    2044             :  * Note: this relies on only the jointype and syn_righthand fields of the
    2045             :  * SpecialJoinInfo; the rest may not be set yet.
    2046             :  */
    2047             : static void
    2048       49212 : compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause)
    2049             : {
    2050             :     List       *semi_operators;
    2051             :     List       *semi_rhs_exprs;
    2052             :     bool        all_btree;
    2053             :     bool        all_hash;
    2054             :     ListCell   *lc;
    2055             : 
    2056             :     /* Initialize semijoin-related fields in case we can't unique-ify */
    2057       49212 :     sjinfo->semi_can_btree = false;
    2058       49212 :     sjinfo->semi_can_hash = false;
    2059       49212 :     sjinfo->semi_operators = NIL;
    2060       49212 :     sjinfo->semi_rhs_exprs = NIL;
    2061             : 
    2062             :     /* Nothing more to do if it's not a semijoin */
    2063       49212 :     if (sjinfo->jointype != JOIN_SEMI)
    2064       47004 :         return;
    2065             : 
    2066             :     /*
    2067             :      * Look to see whether the semijoin's join quals consist of AND'ed
    2068             :      * equality operators, with (only) RHS variables on only one side of each
    2069             :      * one.  If so, we can figure out how to enforce uniqueness for the RHS.
    2070             :      *
    2071             :      * Note that the input clause list is the list of quals that are
    2072             :      * *syntactically* associated with the semijoin, which in practice means
    2073             :      * the synthesized comparison list for an IN or the WHERE of an EXISTS.
    2074             :      * Particularly in the latter case, it might contain clauses that aren't
    2075             :      * *semantically* associated with the join, but refer to just one side or
    2076             :      * the other.  We can ignore such clauses here, as they will just drop
    2077             :      * down to be processed within one side or the other.  (It is okay to
    2078             :      * consider only the syntactically-associated clauses here because for a
    2079             :      * semijoin, no higher-level quals could refer to the RHS, and so there
    2080             :      * can be no other quals that are semantically associated with this join.
    2081             :      * We do things this way because it is useful to have the set of potential
    2082             :      * unique-ification expressions before we can extract the list of quals
    2083             :      * that are actually semantically associated with the particular join.)
    2084             :      *
    2085             :      * Note that the semi_operators list consists of the joinqual operators
    2086             :      * themselves (but commuted if needed to put the RHS value on the right).
    2087             :      * These could be cross-type operators, in which case the operator
    2088             :      * actually needed for uniqueness is a related single-type operator. We
    2089             :      * assume here that that operator will be available from the btree or hash
    2090             :      * opclass when the time comes ... if not, create_unique_plan() will fail.
    2091             :      */
    2092        2208 :     semi_operators = NIL;
    2093        2208 :     semi_rhs_exprs = NIL;
    2094        2208 :     all_btree = true;
    2095        2208 :     all_hash = enable_hashagg;  /* don't consider hash if not enabled */
    2096        4696 :     foreach(lc, clause)
    2097             :     {
    2098        2590 :         OpExpr     *op = (OpExpr *) lfirst(lc);
    2099             :         Oid         opno;
    2100             :         Node       *left_expr;
    2101             :         Node       *right_expr;
    2102             :         Relids      left_varnos;
    2103             :         Relids      right_varnos;
    2104             :         Relids      all_varnos;
    2105             :         Oid         opinputtype;
    2106             : 
    2107             :         /* Is it a binary opclause? */
    2108        5072 :         if (!IsA(op, OpExpr) ||
    2109        2482 :             list_length(op->args) != 2)
    2110             :         {
    2111             :             /* No, but does it reference both sides? */
    2112         108 :             all_varnos = pull_varnos(root, (Node *) op);
    2113         204 :             if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
    2114          96 :                 bms_is_subset(all_varnos, sjinfo->syn_righthand))
    2115             :             {
    2116             :                 /*
    2117             :                  * Clause refers to only one rel, so ignore it --- unless it
    2118             :                  * contains volatile functions, in which case we'd better
    2119             :                  * punt.
    2120             :                  */
    2121          96 :                 if (contain_volatile_functions((Node *) op))
    2122         102 :                     return;
    2123          96 :                 continue;
    2124             :             }
    2125             :             /* Non-operator clause referencing both sides, must punt */
    2126          12 :             return;
    2127             :         }
    2128             : 
    2129             :         /* Extract data from binary opclause */
    2130        2482 :         opno = op->opno;
    2131        2482 :         left_expr = linitial(op->args);
    2132        2482 :         right_expr = lsecond(op->args);
    2133        2482 :         left_varnos = pull_varnos(root, left_expr);
    2134        2482 :         right_varnos = pull_varnos(root, right_expr);
    2135        2482 :         all_varnos = bms_union(left_varnos, right_varnos);
    2136        2482 :         opinputtype = exprType(left_expr);
    2137             : 
    2138             :         /* Does it reference both sides? */
    2139        4956 :         if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
    2140        2474 :             bms_is_subset(all_varnos, sjinfo->syn_righthand))
    2141             :         {
    2142             :             /*
    2143             :              * Clause refers to only one rel, so ignore it --- unless it
    2144             :              * contains volatile functions, in which case we'd better punt.
    2145             :              */
    2146          82 :             if (contain_volatile_functions((Node *) op))
    2147           0 :                 return;
    2148          82 :             continue;
    2149             :         }
    2150             : 
    2151             :         /* check rel membership of arguments */
    2152        4800 :         if (!bms_is_empty(right_varnos) &&
    2153        2400 :             bms_is_subset(right_varnos, sjinfo->syn_righthand) &&
    2154        1946 :             !bms_overlap(left_varnos, sjinfo->syn_righthand))
    2155             :         {
    2156             :             /* typical case, right_expr is RHS variable */
    2157             :         }
    2158         908 :         else if (!bms_is_empty(left_varnos) &&
    2159         454 :                  bms_is_subset(left_varnos, sjinfo->syn_righthand) &&
    2160         448 :                  !bms_overlap(right_varnos, sjinfo->syn_righthand))
    2161             :         {
    2162             :             /* flipped case, left_expr is RHS variable */
    2163         448 :             opno = get_commutator(opno);
    2164         448 :             if (!OidIsValid(opno))
    2165           0 :                 return;
    2166         448 :             right_expr = left_expr;
    2167             :         }
    2168             :         else
    2169             :         {
    2170             :             /* mixed membership of args, punt */
    2171           6 :             return;
    2172             :         }
    2173             : 
    2174             :         /* all operators must be btree equality or hash equality */
    2175        2394 :         if (all_btree)
    2176             :         {
    2177             :             /* oprcanmerge is considered a hint... */
    2178        4704 :             if (!op_mergejoinable(opno, opinputtype) ||
    2179        2310 :                 get_mergejoin_opfamilies(opno) == NIL)
    2180          84 :                 all_btree = false;
    2181             :         }
    2182        2394 :         if (all_hash)
    2183             :         {
    2184             :             /* ... but oprcanhash had better be correct */
    2185        2322 :             if (!op_hashjoinable(opno, opinputtype))
    2186          84 :                 all_hash = false;
    2187             :         }
    2188        2394 :         if (!(all_btree || all_hash))
    2189          84 :             return;
    2190             : 
    2191             :         /* so far so good, keep building lists */
    2192        2310 :         semi_operators = lappend_oid(semi_operators, opno);
    2193        2310 :         semi_rhs_exprs = lappend(semi_rhs_exprs, copyObject(right_expr));
    2194             :     }
    2195             : 
    2196             :     /* Punt if we didn't find at least one column to unique-ify */
    2197        2106 :     if (semi_rhs_exprs == NIL)
    2198          12 :         return;
    2199             : 
    2200             :     /*
    2201             :      * The expressions we'd need to unique-ify mustn't be volatile.
    2202             :      */
    2203        2094 :     if (contain_volatile_functions((Node *) semi_rhs_exprs))
    2204           0 :         return;
    2205             : 
    2206             :     /*
    2207             :      * If we get here, we can unique-ify the semijoin's RHS using at least one
    2208             :      * of sorting and hashing.  Save the information about how to do that.
    2209             :      */
    2210        2094 :     sjinfo->semi_can_btree = all_btree;
    2211        2094 :     sjinfo->semi_can_hash = all_hash;
    2212        2094 :     sjinfo->semi_operators = semi_operators;
    2213        2094 :     sjinfo->semi_rhs_exprs = semi_rhs_exprs;
    2214             : }
    2215             : 
    2216             : /*
    2217             :  * deconstruct_distribute_oj_quals
    2218             :  *    Adjust LEFT JOIN quals to be suitable for commuted-left-join cases,
    2219             :  *    then push them into the joinqual lists and EquivalenceClass structures.
    2220             :  *
    2221             :  * This runs immediately after we've completed the deconstruct_distribute scan.
    2222             :  * jtitems contains all the JoinTreeItems (in depth-first order), and jtitem
    2223             :  * is one that has postponed oj_joinclauses to deal with.
    2224             :  */
    2225             : static void
    2226       40672 : deconstruct_distribute_oj_quals(PlannerInfo *root,
    2227             :                                 List *jtitems,
    2228             :                                 JoinTreeItem *jtitem)
    2229             : {
    2230       40672 :     SpecialJoinInfo *sjinfo = jtitem->sjinfo;
    2231             :     Relids      qualscope,
    2232             :                 ojscope,
    2233             :                 nonnullable_rels;
    2234             : 
    2235             :     /* Recompute syntactic and semantic scopes of this left join */
    2236       40672 :     qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
    2237       40672 :     qualscope = bms_add_member(qualscope, sjinfo->ojrelid);
    2238       40672 :     ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
    2239       40672 :     nonnullable_rels = sjinfo->syn_lefthand;
    2240             : 
    2241             :     /*
    2242             :      * If this join can commute with any other ones per outer-join identity 3,
    2243             :      * and it is the one providing the join clause with flexible semantics,
    2244             :      * then we have to generate variants of the join clause with different
    2245             :      * nullingrels labeling.  Otherwise, just push out the postponed clause
    2246             :      * as-is.
    2247             :      */
    2248             :     Assert(sjinfo->lhs_strict); /* else we shouldn't be here */
    2249       40672 :     if (sjinfo->commute_above_r || sjinfo->commute_below_l)
    2250        4684 :     {
    2251             :         Relids      joins_above;
    2252             :         Relids      joins_below;
    2253             :         Relids      incompatible_joins;
    2254             :         Relids      joins_so_far;
    2255             :         List       *quals;
    2256             :         int         save_last_rinfo_serial;
    2257             :         ListCell   *lc;
    2258             : 
    2259             :         /* Identify the outer joins this one commutes with */
    2260        4684 :         joins_above = sjinfo->commute_above_r;
    2261        4684 :         joins_below = sjinfo->commute_below_l;
    2262             : 
    2263             :         /*
    2264             :          * Generate qual variants with different sets of nullingrels bits.
    2265             :          *
    2266             :          * We only need bit-sets that correspond to the successively less
    2267             :          * deeply syntactically-nested subsets of this join and its
    2268             :          * commutators.  That's true first because obviously only those forms
    2269             :          * of the Vars and PHVs could appear elsewhere in the query, and
    2270             :          * second because the outer join identities do not provide a way to
    2271             :          * re-order such joins in a way that would require different marking.
    2272             :          * (That is, while the current join may commute with several others,
    2273             :          * none of those others can commute with each other.)  To visit the
    2274             :          * interesting joins in syntactic nesting order, we rely on the
    2275             :          * jtitems list to be ordered that way.
    2276             :          *
    2277             :          * We first strip out all the nullingrels bits corresponding to
    2278             :          * commuting joins below this one, and then successively put them back
    2279             :          * as we crawl up the join stack.
    2280             :          */
    2281        4684 :         quals = jtitem->oj_joinclauses;
    2282        4684 :         if (!bms_is_empty(joins_below))
    2283        4470 :             quals = (List *) remove_nulling_relids((Node *) quals,
    2284             :                                                    joins_below,
    2285             :                                                    NULL);
    2286             : 
    2287             :         /*
    2288             :          * We'll need to mark the lower versions of the quals as not safe to
    2289             :          * apply above not-yet-processed joins of the stack.  This prevents
    2290             :          * possibly applying a cloned qual at the wrong join level.
    2291             :          */
    2292        4684 :         incompatible_joins = bms_union(joins_below, joins_above);
    2293        4684 :         incompatible_joins = bms_add_member(incompatible_joins,
    2294        4684 :                                             sjinfo->ojrelid);
    2295             : 
    2296             :         /*
    2297             :          * Each time we produce RestrictInfo(s) from these quals, reset the
    2298             :          * last_rinfo_serial counter, so that the RestrictInfos for the "same"
    2299             :          * qual condition get identical serial numbers.  (This relies on the
    2300             :          * fact that we're not changing the qual list in any way that'd affect
    2301             :          * the number of RestrictInfos built from it.) This'll allow us to
    2302             :          * detect duplicative qual usage later.
    2303             :          */
    2304        4684 :         save_last_rinfo_serial = root->last_rinfo_serial;
    2305             : 
    2306        4684 :         joins_so_far = NULL;
    2307       39960 :         foreach(lc, jtitems)
    2308             :         {
    2309       35276 :             JoinTreeItem *otherjtitem = (JoinTreeItem *) lfirst(lc);
    2310       35276 :             SpecialJoinInfo *othersj = otherjtitem->sjinfo;
    2311       35276 :             bool        below_sjinfo = false;
    2312       35276 :             bool        above_sjinfo = false;
    2313             :             Relids      this_qualscope;
    2314             :             Relids      this_ojscope;
    2315             :             bool        allow_equivalence,
    2316             :                         has_clone,
    2317             :                         is_clone;
    2318             : 
    2319       35276 :             if (othersj == NULL)
    2320       25144 :                 continue;       /* not an outer-join item, ignore */
    2321             : 
    2322       10132 :             if (bms_is_member(othersj->ojrelid, joins_below))
    2323             :             {
    2324             :                 /* othersj commutes with sjinfo from below left */
    2325        4506 :                 below_sjinfo = true;
    2326             :             }
    2327        5626 :             else if (othersj == sjinfo)
    2328             :             {
    2329             :                 /* found our join in syntactic order */
    2330             :                 Assert(bms_equal(joins_so_far, joins_below));
    2331             :             }
    2332         942 :             else if (bms_is_member(othersj->ojrelid, joins_above))
    2333             :             {
    2334             :                 /* othersj commutes with sjinfo from above */
    2335         214 :                 above_sjinfo = true;
    2336             :             }
    2337             :             else
    2338             :             {
    2339             :                 /* othersj is not relevant, ignore */
    2340         728 :                 continue;
    2341             :             }
    2342             : 
    2343             :             /* Reset serial counter for this version of the quals */
    2344        9404 :             root->last_rinfo_serial = save_last_rinfo_serial;
    2345             : 
    2346             :             /*
    2347             :              * When we are looking at joins above sjinfo, we are envisioning
    2348             :              * pushing sjinfo to above othersj, so add othersj's nulling bit
    2349             :              * before distributing the quals.  We should add it to Vars coming
    2350             :              * from the current join's LHS: we want to transform the second
    2351             :              * form of OJ identity 3 to the first form, in which Vars of
    2352             :              * relation B will appear nulled by the syntactically-upper OJ
    2353             :              * within the Pbc clause, but those of relation C will not.  (In
    2354             :              * the notation used by optimizer/README, we're converting a qual
    2355             :              * of the form Pbc to Pb*c.)  Of course, we must also remove that
    2356             :              * bit from the incompatible_joins value, else we'll make a qual
    2357             :              * that can't be placed anywhere.
    2358             :              */
    2359        9404 :             if (above_sjinfo)
    2360             :             {
    2361             :                 quals = (List *)
    2362         214 :                     add_nulling_relids((Node *) quals,
    2363         214 :                                        sjinfo->syn_lefthand,
    2364         214 :                                        bms_make_singleton(othersj->ojrelid));
    2365         214 :                 incompatible_joins = bms_del_member(incompatible_joins,
    2366         214 :                                                     othersj->ojrelid);
    2367             :             }
    2368             : 
    2369             :             /* Compute qualscope and ojscope for this join level */
    2370        9404 :             this_qualscope = bms_union(qualscope, joins_so_far);
    2371        9404 :             this_ojscope = bms_union(ojscope, joins_so_far);
    2372        9404 :             if (above_sjinfo)
    2373             :             {
    2374             :                 /* othersj is not yet in joins_so_far, but we need it */
    2375         214 :                 this_qualscope = bms_add_member(this_qualscope,
    2376         214 :                                                 othersj->ojrelid);
    2377         214 :                 this_ojscope = bms_add_member(this_ojscope,
    2378         214 :                                               othersj->ojrelid);
    2379             :                 /* sjinfo is in joins_so_far, and we don't want it */
    2380         214 :                 this_ojscope = bms_del_member(this_ojscope,
    2381         214 :                                               sjinfo->ojrelid);
    2382             :             }
    2383             : 
    2384             :             /*
    2385             :              * We generate EquivalenceClasses only from the first form of the
    2386             :              * quals, with the fewest nullingrels bits set.  An EC made from
    2387             :              * this version of the quals can be useful below the outer-join
    2388             :              * nest, whereas versions with some nullingrels bits set would not
    2389             :              * be.  We cannot generate ECs from more than one version, or
    2390             :              * we'll make nonsensical conclusions that Vars with nullingrels
    2391             :              * bits set are equal to their versions without.  Fortunately,
    2392             :              * such ECs wouldn't be very useful anyway, because they'd equate
    2393             :              * values not observable outside the join nest.  (See
    2394             :              * optimizer/README.)
    2395             :              *
    2396             :              * The first form of the quals is also the only one marked as
    2397             :              * has_clone rather than is_clone.
    2398             :              */
    2399        9404 :             allow_equivalence = (joins_so_far == NULL);
    2400        9404 :             has_clone = allow_equivalence;
    2401        9404 :             is_clone = !has_clone;
    2402             : 
    2403        9404 :             distribute_quals_to_rels(root, quals,
    2404             :                                      otherjtitem,
    2405             :                                      sjinfo,
    2406             :                                      root->qual_security_level,
    2407             :                                      this_qualscope,
    2408             :                                      this_ojscope, nonnullable_rels,
    2409             :                                      bms_copy(incompatible_joins),
    2410             :                                      allow_equivalence,
    2411             :                                      has_clone,
    2412             :                                      is_clone,
    2413             :                                      NULL); /* no more postponement */
    2414             : 
    2415             :             /*
    2416             :              * Adjust qual nulling bits for next level up, if needed.  We
    2417             :              * don't want to put sjinfo's own bit in at all, and if we're
    2418             :              * above sjinfo then we did it already.  Here, we should mark all
    2419             :              * Vars coming from the lower join's RHS.  (Again, we are
    2420             :              * converting a qual of the form Pbc to Pb*c, but now we are
    2421             :              * putting back bits that were there in the parser output and were
    2422             :              * temporarily stripped above.)  Update incompatible_joins too.
    2423             :              */
    2424        9404 :             if (below_sjinfo)
    2425             :             {
    2426             :                 quals = (List *)
    2427        4506 :                     add_nulling_relids((Node *) quals,
    2428        4506 :                                        othersj->syn_righthand,
    2429        4506 :                                        bms_make_singleton(othersj->ojrelid));
    2430        4506 :                 incompatible_joins = bms_del_member(incompatible_joins,
    2431        4506 :                                                     othersj->ojrelid);
    2432             :             }
    2433             : 
    2434             :             /* ... and track joins processed so far */
    2435        9404 :             joins_so_far = bms_add_member(joins_so_far, othersj->ojrelid);
    2436             :         }
    2437             :     }
    2438             :     else
    2439             :     {
    2440             :         /* No commutation possible, just process the postponed clauses */
    2441       35988 :         distribute_quals_to_rels(root, jtitem->oj_joinclauses,
    2442             :                                  jtitem,
    2443             :                                  sjinfo,
    2444             :                                  root->qual_security_level,
    2445             :                                  qualscope,
    2446             :                                  ojscope, nonnullable_rels,
    2447             :                                  NULL,  /* incompatible_relids */
    2448             :                                  true,  /* allow_equivalence */
    2449             :                                  false, false,  /* not clones */
    2450             :                                  NULL); /* no more postponement */
    2451             :     }
    2452       40672 : }
    2453             : 
    2454             : 
    2455             : /*****************************************************************************
    2456             :  *
    2457             :  *    QUALIFICATIONS
    2458             :  *
    2459             :  *****************************************************************************/
    2460             : 
    2461             : /*
    2462             :  * distribute_quals_to_rels
    2463             :  *    Convenience routine to apply distribute_qual_to_rels to each element
    2464             :  *    of an AND'ed list of clauses.
    2465             :  */
    2466             : static void
    2467      785264 : distribute_quals_to_rels(PlannerInfo *root, List *clauses,
    2468             :                          JoinTreeItem *jtitem,
    2469             :                          SpecialJoinInfo *sjinfo,
    2470             :                          Index security_level,
    2471             :                          Relids qualscope,
    2472             :                          Relids ojscope,
    2473             :                          Relids outerjoin_nonnullable,
    2474             :                          Relids incompatible_relids,
    2475             :                          bool allow_equivalence,
    2476             :                          bool has_clone,
    2477             :                          bool is_clone,
    2478             :                          List **postponed_oj_qual_list)
    2479             : {
    2480             :     ListCell   *lc;
    2481             : 
    2482     1347622 :     foreach(lc, clauses)
    2483             :     {
    2484      562358 :         Node       *clause = (Node *) lfirst(lc);
    2485             : 
    2486      562358 :         distribute_qual_to_rels(root, clause,
    2487             :                                 jtitem,
    2488             :                                 sjinfo,
    2489             :                                 security_level,
    2490             :                                 qualscope,
    2491             :                                 ojscope,
    2492             :                                 outerjoin_nonnullable,
    2493             :                                 incompatible_relids,
    2494             :                                 allow_equivalence,
    2495             :                                 has_clone,
    2496             :                                 is_clone,
    2497             :                                 postponed_oj_qual_list);
    2498             :     }
    2499      785264 : }
    2500             : 
    2501             : /*
    2502             :  * distribute_qual_to_rels
    2503             :  *    Add clause information to either the baserestrictinfo or joininfo list
    2504             :  *    (depending on whether the clause is a join) of each base relation
    2505             :  *    mentioned in the clause.  A RestrictInfo node is created and added to
    2506             :  *    the appropriate list for each rel.  Alternatively, if the clause uses a
    2507             :  *    mergejoinable operator, enter its left- and right-side expressions into
    2508             :  *    the query's EquivalenceClasses.
    2509             :  *
    2510             :  * In some cases, quals will be added to parent jtitems' lateral_clauses
    2511             :  * or to postponed_oj_qual_list instead of being processed right away.
    2512             :  * These will be dealt with in later calls of deconstruct_distribute.
    2513             :  *
    2514             :  * 'clause': the qual clause to be distributed
    2515             :  * 'jtitem': the JoinTreeItem for the containing jointree node
    2516             :  * 'sjinfo': join's SpecialJoinInfo (NULL for an inner join or WHERE clause)
    2517             :  * 'security_level': security_level to assign to the qual
    2518             :  * 'qualscope': set of base+OJ rels the qual's syntactic scope covers
    2519             :  * 'ojscope': NULL if not an outer-join qual, else the minimum set of base+OJ
    2520             :  *      rels needed to form this join
    2521             :  * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
    2522             :  *      base+OJ rels appearing on the outer (nonnullable) side of the join
    2523             :  *      (for FULL JOIN this includes both sides of the join, and must in fact
    2524             :  *      equal qualscope)
    2525             :  * 'incompatible_relids': the set of outer-join relid(s) that must not be
    2526             :  *      computed below this qual.  We only bother to compute this for
    2527             :  *      "clone" quals, otherwise it can be left NULL.
    2528             :  * 'allow_equivalence': true if it's okay to convert clause into an
    2529             :  *      EquivalenceClass
    2530             :  * 'has_clone': has_clone property to assign to the qual
    2531             :  * 'is_clone': is_clone property to assign to the qual
    2532             :  * 'postponed_oj_qual_list': if not NULL, non-degenerate outer join clauses
    2533             :  *      should be added to this list instead of being processed (list entries
    2534             :  *      are just the bare clauses)
    2535             :  *
    2536             :  * 'qualscope' identifies what level of JOIN the qual came from syntactically.
    2537             :  * 'ojscope' is needed if we decide to force the qual up to the outer-join
    2538             :  * level, which will be ojscope not necessarily qualscope.
    2539             :  *
    2540             :  * At the time this is called, root->join_info_list must contain entries for
    2541             :  * at least those special joins that are syntactically below this qual.
    2542             :  * (We now need that only for detection of redundant IS NULL quals.)
    2543             :  */
    2544             : static void
    2545      562358 : distribute_qual_to_rels(PlannerInfo *root, Node *clause,
    2546             :                         JoinTreeItem *jtitem,
    2547             :                         SpecialJoinInfo *sjinfo,
    2548             :                         Index security_level,
    2549             :                         Relids qualscope,
    2550             :                         Relids ojscope,
    2551             :                         Relids outerjoin_nonnullable,
    2552             :                         Relids incompatible_relids,
    2553             :                         bool allow_equivalence,
    2554             :                         bool has_clone,
    2555             :                         bool is_clone,
    2556             :                         List **postponed_oj_qual_list)
    2557             : {
    2558             :     Relids      relids;
    2559             :     bool        is_pushed_down;
    2560      562358 :     bool        pseudoconstant = false;
    2561             :     bool        maybe_equivalence;
    2562             :     bool        maybe_outer_join;
    2563             :     RestrictInfo *restrictinfo;
    2564             : 
    2565             :     /*
    2566             :      * Retrieve all relids mentioned within the clause.
    2567             :      */
    2568      562358 :     relids = pull_varnos(root, clause);
    2569             : 
    2570             :     /*
    2571             :      * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels
    2572             :      * that aren't within its syntactic scope; however, if we pulled up a
    2573             :      * LATERAL subquery then we might find such references in quals that have
    2574             :      * been pulled up.  We need to treat such quals as belonging to the join
    2575             :      * level that includes every rel they reference.  Although we could make
    2576             :      * pull_up_subqueries() place such quals correctly to begin with, it's
    2577             :      * easier to handle it here.  When we find a clause that contains Vars
    2578             :      * outside its syntactic scope, locate the nearest parent join level that
    2579             :      * includes all the required rels and add the clause to that level's
    2580             :      * lateral_clauses list.  We'll process it when we reach that join level.
    2581             :      */
    2582      562358 :     if (!bms_is_subset(relids, qualscope))
    2583             :     {
    2584             :         JoinTreeItem *pitem;
    2585             : 
    2586             :         Assert(root->hasLateralRTEs);    /* shouldn't happen otherwise */
    2587             :         Assert(sjinfo == NULL); /* mustn't postpone past outer join */
    2588         116 :         for (pitem = jtitem->jti_parent; pitem; pitem = pitem->jti_parent)
    2589             :         {
    2590         116 :             if (bms_is_subset(relids, pitem->qualscope))
    2591             :             {
    2592         110 :                 pitem->lateral_clauses = lappend(pitem->lateral_clauses,
    2593             :                                                  clause);
    2594      390850 :                 return;
    2595             :             }
    2596             : 
    2597             :             /*
    2598             :              * We should not be postponing any quals past an outer join.  If
    2599             :              * this Assert fires, pull_up_subqueries() messed up.
    2600             :              */
    2601             :             Assert(pitem->sjinfo == NULL);
    2602             :         }
    2603           0 :         elog(ERROR, "failed to postpone qual containing lateral reference");
    2604             :     }
    2605             : 
    2606             :     /*
    2607             :      * If it's an outer-join clause, also check that relids is a subset of
    2608             :      * ojscope.  (This should not fail if the syntactic scope check passed.)
    2609             :      */
    2610      562248 :     if (ojscope && !bms_is_subset(relids, ojscope))
    2611           0 :         elog(ERROR, "JOIN qualification cannot refer to other relations");
    2612             : 
    2613             :     /*
    2614             :      * If the clause is variable-free, our normal heuristic for pushing it
    2615             :      * down to just the mentioned rels doesn't work, because there are none.
    2616             :      *
    2617             :      * If the clause is an outer-join clause, we must force it to the OJ's
    2618             :      * semantic level to preserve semantics.
    2619             :      *
    2620             :      * Otherwise, when the clause contains volatile functions, we force it to
    2621             :      * be evaluated at its original syntactic level.  This preserves the
    2622             :      * expected semantics.
    2623             :      *
    2624             :      * When the clause contains no volatile functions either, it is actually a
    2625             :      * pseudoconstant clause that will not change value during any one
    2626             :      * execution of the plan, and hence can be used as a one-time qual in a
    2627             :      * gating Result plan node.  We put such a clause into the regular
    2628             :      * RestrictInfo lists for the moment, but eventually createplan.c will
    2629             :      * pull it out and make a gating Result node immediately above whatever
    2630             :      * plan node the pseudoconstant clause is assigned to.  It's usually best
    2631             :      * to put a gating node as high in the plan tree as possible.
    2632             :      */
    2633      562248 :     if (bms_is_empty(relids))
    2634             :     {
    2635       10736 :         if (ojscope)
    2636             :         {
    2637             :             /* clause is attached to outer join, eval it there */
    2638         392 :             relids = bms_copy(ojscope);
    2639             :             /* mustn't use as gating qual, so don't mark pseudoconstant */
    2640             :         }
    2641       10344 :         else if (contain_volatile_functions(clause))
    2642             :         {
    2643             :             /* eval at original syntactic level */
    2644         174 :             relids = bms_copy(qualscope);
    2645             :             /* again, can't mark pseudoconstant */
    2646             :         }
    2647             :         else
    2648             :         {
    2649             :             /*
    2650             :              * If we are in the top-level join domain, we can push the qual to
    2651             :              * the top of the plan tree.  Otherwise, be conservative and eval
    2652             :              * it at original syntactic level.  (Ideally we'd push it to the
    2653             :              * top of the current join domain in all cases, but that causes
    2654             :              * problems if we later rearrange outer-join evaluation order.
    2655             :              * Pseudoconstant quals below the top level are a pretty odd case,
    2656             :              * so it's not clear that it's worth working hard on.)
    2657             :              */
    2658       10170 :             if (jtitem->jdomain == (JoinDomain *) linitial(root->join_domains))
    2659       10110 :                 relids = bms_copy(jtitem->jdomain->jd_relids);
    2660             :             else
    2661          60 :                 relids = bms_copy(qualscope);
    2662             :             /* mark as gating qual */
    2663       10170 :             pseudoconstant = true;
    2664             :             /* tell createplan.c to check for gating quals */
    2665       10170 :             root->hasPseudoConstantQuals = true;
    2666             :         }
    2667             :     }
    2668             : 
    2669             :     /*----------
    2670             :      * Check to see if clause application must be delayed by outer-join
    2671             :      * considerations.
    2672             :      *
    2673             :      * A word about is_pushed_down: we mark the qual as "pushed down" if
    2674             :      * it is (potentially) applicable at a level different from its original
    2675             :      * syntactic level.  This flag is used to distinguish OUTER JOIN ON quals
    2676             :      * from other quals pushed down to the same joinrel.  The rules are:
    2677             :      *      WHERE quals and INNER JOIN quals: is_pushed_down = true.
    2678             :      *      Non-degenerate OUTER JOIN quals: is_pushed_down = false.
    2679             :      *      Degenerate OUTER JOIN quals: is_pushed_down = true.
    2680             :      * A "degenerate" OUTER JOIN qual is one that doesn't mention the
    2681             :      * non-nullable side, and hence can be pushed down into the nullable side
    2682             :      * without changing the join result.  It is correct to treat it as a
    2683             :      * regular filter condition at the level where it is evaluated.
    2684             :      *
    2685             :      * Note: it is not immediately obvious that a simple boolean is enough
    2686             :      * for this: if for some reason we were to attach a degenerate qual to
    2687             :      * its original join level, it would need to be treated as an outer join
    2688             :      * qual there.  However, this cannot happen, because all the rels the
    2689             :      * clause mentions must be in the outer join's min_righthand, therefore
    2690             :      * the join it needs must be formed before the outer join; and we always
    2691             :      * attach quals to the lowest level where they can be evaluated.  But
    2692             :      * if we were ever to re-introduce a mechanism for delaying evaluation
    2693             :      * of "expensive" quals, this area would need work.
    2694             :      *
    2695             :      * Note: generally, use of is_pushed_down has to go through the macro
    2696             :      * RINFO_IS_PUSHED_DOWN, because that flag alone is not always sufficient
    2697             :      * to tell whether a clause must be treated as pushed-down in context.
    2698             :      * This seems like another reason why it should perhaps be rethought.
    2699             :      *----------
    2700             :      */
    2701      562248 :     if (bms_overlap(relids, outerjoin_nonnullable))
    2702             :     {
    2703             :         /*
    2704             :          * The qual is attached to an outer join and mentions (some of the)
    2705             :          * rels on the nonnullable side, so it's not degenerate.  If the
    2706             :          * caller wants to postpone handling such clauses, just add it to
    2707             :          * postponed_oj_qual_list and return.  (The work we've done up to here
    2708             :          * will have to be redone later, but there's not much of it.)
    2709             :          */
    2710      101010 :         if (postponed_oj_qual_list != NULL)
    2711             :         {
    2712       44866 :             *postponed_oj_qual_list = lappend(*postponed_oj_qual_list, clause);
    2713       44866 :             return;
    2714             :         }
    2715             : 
    2716             :         /*
    2717             :          * We can't use such a clause to deduce equivalence (the left and
    2718             :          * right sides might be unequal above the join because one of them has
    2719             :          * gone to NULL) ... but we might be able to use it for more limited
    2720             :          * deductions, if it is mergejoinable.  So consider adding it to the
    2721             :          * lists of set-aside outer-join clauses.
    2722             :          */
    2723       56144 :         is_pushed_down = false;
    2724       56144 :         maybe_equivalence = false;
    2725       56144 :         maybe_outer_join = true;
    2726             : 
    2727             :         /*
    2728             :          * Now force the qual to be evaluated exactly at the level of joining
    2729             :          * corresponding to the outer join.  We cannot let it get pushed down
    2730             :          * into the nonnullable side, since then we'd produce no output rows,
    2731             :          * rather than the intended single null-extended row, for any
    2732             :          * nonnullable-side rows failing the qual.
    2733             :          */
    2734             :         Assert(ojscope);
    2735       56144 :         relids = ojscope;
    2736             :         Assert(!pseudoconstant);
    2737             :     }
    2738             :     else
    2739             :     {
    2740             :         /*
    2741             :          * Normal qual clause or degenerate outer-join clause.  Either way, we
    2742             :          * can mark it as pushed-down.
    2743             :          */
    2744      461238 :         is_pushed_down = true;
    2745             : 
    2746             :         /*
    2747             :          * It's possible that this is an IS NULL clause that's redundant with
    2748             :          * a lower antijoin; if so we can just discard it.  We need not test
    2749             :          * in any of the other cases, because this will only be possible for
    2750             :          * pushed-down clauses.
    2751             :          */
    2752      461238 :         if (check_redundant_nullability_qual(root, clause))
    2753        1132 :             return;
    2754             : 
    2755             :         /* Feed qual to the equivalence machinery, if allowed by caller */
    2756      460106 :         maybe_equivalence = allow_equivalence;
    2757             : 
    2758             :         /*
    2759             :          * Since it doesn't mention the LHS, it's certainly not useful as a
    2760             :          * set-aside OJ clause, even if it's in an OJ.
    2761             :          */
    2762      460106 :         maybe_outer_join = false;
    2763             :     }
    2764             : 
    2765             :     /*
    2766             :      * Build the RestrictInfo node itself.
    2767             :      */
    2768      516250 :     restrictinfo = make_restrictinfo(root,
    2769             :                                      (Expr *) clause,
    2770             :                                      is_pushed_down,
    2771             :                                      has_clone,
    2772             :                                      is_clone,
    2773             :                                      pseudoconstant,
    2774             :                                      security_level,
    2775             :                                      relids,
    2776             :                                      incompatible_relids,
    2777             :                                      outerjoin_nonnullable);
    2778             : 
    2779             :     /*
    2780             :      * If it's a join clause, add vars used in the clause to targetlists of
    2781             :      * their relations, so that they will be emitted by the plan nodes that
    2782             :      * scan those relations (else they won't be available at the join node!).
    2783             :      *
    2784             :      * Normally we mark the vars as needed at the join identified by "relids".
    2785             :      * However, if this is a clone clause then ignore the outer-join relids in
    2786             :      * that set.  Otherwise, vars appearing in a cloned clause would end up
    2787             :      * marked as having to propagate to the highest one of the commuting
    2788             :      * joins, which would often be an overestimate.  For such clauses, correct
    2789             :      * var propagation is ensured by making ojscope include input rels from
    2790             :      * both sides of the join.
    2791             :      *
    2792             :      * See also rebuild_joinclause_attr_needed, which has to partially repeat
    2793             :      * this work after removal of an outer join.
    2794             :      *
    2795             :      * Note: if the clause gets absorbed into an EquivalenceClass then this
    2796             :      * may be unnecessary, but for now we have to do it to cover the case
    2797             :      * where the EC becomes ec_broken and we end up reinserting the original
    2798             :      * clauses into the plan.
    2799             :      */
    2800      516250 :     if (bms_membership(relids) == BMS_MULTIPLE)
    2801             :     {
    2802      147758 :         List       *vars = pull_var_clause(clause,
    2803             :                                            PVC_RECURSE_AGGREGATES |
    2804             :                                            PVC_RECURSE_WINDOWFUNCS |
    2805             :                                            PVC_INCLUDE_PLACEHOLDERS);
    2806             :         Relids      where_needed;
    2807             : 
    2808      147758 :         if (is_clone)
    2809        4762 :             where_needed = bms_intersect(relids, root->all_baserels);
    2810             :         else
    2811      142996 :             where_needed = relids;
    2812      147758 :         add_vars_to_targetlist(root, vars, where_needed);
    2813      147758 :         list_free(vars);
    2814             :     }
    2815             : 
    2816             :     /*
    2817             :      * We check "mergejoinability" of every clause, not only join clauses,
    2818             :      * because we want to know about equivalences between vars of the same
    2819             :      * relation, or between vars and consts.
    2820             :      */
    2821      516250 :     check_mergejoinable(restrictinfo);
    2822             : 
    2823             :     /*
    2824             :      * If it is a true equivalence clause, send it to the EquivalenceClass
    2825             :      * machinery.  We do *not* attach it directly to any restriction or join
    2826             :      * lists.  The EC code will propagate it to the appropriate places later.
    2827             :      *
    2828             :      * If the clause has a mergejoinable operator, yet isn't an equivalence
    2829             :      * because it is an outer-join clause, the EC code may still be able to do
    2830             :      * something with it.  We add it to appropriate lists for further
    2831             :      * consideration later.  Specifically:
    2832             :      *
    2833             :      * If it is a left or right outer-join qualification that relates the two
    2834             :      * sides of the outer join (no funny business like leftvar1 = leftvar2 +
    2835             :      * rightvar), we add it to root->left_join_clauses or
    2836             :      * root->right_join_clauses according to which side the nonnullable
    2837             :      * variable appears on.
    2838             :      *
    2839             :      * If it is a full outer-join qualification, we add it to
    2840             :      * root->full_join_clauses.  (Ideally we'd discard cases that aren't
    2841             :      * leftvar = rightvar, as we do for left/right joins, but this routine
    2842             :      * doesn't have the info needed to do that; and the current usage of the
    2843             :      * full_join_clauses list doesn't require that, so it's not currently
    2844             :      * worth complicating this routine's API to make it possible.)
    2845             :      *
    2846             :      * If none of the above hold, pass it off to
    2847             :      * distribute_restrictinfo_to_rels().
    2848             :      *
    2849             :      * In all cases, it's important to initialize the left_ec and right_ec
    2850             :      * fields of a mergejoinable clause, so that all possibly mergejoinable
    2851             :      * expressions have representations in EquivalenceClasses.  If
    2852             :      * process_equivalence is successful, it will take care of that;
    2853             :      * otherwise, we have to call initialize_mergeclause_eclasses to do it.
    2854             :      */
    2855      516250 :     if (restrictinfo->mergeopfamilies)
    2856             :     {
    2857      345918 :         if (maybe_equivalence)
    2858             :         {
    2859      291222 :             if (process_equivalence(root, &restrictinfo, jtitem->jdomain))
    2860      290960 :                 return;
    2861             :             /* EC rejected it, so set left_ec/right_ec the hard way ... */
    2862         262 :             if (restrictinfo->mergeopfamilies)   /* EC might have changed this */
    2863         208 :                 initialize_mergeclause_eclasses(root, restrictinfo);
    2864             :             /* ... and fall through to distribute_restrictinfo_to_rels */
    2865             :         }
    2866       54696 :         else if (maybe_outer_join && restrictinfo->can_join)
    2867             :         {
    2868             :             /* we need to set up left_ec/right_ec the hard way */
    2869       54002 :             initialize_mergeclause_eclasses(root, restrictinfo);
    2870             :             /* now see if it should go to any outer-join lists */
    2871             :             Assert(sjinfo != NULL);
    2872       54002 :             if (bms_is_subset(restrictinfo->left_relids,
    2873       27016 :                               outerjoin_nonnullable) &&
    2874       27016 :                 !bms_overlap(restrictinfo->right_relids,
    2875             :                              outerjoin_nonnullable))
    2876             :             {
    2877             :                 /* we have outervar = innervar */
    2878       25734 :                 OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
    2879             : 
    2880       25734 :                 ojcinfo->rinfo = restrictinfo;
    2881       25734 :                 ojcinfo->sjinfo = sjinfo;
    2882       25734 :                 root->left_join_clauses = lappend(root->left_join_clauses,
    2883             :                                                   ojcinfo);
    2884       25734 :                 return;
    2885             :             }
    2886       28268 :             if (bms_is_subset(restrictinfo->right_relids,
    2887       28084 :                               outerjoin_nonnullable) &&
    2888       28084 :                 !bms_overlap(restrictinfo->left_relids,
    2889             :                              outerjoin_nonnullable))
    2890             :             {
    2891             :                 /* we have innervar = outervar */
    2892       26802 :                 OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
    2893             : 
    2894       26802 :                 ojcinfo->rinfo = restrictinfo;
    2895       26802 :                 ojcinfo->sjinfo = sjinfo;
    2896       26802 :                 root->right_join_clauses = lappend(root->right_join_clauses,
    2897             :                                                    ojcinfo);
    2898       26802 :                 return;
    2899             :             }
    2900        1466 :             if (sjinfo->jointype == JOIN_FULL)
    2901             :             {
    2902             :                 /* FULL JOIN (above tests cannot match in this case) */
    2903        1246 :                 OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
    2904             : 
    2905        1246 :                 ojcinfo->rinfo = restrictinfo;
    2906        1246 :                 ojcinfo->sjinfo = sjinfo;
    2907        1246 :                 root->full_join_clauses = lappend(root->full_join_clauses,
    2908             :                                                   ojcinfo);
    2909        1246 :                 return;
    2910             :             }
    2911             :             /* nope, so fall through to distribute_restrictinfo_to_rels */
    2912             :         }
    2913             :         else
    2914             :         {
    2915             :             /* we still need to set up left_ec/right_ec */
    2916         694 :             initialize_mergeclause_eclasses(root, restrictinfo);
    2917             :         }
    2918             :     }
    2919             : 
    2920             :     /* No EC special case applies, so push it into the clause lists */
    2921      171508 :     distribute_restrictinfo_to_rels(root, restrictinfo);
    2922             : }
    2923             : 
    2924             : /*
    2925             :  * check_redundant_nullability_qual
    2926             :  *    Check to see if the qual is an IS NULL qual that is redundant with
    2927             :  *    a lower JOIN_ANTI join.
    2928             :  *
    2929             :  * We want to suppress redundant IS NULL quals, not so much to save cycles
    2930             :  * as to avoid generating bogus selectivity estimates for them.  So if
    2931             :  * redundancy is detected here, distribute_qual_to_rels() just throws away
    2932             :  * the qual.
    2933             :  */
    2934             : static bool
    2935      461238 : check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
    2936             : {
    2937             :     Var        *forced_null_var;
    2938             :     ListCell   *lc;
    2939             : 
    2940             :     /* Check for IS NULL, and identify the Var forced to NULL */
    2941      461238 :     forced_null_var = find_forced_null_var(clause);
    2942      461238 :     if (forced_null_var == NULL)
    2943      458566 :         return false;
    2944             : 
    2945             :     /*
    2946             :      * If the Var comes from the nullable side of a lower antijoin, the IS
    2947             :      * NULL condition is necessarily true.  If it's not nulled by anything,
    2948             :      * there is no point in searching the join_info_list.  Otherwise, we need
    2949             :      * to find out whether the nulling rel is an antijoin.
    2950             :      */
    2951        2672 :     if (forced_null_var->varnullingrels == NULL)
    2952        1428 :         return false;
    2953             : 
    2954        1400 :     foreach(lc, root->join_info_list)
    2955             :     {
    2956        1288 :         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
    2957             : 
    2958             :         /*
    2959             :          * This test will not succeed if sjinfo->ojrelid is zero, which is
    2960             :          * possible for an antijoin that was converted from a semijoin; but in
    2961             :          * such a case the Var couldn't have come from its nullable side.
    2962             :          */
    2963        2420 :         if (sjinfo->jointype == JOIN_ANTI && sjinfo->ojrelid != 0 &&
    2964        1132 :             bms_is_member(sjinfo->ojrelid, forced_null_var->varnullingrels))
    2965        1132 :             return true;
    2966             :     }
    2967             : 
    2968         112 :     return false;
    2969             : }
    2970             : 
    2971             : /*
    2972             :  * add_base_clause_to_rel
    2973             :  *      Add 'restrictinfo' as a baserestrictinfo to the base relation denoted
    2974             :  *      by 'relid'.  We offer some simple prechecks to try to determine if the
    2975             :  *      qual is always true, in which case we ignore it rather than add it.
    2976             :  *      If we detect the qual is always false, we replace it with
    2977             :  *      constant-FALSE.
    2978             :  */
    2979             : static void
    2980      386868 : add_base_clause_to_rel(PlannerInfo *root, Index relid,
    2981             :                        RestrictInfo *restrictinfo)
    2982             : {
    2983      386868 :     RelOptInfo *rel = find_base_rel(root, relid);
    2984      386868 :     RangeTblEntry *rte = root->simple_rte_array[relid];
    2985             : 
    2986             :     Assert(bms_membership(restrictinfo->required_relids) == BMS_SINGLETON);
    2987             : 
    2988             :     /*
    2989             :      * For inheritance parent tables, we must always record the RestrictInfo
    2990             :      * in baserestrictinfo as is.  If we were to transform or skip adding it,
    2991             :      * then the original wouldn't be available in apply_child_basequals. Since
    2992             :      * there are two RangeTblEntries for inheritance parents, one with
    2993             :      * inh==true and the other with inh==false, we're still able to apply this
    2994             :      * optimization to the inh==false one.  The inh==true one is what
    2995             :      * apply_child_basequals() sees, whereas the inh==false one is what's used
    2996             :      * for the scan node in the final plan.
    2997             :      *
    2998             :      * We make an exception to this for partitioned tables.  For these, we
    2999             :      * always apply the constant-TRUE and constant-FALSE transformations.  A
    3000             :      * qual which is either of these for a partitioned table must also be that
    3001             :      * for all of its child partitions.
    3002             :      */
    3003      386868 :     if (!rte->inh || rte->relkind == RELKIND_PARTITIONED_TABLE)
    3004             :     {
    3005             :         /* Don't add the clause if it is always true */
    3006      385114 :         if (restriction_is_always_true(root, restrictinfo))
    3007         670 :             return;
    3008             : 
    3009             :         /*
    3010             :          * Substitute the origin qual with constant-FALSE if it is provably
    3011             :          * always false.
    3012             :          *
    3013             :          * Note that we need to keep the same rinfo_serial, since it is in
    3014             :          * practice the same condition.  We also need to reset the
    3015             :          * last_rinfo_serial counter, which is essential to ensure that the
    3016             :          * RestrictInfos for the "same" qual condition get identical serial
    3017             :          * numbers (see deconstruct_distribute_oj_quals).
    3018             :          */
    3019      384444 :         if (restriction_is_always_false(root, restrictinfo))
    3020             :         {
    3021          34 :             int         save_rinfo_serial = restrictinfo->rinfo_serial;
    3022          34 :             int         save_last_rinfo_serial = root->last_rinfo_serial;
    3023             : 
    3024          34 :             restrictinfo = make_restrictinfo(root,
    3025          34 :                                              (Expr *) makeBoolConst(false, false),
    3026          34 :                                              restrictinfo->is_pushed_down,
    3027          34 :                                              restrictinfo->has_clone,
    3028          34 :                                              restrictinfo->is_clone,
    3029          34 :                                              restrictinfo->pseudoconstant,
    3030             :                                              0, /* security_level */
    3031             :                                              restrictinfo->required_relids,
    3032             :                                              restrictinfo->incompatible_relids,
    3033             :                                              restrictinfo->outer_relids);
    3034          34 :             restrictinfo->rinfo_serial = save_rinfo_serial;
    3035          34 :             root->last_rinfo_serial = save_last_rinfo_serial;
    3036             :         }
    3037             :     }
    3038             : 
    3039             :     /* Add clause to rel's restriction list */
    3040      386198 :     rel->baserestrictinfo = lappend(rel->baserestrictinfo, restrictinfo);
    3041             : 
    3042             :     /* Update security level info */
    3043      386198 :     rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
    3044             :                                          restrictinfo->security_level);
    3045             : }
    3046             : 
    3047             : /*
    3048             :  * expr_is_nonnullable
    3049             :  *    Check to see if the Expr cannot be NULL
    3050             :  *
    3051             :  * If the Expr is a simple Var that is defined NOT NULL and meanwhile is not
    3052             :  * nulled by any outer joins, then we can know that it cannot be NULL.
    3053             :  */
    3054             : static bool
    3055       10994 : expr_is_nonnullable(PlannerInfo *root, Expr *expr)
    3056             : {
    3057             :     RelOptInfo *rel;
    3058             :     Var        *var;
    3059             : 
    3060             :     /* For now only check simple Vars */
    3061       10994 :     if (!IsA(expr, Var))
    3062         628 :         return false;
    3063             : 
    3064       10366 :     var = (Var *) expr;
    3065             : 
    3066             :     /* could the Var be nulled by any outer joins? */
    3067       10366 :     if (!bms_is_empty(var->varnullingrels))
    3068         864 :         return false;
    3069             : 
    3070             :     /* system columns cannot be NULL */
    3071        9502 :     if (var->varattno < 0)
    3072          24 :         return true;
    3073             : 
    3074             :     /* is the column defined NOT NULL? */
    3075        9478 :     rel = find_base_rel(root, var->varno);
    3076       18800 :     if (var->varattno > 0 &&
    3077        9322 :         bms_is_member(var->varattno, rel->notnullattnums))
    3078         758 :         return true;
    3079             : 
    3080        8720 :     return false;
    3081             : }
    3082             : 
    3083             : /*
    3084             :  * restriction_is_always_true
    3085             :  *    Check to see if the RestrictInfo is always true.
    3086             :  *
    3087             :  * Currently we only check for NullTest quals and OR clauses that include
    3088             :  * NullTest quals.  We may extend it in the future.
    3089             :  */
    3090             : bool
    3091      500834 : restriction_is_always_true(PlannerInfo *root,
    3092             :                            RestrictInfo *restrictinfo)
    3093             : {
    3094             :     /*
    3095             :      * For a clone clause, we don't have a reliable way to determine if the
    3096             :      * input expression of a NullTest is non-nullable: nullingrel bits in
    3097             :      * clone clauses may not reflect reality, so we dare not draw conclusions
    3098             :      * from clones about whether Vars are guaranteed not-null.
    3099             :      */
    3100      500834 :     if (restrictinfo->has_clone || restrictinfo->is_clone)
    3101        9488 :         return false;
    3102             : 
    3103             :     /* Check for NullTest qual */
    3104      491346 :     if (IsA(restrictinfo->clause, NullTest))
    3105             :     {
    3106       11420 :         NullTest   *nulltest = (NullTest *) restrictinfo->clause;
    3107             : 
    3108             :         /* is this NullTest an IS_NOT_NULL qual? */
    3109       11420 :         if (nulltest->nulltesttype != IS_NOT_NULL)
    3110        3120 :             return false;
    3111             : 
    3112        8300 :         return expr_is_nonnullable(root, nulltest->arg);
    3113             :     }
    3114             : 
    3115             :     /* If it's an OR, check its sub-clauses */
    3116      479926 :     if (restriction_is_or_clause(restrictinfo))
    3117             :     {
    3118             :         ListCell   *lc;
    3119             : 
    3120             :         Assert(is_orclause(restrictinfo->orclause));
    3121             : 
    3122             :         /*
    3123             :          * if any of the given OR branches is provably always true then the
    3124             :          * entire condition is true.
    3125             :          */
    3126       32634 :         foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
    3127             :         {
    3128       22796 :             Node       *orarg = (Node *) lfirst(lc);
    3129             : 
    3130       22796 :             if (!IsA(orarg, RestrictInfo))
    3131        3036 :                 continue;
    3132             : 
    3133       19760 :             if (restriction_is_always_true(root, (RestrictInfo *) orarg))
    3134          12 :                 return true;
    3135             :         }
    3136             :     }
    3137             : 
    3138      479914 :     return false;
    3139             : }
    3140             : 
    3141             : /*
    3142             :  * restriction_is_always_false
    3143             :  *    Check to see if the RestrictInfo is always false.
    3144             :  *
    3145             :  * Currently we only check for NullTest quals and OR clauses that include
    3146             :  * NullTest quals.  We may extend it in the future.
    3147             :  */
    3148             : bool
    3149      488864 : restriction_is_always_false(PlannerInfo *root,
    3150             :                             RestrictInfo *restrictinfo)
    3151             : {
    3152             :     /*
    3153             :      * For a clone clause, we don't have a reliable way to determine if the
    3154             :      * input expression of a NullTest is non-nullable: nullingrel bits in
    3155             :      * clone clauses may not reflect reality, so we dare not draw conclusions
    3156             :      * from clones about whether Vars are guaranteed not-null.
    3157             :      */
    3158      488864 :     if (restrictinfo->has_clone || restrictinfo->is_clone)
    3159        9488 :         return false;
    3160             : 
    3161             :     /* Check for NullTest qual */
    3162      479376 :     if (IsA(restrictinfo->clause, NullTest))
    3163             :     {
    3164        9566 :         NullTest   *nulltest = (NullTest *) restrictinfo->clause;
    3165             : 
    3166             :         /* is this NullTest an IS_NULL qual? */
    3167        9566 :         if (nulltest->nulltesttype != IS_NULL)
    3168        6872 :             return false;
    3169             : 
    3170        2694 :         return expr_is_nonnullable(root, nulltest->arg);
    3171             :     }
    3172             : 
    3173             :     /* If it's an OR, check its sub-clauses */
    3174      469810 :     if (restriction_is_or_clause(restrictinfo))
    3175             :     {
    3176             :         ListCell   *lc;
    3177             : 
    3178             :         Assert(is_orclause(restrictinfo->orclause));
    3179             : 
    3180             :         /*
    3181             :          * Currently, when processing OR expressions, we only return true when
    3182             :          * all of the OR branches are always false.  This could perhaps be
    3183             :          * expanded to remove OR branches that are provably false.  This may
    3184             :          * be a useful thing to do as it could result in the OR being left
    3185             :          * with a single arg.  That's useful as it would allow the OR
    3186             :          * condition to be replaced with its single argument which may allow
    3187             :          * use of an index for faster filtering on the remaining condition.
    3188             :          */
    3189        9880 :         foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
    3190             :         {
    3191        9868 :             Node       *orarg = (Node *) lfirst(lc);
    3192             : 
    3193        9868 :             if (!IsA(orarg, RestrictInfo) ||
    3194        8460 :                 !restriction_is_always_false(root, (RestrictInfo *) orarg))
    3195        9826 :                 return false;
    3196             :         }
    3197          12 :         return true;
    3198             :     }
    3199             : 
    3200      459972 :     return false;
    3201             : }
    3202             : 
    3203             : /*
    3204             :  * distribute_restrictinfo_to_rels
    3205             :  *    Push a completed RestrictInfo into the proper restriction or join
    3206             :  *    clause list(s).
    3207             :  *
    3208             :  * This is the last step of distribute_qual_to_rels() for ordinary qual
    3209             :  * clauses.  Clauses that are interesting for equivalence-class processing
    3210             :  * are diverted to the EC machinery, but may ultimately get fed back here.
    3211             :  */
    3212             : void
    3213      454546 : distribute_restrictinfo_to_rels(PlannerInfo *root,
    3214             :                                 RestrictInfo *restrictinfo)
    3215             : {
    3216      454546 :     Relids      relids = restrictinfo->required_relids;
    3217             : 
    3218      454546 :     if (!bms_is_empty(relids))
    3219             :     {
    3220             :         int         relid;
    3221             : 
    3222      454546 :         if (bms_get_singleton_member(relids, &relid))
    3223             :         {
    3224             :             /*
    3225             :              * There is only one relation participating in the clause, so it
    3226             :              * is a restriction clause for that relation.
    3227             :              */
    3228      386868 :             add_base_clause_to_rel(root, relid, restrictinfo);
    3229             :         }
    3230             :         else
    3231             :         {
    3232             :             /*
    3233             :              * The clause is a join clause, since there is more than one rel
    3234             :              * in its relid set.
    3235             :              */
    3236             : 
    3237             :             /*
    3238             :              * Check for hashjoinable operators.  (We don't bother setting the
    3239             :              * hashjoin info except in true join clauses.)
    3240             :              */
    3241       67678 :             check_hashjoinable(restrictinfo);
    3242             : 
    3243             :             /*
    3244             :              * Likewise, check if the clause is suitable to be used with a
    3245             :              * Memoize node to cache inner tuples during a parameterized
    3246             :              * nested loop.
    3247             :              */
    3248       67678 :             check_memoizable(restrictinfo);
    3249             : 
    3250             :             /*
    3251             :              * Add clause to the join lists of all the relevant relations.
    3252             :              */
    3253       67678 :             add_join_clause_to_rels(root, restrictinfo, relids);
    3254             :         }
    3255             :     }
    3256             :     else
    3257             :     {
    3258             :         /*
    3259             :          * clause references no rels, and therefore we have no place to attach
    3260             :          * it.  Shouldn't get here if callers are working properly.
    3261             :          */
    3262           0 :         elog(ERROR, "cannot cope with variable-free clause");
    3263             :     }
    3264      454546 : }
    3265             : 
    3266             : /*
    3267             :  * process_implied_equality
    3268             :  *    Create a restrictinfo item that says "item1 op item2", and push it
    3269             :  *    into the appropriate lists.  (In practice opno is always a btree
    3270             :  *    equality operator.)
    3271             :  *
    3272             :  * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
    3273             :  * This must contain at least all the rels used in the expressions, but it
    3274             :  * is used only to set the qual application level when both exprs are
    3275             :  * variable-free.  (Hence, it should usually match the join domain in which
    3276             :  * the clause applies.)  Otherwise the qual is applied at the lowest join
    3277             :  * level that provides all its variables.
    3278             :  *
    3279             :  * "security_level" is the security level to assign to the new restrictinfo.
    3280             :  *
    3281             :  * "both_const" indicates whether both items are known pseudo-constant;
    3282             :  * in this case it is worth applying eval_const_expressions() in case we
    3283             :  * can produce constant TRUE or constant FALSE.  (Otherwise it's not,
    3284             :  * because the expressions went through eval_const_expressions already.)
    3285             :  *
    3286             :  * Returns the generated RestrictInfo, if any.  The result will be NULL
    3287             :  * if both_const is true and we successfully reduced the clause to
    3288             :  * constant TRUE.
    3289             :  *
    3290             :  * Note: this function will copy item1 and item2, but it is caller's
    3291             :  * responsibility to make sure that the Relids parameters are fresh copies
    3292             :  * not shared with other uses.
    3293             :  *
    3294             :  * Note: we do not do initialize_mergeclause_eclasses() here.  It is
    3295             :  * caller's responsibility that left_ec/right_ec be set as necessary.
    3296             :  */
    3297             : RestrictInfo *
    3298       38062 : process_implied_equality(PlannerInfo *root,
    3299             :                          Oid opno,
    3300             :                          Oid collation,
    3301             :                          Expr *item1,
    3302             :                          Expr *item2,
    3303             :                          Relids qualscope,
    3304             :                          Index security_level,
    3305             :                          bool both_const)
    3306             : {
    3307             :     RestrictInfo *restrictinfo;
    3308             :     Node       *clause;
    3309             :     Relids      relids;
    3310       38062 :     bool        pseudoconstant = false;
    3311             : 
    3312             :     /*
    3313             :      * Build the new clause.  Copy to ensure it shares no substructure with
    3314             :      * original (this is necessary in case there are subselects in there...)
    3315             :      */
    3316       38062 :     clause = (Node *) make_opclause(opno,
    3317             :                                     BOOLOID,    /* opresulttype */
    3318             :                                     false,  /* opretset */
    3319       38062 :                                     copyObject(item1),
    3320       38062 :                                     copyObject(item2),
    3321             :                                     InvalidOid,
    3322             :                                     collation);
    3323             : 
    3324             :     /* If both constant, try to reduce to a boolean constant. */
    3325       38062 :     if (both_const)
    3326             :     {
    3327         132 :         clause = eval_const_expressions(root, clause);
    3328             : 
    3329             :         /* If we produced const TRUE, just drop the clause */
    3330         132 :         if (clause && IsA(clause, Const))
    3331             :         {
    3332         126 :             Const      *cclause = (Const *) clause;
    3333             : 
    3334             :             Assert(cclause->consttype == BOOLOID);
    3335         126 :             if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
    3336           0 :                 return NULL;
    3337             :         }
    3338             :     }
    3339             : 
    3340             :     /*
    3341             :      * The rest of this is a very cut-down version of distribute_qual_to_rels.
    3342             :      * We can skip most of the work therein, but there are a couple of special
    3343             :      * cases we still have to handle.
    3344             :      *
    3345             :      * Retrieve all relids mentioned within the possibly-simplified clause.
    3346             :      */
    3347       38062 :     relids = pull_varnos(root, clause);
    3348             :     Assert(bms_is_subset(relids, qualscope));
    3349             : 
    3350             :     /*
    3351             :      * If the clause is variable-free, our normal heuristic for pushing it
    3352             :      * down to just the mentioned rels doesn't work, because there are none.
    3353             :      * Apply it as a gating qual at the appropriate level (see comments for
    3354             :      * get_join_domain_min_rels).
    3355             :      */
    3356       38062 :     if (bms_is_empty(relids))
    3357             :     {
    3358             :         /* eval at join domain's safe level */
    3359         132 :         relids = get_join_domain_min_rels(root, qualscope);
    3360             :         /* mark as gating qual */
    3361         132 :         pseudoconstant = true;
    3362             :         /* tell createplan.c to check for gating quals */
    3363         132 :         root->hasPseudoConstantQuals = true;
    3364             :     }
    3365             : 
    3366             :     /*
    3367             :      * Build the RestrictInfo node itself.
    3368             :      */
    3369       38062 :     restrictinfo = make_restrictinfo(root,
    3370             :                                      (Expr *) clause,
    3371             :                                      true,  /* is_pushed_down */
    3372             :                                      false, /* !has_clone */
    3373             :                                      false, /* !is_clone */
    3374             :                                      pseudoconstant,
    3375             :                                      security_level,
    3376             :                                      relids,
    3377             :                                      NULL,  /* incompatible_relids */
    3378             :                                      NULL); /* outer_relids */
    3379             : 
    3380             :     /*
    3381             :      * If it's a join clause, add vars used in the clause to targetlists of
    3382             :      * their relations, so that they will be emitted by the plan nodes that
    3383             :      * scan those relations (else they won't be available at the join node!).
    3384             :      *
    3385             :      * Typically, we'd have already done this when the component expressions
    3386             :      * were first seen by distribute_qual_to_rels; but it is possible that
    3387             :      * some of the Vars could have missed having that done because they only
    3388             :      * appeared in single-relation clauses originally.  So do it here for
    3389             :      * safety.
    3390             :      *
    3391             :      * See also rebuild_joinclause_attr_needed, which has to partially repeat
    3392             :      * this work after removal of an outer join.  (Since we will put this
    3393             :      * clause into the joininfo lists, that function needn't do any extra work
    3394             :      * to find it.)
    3395             :      */
    3396       38062 :     if (bms_membership(relids) == BMS_MULTIPLE)
    3397             :     {
    3398          60 :         List       *vars = pull_var_clause(clause,
    3399             :                                            PVC_RECURSE_AGGREGATES |
    3400             :                                            PVC_RECURSE_WINDOWFUNCS |
    3401             :                                            PVC_INCLUDE_PLACEHOLDERS);
    3402             : 
    3403          60 :         add_vars_to_targetlist(root, vars, relids);
    3404          60 :         list_free(vars);
    3405             :     }
    3406             : 
    3407             :     /*
    3408             :      * Check mergejoinability.  This will usually succeed, since the op came
    3409             :      * from an EquivalenceClass; but we could have reduced the original clause
    3410             :      * to a constant.
    3411             :      */
    3412       38062 :     check_mergejoinable(restrictinfo);
    3413             : 
    3414             :     /*
    3415             :      * Note we don't do initialize_mergeclause_eclasses(); the caller can
    3416             :      * handle that much more cheaply than we can.  It's okay to call
    3417             :      * distribute_restrictinfo_to_rels() before that happens.
    3418             :      */
    3419             : 
    3420             :     /*
    3421             :      * Push the new clause into all the appropriate restrictinfo lists.
    3422             :      */
    3423       38062 :     distribute_restrictinfo_to_rels(root, restrictinfo);
    3424             : 
    3425       38062 :     return restrictinfo;
    3426             : }
    3427             : 
    3428             : /*
    3429             :  * build_implied_join_equality --- build a RestrictInfo for a derived equality
    3430             :  *
    3431             :  * This overlaps the functionality of process_implied_equality(), but we
    3432             :  * must not push the RestrictInfo into the joininfo tree.
    3433             :  *
    3434             :  * Note: this function will copy item1 and item2, but it is caller's
    3435             :  * responsibility to make sure that the Relids parameters are fresh copies
    3436             :  * not shared with other uses.
    3437             :  *
    3438             :  * Note: we do not do initialize_mergeclause_eclasses() here.  It is
    3439             :  * caller's responsibility that left_ec/right_ec be set as necessary.
    3440             :  */
    3441             : RestrictInfo *
    3442       73178 : build_implied_join_equality(PlannerInfo *root,
    3443             :                             Oid opno,
    3444             :                             Oid collation,
    3445             :                             Expr *item1,
    3446             :                             Expr *item2,
    3447             :                             Relids qualscope,
    3448             :                             Index security_level)
    3449             : {
    3450             :     RestrictInfo *restrictinfo;
    3451             :     Expr       *clause;
    3452             : 
    3453             :     /*
    3454             :      * Build the new clause.  Copy to ensure it shares no substructure with
    3455             :      * original (this is necessary in case there are subselects in there...)
    3456             :      */
    3457       73178 :     clause = make_opclause(opno,
    3458             :                            BOOLOID, /* opresulttype */
    3459             :                            false,   /* opretset */
    3460       73178 :                            copyObject(item1),
    3461       73178 :                            copyObject(item2),
    3462             :                            InvalidOid,
    3463             :                            collation);
    3464             : 
    3465             :     /*
    3466             :      * Build the RestrictInfo node itself.
    3467             :      */
    3468       73178 :     restrictinfo = make_restrictinfo(root,
    3469             :                                      clause,
    3470             :                                      true,  /* is_pushed_down */
    3471             :                                      false, /* !has_clone */
    3472             :                                      false, /* !is_clone */
    3473             :                                      false, /* pseudoconstant */
    3474             :                                      security_level,    /* security_level */
    3475             :                                      qualscope, /* required_relids */
    3476             :                                      NULL,  /* incompatible_relids */
    3477             :                                      NULL); /* outer_relids */
    3478             : 
    3479             :     /* Set mergejoinability/hashjoinability flags */
    3480       73178 :     check_mergejoinable(restrictinfo);
    3481       73178 :     check_hashjoinable(restrictinfo);
    3482       73178 :     check_memoizable(restrictinfo);
    3483             : 
    3484       73178 :     return restrictinfo;
    3485             : }
    3486             : 
    3487             : /*
    3488             :  * get_join_domain_min_rels
    3489             :  *    Identify the appropriate join level for derived quals belonging
    3490             :  *    to the join domain with the given relids.
    3491             :  *
    3492             :  * When we derive a pseudoconstant (Var-free) clause from an EquivalenceClass,
    3493             :  * we'd ideally apply the clause at the top level of the EC's join domain.
    3494             :  * However, if there are any outer joins inside that domain that get commuted
    3495             :  * with joins outside it, that leads to not finding a correct place to apply
    3496             :  * the clause.  Instead, remove any lower outer joins from the relid set,
    3497             :  * and apply the clause to just the remaining rels.  This still results in a
    3498             :  * correct answer, since if the clause produces FALSE then the LHS of these
    3499             :  * joins will be empty leading to an empty join result.
    3500             :  *
    3501             :  * However, there's no need to remove outer joins if this is the top-level
    3502             :  * join domain of the query, since then there's nothing else to commute with.
    3503             :  *
    3504             :  * Note: it's tempting to use this in distribute_qual_to_rels where it's
    3505             :  * dealing with pseudoconstant quals; but we can't because the necessary
    3506             :  * SpecialJoinInfos aren't all formed at that point.
    3507             :  *
    3508             :  * The result is always freshly palloc'd; we do not modify domain_relids.
    3509             :  */
    3510             : static Relids
    3511         132 : get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids)
    3512             : {
    3513         132 :     Relids      result = bms_copy(domain_relids);
    3514             :     ListCell   *lc;
    3515             : 
    3516             :     /* Top-level join domain? */
    3517         132 :     if (bms_equal(result, root->all_query_rels))
    3518          66 :         return result;
    3519             : 
    3520             :     /* Nope, look for lower outer joins that could potentially commute out */
    3521         138 :     foreach(lc, root->join_info_list)
    3522             :     {
    3523          72 :         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
    3524             : 
    3525         144 :         if (sjinfo->jointype == JOIN_LEFT &&
    3526          72 :             bms_is_member(sjinfo->ojrelid, result))
    3527             :         {
    3528           6 :             result = bms_del_member(result, sjinfo->ojrelid);
    3529           6 :             result = bms_del_members(result, sjinfo->syn_righthand);
    3530             :         }
    3531             :     }
    3532          66 :     return result;
    3533             : }
    3534             : 
    3535             : 
    3536             : /*
    3537             :  * rebuild_joinclause_attr_needed
    3538             :  *    Put back attr_needed bits for Vars/PHVs needed for join clauses.
    3539             :  *
    3540             :  * This is used to rebuild attr_needed/ph_needed sets after removal of a
    3541             :  * useless outer join.  It should match what distribute_qual_to_rels did,
    3542             :  * except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
    3543             :  */
    3544             : void
    3545       10828 : rebuild_joinclause_attr_needed(PlannerInfo *root)
    3546             : {
    3547             :     /*
    3548             :      * We must examine all join clauses, but there's no value in processing
    3549             :      * any join clause more than once.  So it's slightly annoying that we have
    3550             :      * to find them via the per-base-relation joininfo lists.  Avoid duplicate
    3551             :      * processing by tracking the rinfo_serial numbers of join clauses we've
    3552             :      * already seen.  (This doesn't work for is_clone clauses, so we must
    3553             :      * waste effort on them.)
    3554             :      */
    3555       10828 :     Bitmapset  *seen_serials = NULL;
    3556             :     Index       rti;
    3557             : 
    3558             :     /* Scan all baserels for join clauses */
    3559       67756 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
    3560             :     {
    3561       56928 :         RelOptInfo *brel = root->simple_rel_array[rti];
    3562             :         ListCell   *lc;
    3563             : 
    3564       56928 :         if (brel == NULL)
    3565       38574 :             continue;
    3566       18354 :         if (brel->reloptkind != RELOPT_BASEREL)
    3567           0 :             continue;
    3568             : 
    3569       27682 :         foreach(lc, brel->joininfo)
    3570             :         {
    3571        9328 :             RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    3572        9328 :             Relids      relids = rinfo->required_relids;
    3573             : 
    3574        9328 :             if (!rinfo->is_clone)    /* else serial number is not unique */
    3575             :             {
    3576        9232 :                 if (bms_is_member(rinfo->rinfo_serial, seen_serials))
    3577        4970 :                     continue;   /* saw it already */
    3578        4262 :                 seen_serials = bms_add_member(seen_serials,
    3579             :                                               rinfo->rinfo_serial);
    3580             :             }
    3581             : 
    3582        4358 :             if (bms_membership(relids) == BMS_MULTIPLE)
    3583             :             {
    3584        4358 :                 List       *vars = pull_var_clause((Node *) rinfo->clause,
    3585             :                                                    PVC_RECURSE_AGGREGATES |
    3586             :                                                    PVC_RECURSE_WINDOWFUNCS |
    3587             :                                                    PVC_INCLUDE_PLACEHOLDERS);
    3588             :                 Relids      where_needed;
    3589             : 
    3590        4358 :                 if (rinfo->is_clone)
    3591          96 :                     where_needed = bms_intersect(relids, root->all_baserels);
    3592             :                 else
    3593        4262 :                     where_needed = relids;
    3594        4358 :                 add_vars_to_attr_needed(root, vars, where_needed);
    3595        4358 :                 list_free(vars);
    3596             :             }
    3597             :         }
    3598             :     }
    3599       10828 : }
    3600             : 
    3601             : 
    3602             : /*
    3603             :  * match_foreign_keys_to_quals
    3604             :  *      Match foreign-key constraints to equivalence classes and join quals
    3605             :  *
    3606             :  * The idea here is to see which query join conditions match equality
    3607             :  * constraints of a foreign-key relationship.  For such join conditions,
    3608             :  * we can use the FK semantics to make selectivity estimates that are more
    3609             :  * reliable than estimating from statistics, especially for multiple-column
    3610             :  * FKs, where the normal assumption of independent conditions tends to fail.
    3611             :  *
    3612             :  * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
    3613             :  * with info about which eclasses and join qual clauses they match, and
    3614             :  * discard any ForeignKeyOptInfos that are irrelevant for the query.
    3615             :  */
    3616             : void
    3617      314636 : match_foreign_keys_to_quals(PlannerInfo *root)
    3618             : {
    3619      314636 :     List       *newlist = NIL;
    3620             :     ListCell   *lc;
    3621             : 
    3622      316424 :     foreach(lc, root->fkey_list)
    3623             :     {
    3624        1788 :         ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
    3625             :         RelOptInfo *con_rel;
    3626             :         RelOptInfo *ref_rel;
    3627             :         int         colno;
    3628             : 
    3629             :         /*
    3630             :          * Either relid might identify a rel that is in the query's rtable but
    3631             :          * isn't referenced by the jointree, or has been removed by join
    3632             :          * removal, so that it won't have a RelOptInfo.  Hence don't use
    3633             :          * find_base_rel() here.  We can ignore such FKs.
    3634             :          */
    3635        1788 :         if (fkinfo->con_relid >= root->simple_rel_array_size ||
    3636        1788 :             fkinfo->ref_relid >= root->simple_rel_array_size)
    3637           0 :             continue;           /* just paranoia */
    3638        1788 :         con_rel = root->simple_rel_array[fkinfo->con_relid];
    3639        1788 :         if (con_rel == NULL)
    3640          12 :             continue;
    3641        1776 :         ref_rel = root->simple_rel_array[fkinfo->ref_relid];
    3642        1776 :         if (ref_rel == NULL)
    3643          24 :             continue;
    3644             : 
    3645             :         /*
    3646             :          * Ignore FK unless both rels are baserels.  This gets rid of FKs that
    3647             :          * link to inheritance child rels (otherrels).
    3648             :          */
    3649        1752 :         if (con_rel->reloptkind != RELOPT_BASEREL ||
    3650        1752 :             ref_rel->reloptkind != RELOPT_BASEREL)
    3651           0 :             continue;
    3652             : 
    3653             :         /*
    3654             :          * Scan the columns and try to match them to eclasses and quals.
    3655             :          *
    3656             :          * Note: for simple inner joins, any match should be in an eclass.
    3657             :          * "Loose" quals that syntactically match an FK equality must have
    3658             :          * been rejected for EC status because they are outer-join quals or
    3659             :          * similar.  We can still consider them to match the FK.
    3660             :          */
    3661        4070 :         for (colno = 0; colno < fkinfo->nkeys; colno++)
    3662             :         {
    3663             :             EquivalenceClass *ec;
    3664             :             AttrNumber  con_attno,
    3665             :                         ref_attno;
    3666             :             Oid         fpeqop;
    3667             :             ListCell   *lc2;
    3668             : 
    3669        2318 :             ec = match_eclasses_to_foreign_key_col(root, fkinfo, colno);
    3670             :             /* Don't bother looking for loose quals if we got an EC match */
    3671        2318 :             if (ec != NULL)
    3672             :             {
    3673         342 :                 fkinfo->nmatched_ec++;
    3674         342 :                 if (ec->ec_has_const)
    3675          74 :                     fkinfo->nconst_ec++;
    3676         342 :                 continue;
    3677             :             }
    3678             : 
    3679             :             /*
    3680             :              * Scan joininfo list for relevant clauses.  Either rel's joininfo
    3681             :              * list would do equally well; we use con_rel's.
    3682             :              */
    3683        1976 :             con_attno = fkinfo->conkey[colno];
    3684        1976 :             ref_attno = fkinfo->confkey[colno];
    3685        1976 :             fpeqop = InvalidOid;    /* we'll look this up only if needed */
    3686             : 
    3687        5168 :             foreach(lc2, con_rel->joininfo)
    3688             :             {
    3689        3192 :                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
    3690        3192 :                 OpExpr     *clause = (OpExpr *) rinfo->clause;
    3691             :                 Var        *leftvar;
    3692             :                 Var        *rightvar;
    3693             : 
    3694             :                 /* Only binary OpExprs are useful for consideration */
    3695        6384 :                 if (!IsA(clause, OpExpr) ||
    3696        3192 :                     list_length(clause->args) != 2)
    3697           0 :                     continue;
    3698        3192 :                 leftvar = (Var *) get_leftop((Expr *) clause);
    3699        3192 :                 rightvar = (Var *) get_rightop((Expr *) clause);
    3700             : 
    3701             :                 /* Operands must be Vars, possibly with RelabelType */
    3702        3438 :                 while (leftvar && IsA(leftvar, RelabelType))
    3703         246 :                     leftvar = (Var *) ((RelabelType *) leftvar)->arg;
    3704        3192 :                 if (!(leftvar && IsA(leftvar, Var)))
    3705           0 :                     continue;
    3706        3420 :                 while (rightvar && IsA(rightvar, RelabelType))
    3707         228 :                     rightvar = (Var *) ((RelabelType *) rightvar)->arg;
    3708        3192 :                 if (!(rightvar && IsA(rightvar, Var)))
    3709          30 :                     continue;
    3710             : 
    3711             :                 /* Now try to match the vars to the current foreign key cols */
    3712        3162 :                 if (fkinfo->ref_relid == leftvar->varno &&
    3713        3036 :                     ref_attno == leftvar->varattno &&
    3714        1730 :                     fkinfo->con_relid == rightvar->varno &&
    3715        1730 :                     con_attno == rightvar->varattno)
    3716             :                 {
    3717             :                     /* Vars match, but is it the right operator? */
    3718        1652 :                     if (clause->opno == fkinfo->conpfeqop[colno])
    3719             :                     {
    3720        1652 :                         fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
    3721             :                                                         rinfo);
    3722        1652 :                         fkinfo->nmatched_ri++;
    3723             :                     }
    3724             :                 }
    3725        1510 :                 else if (fkinfo->ref_relid == rightvar->varno &&
    3726          90 :                          ref_attno == rightvar->varattno &&
    3727          36 :                          fkinfo->con_relid == leftvar->varno &&
    3728          36 :                          con_attno == leftvar->varattno)
    3729             :                 {
    3730             :                     /*
    3731             :                      * Reverse match, must check commutator operator.  Look it
    3732             :                      * up if we didn't already.  (In the worst case we might
    3733             :                      * do multiple lookups here, but that would require an FK
    3734             :                      * equality operator without commutator, which is
    3735             :                      * unlikely.)
    3736             :                      */
    3737          36 :                     if (!OidIsValid(fpeqop))
    3738          36 :                         fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
    3739          36 :                     if (clause->opno == fpeqop)
    3740             :                     {
    3741          36 :                         fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
    3742             :                                                         rinfo);
    3743          36 :                         fkinfo->nmatched_ri++;
    3744             :                     }
    3745             :                 }
    3746             :             }
    3747             :             /* If we found any matching loose quals, count col as matched */
    3748        1976 :             if (fkinfo->rinfos[colno])
    3749        1688 :                 fkinfo->nmatched_rcols++;
    3750             :         }
    3751             : 
    3752             :         /*
    3753             :          * Currently, we drop multicolumn FKs that aren't fully matched to the
    3754             :          * query.  Later we might figure out how to derive some sort of
    3755             :          * estimate from them, in which case this test should be weakened to
    3756             :          * "if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) > 0)".
    3757             :          */
    3758        1752 :         if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) == fkinfo->nkeys)
    3759        1488 :             newlist = lappend(newlist, fkinfo);
    3760             :     }
    3761             :     /* Replace fkey_list, thereby discarding any useless entries */
    3762      314636 :     root->fkey_list = newlist;
    3763      314636 : }
    3764             : 
    3765             : 
    3766             : /*****************************************************************************
    3767             :  *
    3768             :  *   CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
    3769             :  *
    3770             :  *****************************************************************************/
    3771             : 
    3772             : /*
    3773             :  * check_mergejoinable
    3774             :  *    If the restrictinfo's clause is mergejoinable, set the mergejoin
    3775             :  *    info fields in the restrictinfo.
    3776             :  *
    3777             :  *    Currently, we support mergejoin for binary opclauses where
    3778             :  *    the operator is a mergejoinable operator.  The arguments can be
    3779             :  *    anything --- as long as there are no volatile functions in them.
    3780             :  */
    3781             : static void
    3782      627490 : check_mergejoinable(RestrictInfo *restrictinfo)
    3783             : {
    3784      627490 :     Expr       *clause = restrictinfo->clause;
    3785             :     Oid         opno;
    3786             :     Node       *leftarg;
    3787             : 
    3788      627490 :     if (restrictinfo->pseudoconstant)
    3789       10302 :         return;
    3790      617188 :     if (!is_opclause(clause))
    3791       82994 :         return;
    3792      534194 :     if (list_length(((OpExpr *) clause)->args) != 2)
    3793          24 :         return;
    3794             : 
    3795      534170 :     opno = ((OpExpr *) clause)->opno;
    3796      534170 :     leftarg = linitial(((OpExpr *) clause)->args);
    3797             : 
    3798      534170 :     if (op_mergejoinable(opno, exprType(leftarg)) &&
    3799      457058 :         !contain_volatile_functions((Node *) restrictinfo))
    3800      457026 :         restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
    3801             : 
    3802             :     /*
    3803             :      * Note: op_mergejoinable is just a hint; if we fail to find the operator
    3804             :      * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
    3805             :      * is not treated as mergejoinable.
    3806             :      */
    3807             : }
    3808             : 
    3809             : /*
    3810             :  * check_hashjoinable
    3811             :  *    If the restrictinfo's clause is hashjoinable, set the hashjoin
    3812             :  *    info fields in the restrictinfo.
    3813             :  *
    3814             :  *    Currently, we support hashjoin for binary opclauses where
    3815             :  *    the operator is a hashjoinable operator.  The arguments can be
    3816             :  *    anything --- as long as there are no volatile functions in them.
    3817             :  */
    3818             : static void
    3819      140856 : check_hashjoinable(RestrictInfo *restrictinfo)
    3820             : {
    3821      140856 :     Expr       *clause = restrictinfo->clause;
    3822             :     Oid         opno;
    3823             :     Node       *leftarg;
    3824             : 
    3825      140856 :     if (restrictinfo->pseudoconstant)
    3826        3496 :         return;
    3827      137360 :     if (!is_opclause(clause))
    3828        8138 :         return;
    3829      129222 :     if (list_length(((OpExpr *) clause)->args) != 2)
    3830           0 :         return;
    3831             : 
    3832      129222 :     opno = ((OpExpr *) clause)->opno;
    3833      129222 :     leftarg = linitial(((OpExpr *) clause)->args);
    3834             : 
    3835      129222 :     if (op_hashjoinable(opno, exprType(leftarg)) &&
    3836      125914 :         !contain_volatile_functions((Node *) restrictinfo))
    3837      125906 :         restrictinfo->hashjoinoperator = opno;
    3838             : }
    3839             : 
    3840             : /*
    3841             :  * check_memoizable
    3842             :  *    If the restrictinfo's clause is suitable to be used for a Memoize node,
    3843             :  *    set the left_hasheqoperator and right_hasheqoperator to the hash equality
    3844             :  *    operator that will be needed during caching.
    3845             :  */
    3846             : static void
    3847      140856 : check_memoizable(RestrictInfo *restrictinfo)
    3848             : {
    3849             :     TypeCacheEntry *typentry;
    3850      140856 :     Expr       *clause = restrictinfo->clause;
    3851             :     Oid         lefttype;
    3852             :     Oid         righttype;
    3853             : 
    3854      140856 :     if (restrictinfo->pseudoconstant)
    3855        3496 :         return;
    3856      137360 :     if (!is_opclause(clause))
    3857        8138 :         return;
    3858      129222 :     if (list_length(((OpExpr *) clause)->args) != 2)
    3859           0 :         return;
    3860             : 
    3861      129222 :     lefttype = exprType(linitial(((OpExpr *) clause)->args));
    3862             : 
    3863      129222 :     typentry = lookup_type_cache(lefttype, TYPECACHE_HASH_PROC |
    3864             :                                  TYPECACHE_EQ_OPR);
    3865             : 
    3866      129222 :     if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
    3867      128814 :         restrictinfo->left_hasheqoperator = typentry->eq_opr;
    3868             : 
    3869      129222 :     righttype = exprType(lsecond(((OpExpr *) clause)->args));
    3870             : 
    3871             :     /*
    3872             :      * Lookup the right type, unless it's the same as the left type, in which
    3873             :      * case typentry is already pointing to the required TypeCacheEntry.
    3874             :      */
    3875      129222 :     if (lefttype != righttype)
    3876        1940 :         typentry = lookup_type_cache(righttype, TYPECACHE_HASH_PROC |
    3877             :                                      TYPECACHE_EQ_OPR);
    3878             : 
    3879      129222 :     if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
    3880      128610 :         restrictinfo->right_hasheqoperator = typentry->eq_opr;
    3881             : }

Generated by: LCOV version 1.14