LCOV - code coverage report
Current view: top level - src/backend/optimizer/util - relnode.c (source / functions) Hit Total Coverage
Test: PostgreSQL 16beta1 Lines: 734 764 96.1 %
Date: 2023-05-30 23:12:14 Functions: 29 29 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * relnode.c
       4             :  *    Relation-node lookup/construction routines
       5             :  *
       6             :  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/optimizer/util/relnode.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : #include "postgres.h"
      16             : 
      17             : #include <limits.h>
      18             : 
      19             : #include "miscadmin.h"
      20             : #include "nodes/nodeFuncs.h"
      21             : #include "optimizer/appendinfo.h"
      22             : #include "optimizer/clauses.h"
      23             : #include "optimizer/cost.h"
      24             : #include "optimizer/inherit.h"
      25             : #include "optimizer/pathnode.h"
      26             : #include "optimizer/paths.h"
      27             : #include "optimizer/placeholder.h"
      28             : #include "optimizer/plancat.h"
      29             : #include "optimizer/restrictinfo.h"
      30             : #include "optimizer/tlist.h"
      31             : #include "rewrite/rewriteManip.h"
      32             : #include "parser/parse_relation.h"
      33             : #include "utils/hsearch.h"
      34             : #include "utils/lsyscache.h"
      35             : 
      36             : 
      37             : typedef struct JoinHashEntry
      38             : {
      39             :     Relids      join_relids;    /* hash key --- MUST BE FIRST */
      40             :     RelOptInfo *join_rel;
      41             : } JoinHashEntry;
      42             : 
      43             : static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
      44             :                                 RelOptInfo *input_rel,
      45             :                                 SpecialJoinInfo *sjinfo,
      46             :                                 List *pushed_down_joins,
      47             :                                 bool can_null);
      48             : static List *build_joinrel_restrictlist(PlannerInfo *root,
      49             :                                         RelOptInfo *joinrel,
      50             :                                         RelOptInfo *outer_rel,
      51             :                                         RelOptInfo *inner_rel,
      52             :                                         SpecialJoinInfo *sjinfo);
      53             : static void build_joinrel_joinlist(RelOptInfo *joinrel,
      54             :                                    RelOptInfo *outer_rel,
      55             :                                    RelOptInfo *inner_rel);
      56             : static List *subbuild_joinrel_restrictlist(PlannerInfo *root,
      57             :                                            RelOptInfo *joinrel,
      58             :                                            RelOptInfo *input_rel,
      59             :                                            Relids both_input_relids,
      60             :                                            List *new_restrictlist);
      61             : static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
      62             :                                        List *joininfo_list,
      63             :                                        List *new_joininfo);
      64             : static void set_foreign_rel_properties(RelOptInfo *joinrel,
      65             :                                        RelOptInfo *outer_rel, RelOptInfo *inner_rel);
      66             : static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel);
      67             : static void build_joinrel_partition_info(PlannerInfo *root,
      68             :                                          RelOptInfo *joinrel,
      69             :                                          RelOptInfo *outer_rel, RelOptInfo *inner_rel,
      70             :                                          SpecialJoinInfo *sjinfo,
      71             :                                          List *restrictlist);
      72             : static bool have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel,
      73             :                                    RelOptInfo *rel1, RelOptInfo *rel2,
      74             :                                    JoinType jointype, List *restrictlist);
      75             : static int  match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel,
      76             :                                          bool strict_op);
      77             : static void set_joinrel_partition_key_exprs(RelOptInfo *joinrel,
      78             :                                             RelOptInfo *outer_rel, RelOptInfo *inner_rel,
      79             :                                             JoinType jointype);
      80             : static void build_child_join_reltarget(PlannerInfo *root,
      81             :                                        RelOptInfo *parentrel,
      82             :                                        RelOptInfo *childrel,
      83             :                                        int nappinfos,
      84             :                                        AppendRelInfo **appinfos);
      85             : 
      86             : 
      87             : /*
      88             :  * setup_simple_rel_arrays
      89             :  *    Prepare the arrays we use for quickly accessing base relations
      90             :  *    and AppendRelInfos.
      91             :  */
      92             : void
      93      481616 : setup_simple_rel_arrays(PlannerInfo *root)
      94             : {
      95             :     int         size;
      96             :     Index       rti;
      97             :     ListCell   *lc;
      98             : 
      99             :     /* Arrays are accessed using RT indexes (1..N) */
     100      481616 :     size = list_length(root->parse->rtable) + 1;
     101      481616 :     root->simple_rel_array_size = size;
     102             : 
     103             :     /*
     104             :      * simple_rel_array is initialized to all NULLs, since no RelOptInfos
     105             :      * exist yet.  It'll be filled by later calls to build_simple_rel().
     106             :      */
     107      481616 :     root->simple_rel_array = (RelOptInfo **)
     108      481616 :         palloc0(size * sizeof(RelOptInfo *));
     109             : 
     110             :     /* simple_rte_array is an array equivalent of the rtable list */
     111      481616 :     root->simple_rte_array = (RangeTblEntry **)
     112      481616 :         palloc0(size * sizeof(RangeTblEntry *));
     113      481616 :     rti = 1;
     114     1262930 :     foreach(lc, root->parse->rtable)
     115             :     {
     116      781314 :         RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
     117             : 
     118      781314 :         root->simple_rte_array[rti++] = rte;
     119             :     }
     120             : 
     121             :     /* append_rel_array is not needed if there are no AppendRelInfos */
     122      481616 :     if (root->append_rel_list == NIL)
     123             :     {
     124      480202 :         root->append_rel_array = NULL;
     125      480202 :         return;
     126             :     }
     127             : 
     128        1414 :     root->append_rel_array = (AppendRelInfo **)
     129        1414 :         palloc0(size * sizeof(AppendRelInfo *));
     130             : 
     131             :     /*
     132             :      * append_rel_array is filled with any already-existing AppendRelInfos,
     133             :      * which currently could only come from UNION ALL flattening.  We might
     134             :      * add more later during inheritance expansion, but it's the
     135             :      * responsibility of the expansion code to update the array properly.
     136             :      */
     137        4902 :     foreach(lc, root->append_rel_list)
     138             :     {
     139        3488 :         AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc);
     140        3488 :         int         child_relid = appinfo->child_relid;
     141             : 
     142             :         /* Sanity check */
     143             :         Assert(child_relid < size);
     144             : 
     145        3488 :         if (root->append_rel_array[child_relid])
     146           0 :             elog(ERROR, "child relation already exists");
     147             : 
     148        3488 :         root->append_rel_array[child_relid] = appinfo;
     149             :     }
     150             : }
     151             : 
     152             : /*
     153             :  * expand_planner_arrays
     154             :  *      Expand the PlannerInfo's per-RTE arrays by add_size members
     155             :  *      and initialize the newly added entries to NULLs
     156             :  *
     157             :  * Note: this causes the append_rel_array to become allocated even if
     158             :  * it was not before.  This is okay for current uses, because we only call
     159             :  * this when adding child relations, which always have AppendRelInfos.
     160             :  */
     161             : void
     162       17046 : expand_planner_arrays(PlannerInfo *root, int add_size)
     163             : {
     164             :     int         new_size;
     165             : 
     166             :     Assert(add_size > 0);
     167             : 
     168       17046 :     new_size = root->simple_rel_array_size + add_size;
     169             : 
     170       17046 :     root->simple_rel_array =
     171       17046 :         repalloc0_array(root->simple_rel_array, RelOptInfo *, root->simple_rel_array_size, new_size);
     172             : 
     173       17046 :     root->simple_rte_array =
     174       17046 :         repalloc0_array(root->simple_rte_array, RangeTblEntry *, root->simple_rel_array_size, new_size);
     175             : 
     176       17046 :     if (root->append_rel_array)
     177        4862 :         root->append_rel_array =
     178        4862 :             repalloc0_array(root->append_rel_array, AppendRelInfo *, root->simple_rel_array_size, new_size);
     179             :     else
     180       12184 :         root->append_rel_array =
     181       12184 :             palloc0_array(AppendRelInfo *, new_size);
     182             : 
     183       17046 :     root->simple_rel_array_size = new_size;
     184       17046 : }
     185             : 
     186             : /*
     187             :  * build_simple_rel
     188             :  *    Construct a new RelOptInfo for a base relation or 'other' relation.
     189             :  */
     190             : RelOptInfo *
     191      629782 : build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
     192             : {
     193             :     RelOptInfo *rel;
     194             :     RangeTblEntry *rte;
     195             : 
     196             :     /* Rel should not exist already */
     197             :     Assert(relid > 0 && relid < root->simple_rel_array_size);
     198      629782 :     if (root->simple_rel_array[relid] != NULL)
     199           0 :         elog(ERROR, "rel %d already exists", relid);
     200             : 
     201             :     /* Fetch RTE for relation */
     202      629782 :     rte = root->simple_rte_array[relid];
     203             :     Assert(rte != NULL);
     204             : 
     205      629782 :     rel = makeNode(RelOptInfo);
     206      629782 :     rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL;
     207      629782 :     rel->relids = bms_make_singleton(relid);
     208      629782 :     rel->rows = 0;
     209             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
     210      629782 :     rel->consider_startup = (root->tuple_fraction > 0);
     211      629782 :     rel->consider_param_startup = false; /* might get changed later */
     212      629782 :     rel->consider_parallel = false; /* might get changed later */
     213      629782 :     rel->reltarget = create_empty_pathtarget();
     214      629782 :     rel->pathlist = NIL;
     215      629782 :     rel->ppilist = NIL;
     216      629782 :     rel->partial_pathlist = NIL;
     217      629782 :     rel->cheapest_startup_path = NULL;
     218      629782 :     rel->cheapest_total_path = NULL;
     219      629782 :     rel->cheapest_unique_path = NULL;
     220      629782 :     rel->cheapest_parameterized_paths = NIL;
     221      629782 :     rel->relid = relid;
     222      629782 :     rel->rtekind = rte->rtekind;
     223             :     /* min_attr, max_attr, attr_needed, attr_widths are set below */
     224      629782 :     rel->lateral_vars = NIL;
     225      629782 :     rel->indexlist = NIL;
     226      629782 :     rel->statlist = NIL;
     227      629782 :     rel->pages = 0;
     228      629782 :     rel->tuples = 0;
     229      629782 :     rel->allvisfrac = 0;
     230      629782 :     rel->eclass_indexes = NULL;
     231      629782 :     rel->subroot = NULL;
     232      629782 :     rel->subplan_params = NIL;
     233      629782 :     rel->rel_parallel_workers = -1; /* set up in get_relation_info */
     234      629782 :     rel->amflags = 0;
     235      629782 :     rel->serverid = InvalidOid;
     236      629782 :     if (rte->rtekind == RTE_RELATION)
     237             :     {
     238             :         Assert(parent == NULL ||
     239             :                parent->rtekind == RTE_RELATION ||
     240             :                parent->rtekind == RTE_SUBQUERY);
     241             : 
     242             :         /*
     243             :          * For any RELATION rte, we need a userid with which to check
     244             :          * permission access. Baserels simply use their own
     245             :          * RTEPermissionInfo's checkAsUser.
     246             :          *
     247             :          * For otherrels normally there's no RTEPermissionInfo, so we use the
     248             :          * parent's, which normally has one. The exceptional case is that the
     249             :          * parent is a subquery, in which case the otherrel will have its own.
     250             :          */
     251      367156 :         if (rel->reloptkind == RELOPT_BASEREL ||
     252       37062 :             (rel->reloptkind == RELOPT_OTHER_MEMBER_REL &&
     253       37062 :              parent->rtekind == RTE_SUBQUERY))
     254      331078 :         {
     255             :             RTEPermissionInfo *perminfo;
     256             : 
     257      331078 :             perminfo = getRTEPermissionInfo(root->parse->rteperminfos, rte);
     258      331078 :             rel->userid = perminfo->checkAsUser;
     259             :         }
     260             :         else
     261       36078 :             rel->userid = parent->userid;
     262             :     }
     263             :     else
     264      262626 :         rel->userid = InvalidOid;
     265      629782 :     rel->useridiscurrent = false;
     266      629782 :     rel->fdwroutine = NULL;
     267      629782 :     rel->fdw_private = NULL;
     268      629782 :     rel->unique_for_rels = NIL;
     269      629782 :     rel->non_unique_for_rels = NIL;
     270      629782 :     rel->baserestrictinfo = NIL;
     271      629782 :     rel->baserestrictcost.startup = 0;
     272      629782 :     rel->baserestrictcost.per_tuple = 0;
     273      629782 :     rel->baserestrict_min_security = UINT_MAX;
     274      629782 :     rel->joininfo = NIL;
     275      629782 :     rel->has_eclass_joins = false;
     276      629782 :     rel->consider_partitionwise_join = false;    /* might get changed later */
     277      629782 :     rel->part_scheme = NULL;
     278      629782 :     rel->nparts = -1;
     279      629782 :     rel->boundinfo = NULL;
     280      629782 :     rel->partbounds_merged = false;
     281      629782 :     rel->partition_qual = NIL;
     282      629782 :     rel->part_rels = NULL;
     283      629782 :     rel->live_parts = NULL;
     284      629782 :     rel->all_partrels = NULL;
     285      629782 :     rel->partexprs = NULL;
     286      629782 :     rel->nullable_partexprs = NULL;
     287             : 
     288             :     /*
     289             :      * Pass assorted information down the inheritance hierarchy.
     290             :      */
     291      629782 :     if (parent)
     292             :     {
     293             :         /* We keep back-links to immediate parent and topmost parent. */
     294       39566 :         rel->parent = parent;
     295       39566 :         rel->top_parent = parent->top_parent ? parent->top_parent : parent;
     296       39566 :         rel->top_parent_relids = rel->top_parent->relids;
     297             : 
     298             :         /*
     299             :          * A child rel is below the same outer joins as its parent.  (We
     300             :          * presume this info was already calculated for the parent.)
     301             :          */
     302       39566 :         rel->nulling_relids = parent->nulling_relids;
     303             : 
     304             :         /*
     305             :          * Also propagate lateral-reference information from appendrel parent
     306             :          * rels to their child rels.  We intentionally give each child rel the
     307             :          * same minimum parameterization, even though it's quite possible that
     308             :          * some don't reference all the lateral rels.  This is because any
     309             :          * append path for the parent will have to have the same
     310             :          * parameterization for every child anyway, and there's no value in
     311             :          * forcing extra reparameterize_path() calls.  Similarly, a lateral
     312             :          * reference to the parent prevents use of otherwise-movable join rels
     313             :          * for each child.
     314             :          *
     315             :          * It's possible for child rels to have their own children, in which
     316             :          * case the topmost parent's lateral info propagates all the way down.
     317             :          */
     318       39566 :         rel->direct_lateral_relids = parent->direct_lateral_relids;
     319       39566 :         rel->lateral_relids = parent->lateral_relids;
     320       39566 :         rel->lateral_referencers = parent->lateral_referencers;
     321             :     }
     322             :     else
     323             :     {
     324      590216 :         rel->parent = NULL;
     325      590216 :         rel->top_parent = NULL;
     326      590216 :         rel->top_parent_relids = NULL;
     327      590216 :         rel->nulling_relids = NULL;
     328      590216 :         rel->direct_lateral_relids = NULL;
     329      590216 :         rel->lateral_relids = NULL;
     330      590216 :         rel->lateral_referencers = NULL;
     331             :     }
     332             : 
     333             :     /* Check type of rtable entry */
     334      629782 :     switch (rte->rtekind)
     335             :     {
     336      367156 :         case RTE_RELATION:
     337             :             /* Table --- retrieve statistics from the system catalogs */
     338      367156 :             get_relation_info(root, rte->relid, rte->inh, rel);
     339      367142 :             break;
     340       67592 :         case RTE_SUBQUERY:
     341             :         case RTE_FUNCTION:
     342             :         case RTE_TABLEFUNC:
     343             :         case RTE_VALUES:
     344             :         case RTE_CTE:
     345             :         case RTE_NAMEDTUPLESTORE:
     346             : 
     347             :             /*
     348             :              * Subquery, function, tablefunc, values list, CTE, or ENR --- set
     349             :              * up attr range and arrays
     350             :              *
     351             :              * Note: 0 is included in range to support whole-row Vars
     352             :              */
     353       67592 :             rel->min_attr = 0;
     354       67592 :             rel->max_attr = list_length(rte->eref->colnames);
     355       67592 :             rel->attr_needed = (Relids *)
     356       67592 :                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
     357       67592 :             rel->attr_widths = (int32 *)
     358       67592 :                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
     359       67592 :             break;
     360      195034 :         case RTE_RESULT:
     361             :             /* RTE_RESULT has no columns, nor could it have whole-row Var */
     362      195034 :             rel->min_attr = 0;
     363      195034 :             rel->max_attr = -1;
     364      195034 :             rel->attr_needed = NULL;
     365      195034 :             rel->attr_widths = NULL;
     366      195034 :             break;
     367           0 :         default:
     368           0 :             elog(ERROR, "unrecognized RTE kind: %d",
     369             :                  (int) rte->rtekind);
     370             :             break;
     371             :     }
     372             : 
     373             :     /*
     374             :      * Copy the parent's quals to the child, with appropriate substitution of
     375             :      * variables.  If any constant false or NULL clauses turn up, we can mark
     376             :      * the child as dummy right away.  (We must do this immediately so that
     377             :      * pruning works correctly when recursing in expand_partitioned_rtentry.)
     378             :      */
     379      629768 :     if (parent)
     380             :     {
     381       39566 :         AppendRelInfo *appinfo = root->append_rel_array[relid];
     382             : 
     383             :         Assert(appinfo != NULL);
     384       39566 :         if (!apply_child_basequals(root, parent, rel, rte, appinfo))
     385             :         {
     386             :             /*
     387             :              * Some restriction clause reduced to constant FALSE or NULL after
     388             :              * substitution, so this child need not be scanned.
     389             :              */
     390          78 :             mark_dummy_rel(rel);
     391             :         }
     392             :     }
     393             : 
     394             :     /* Save the finished struct in the query's simple_rel_array */
     395      629768 :     root->simple_rel_array[relid] = rel;
     396             : 
     397      629768 :     return rel;
     398             : }
     399             : 
     400             : /*
     401             :  * find_base_rel
     402             :  *    Find a base or otherrel relation entry, which must already exist.
     403             :  */
     404             : RelOptInfo *
     405     5407092 : find_base_rel(PlannerInfo *root, int relid)
     406             : {
     407             :     RelOptInfo *rel;
     408             : 
     409             :     Assert(relid > 0);
     410             : 
     411     5407092 :     if (relid < root->simple_rel_array_size)
     412             :     {
     413     5407092 :         rel = root->simple_rel_array[relid];
     414     5407092 :         if (rel)
     415     5407092 :             return rel;
     416             :     }
     417             : 
     418           0 :     elog(ERROR, "no relation entry for relid %d", relid);
     419             : 
     420             :     return NULL;                /* keep compiler quiet */
     421             : }
     422             : 
     423             : /*
     424             :  * find_base_rel_ignore_join
     425             :  *    Find a base or otherrel relation entry, which must already exist.
     426             :  *
     427             :  * Unlike find_base_rel, if relid references an outer join then this
     428             :  * will return NULL rather than raising an error.  This is convenient
     429             :  * for callers that must deal with relid sets including both base and
     430             :  * outer joins.
     431             :  */
     432             : RelOptInfo *
     433      143162 : find_base_rel_ignore_join(PlannerInfo *root, int relid)
     434             : {
     435             :     Assert(relid > 0);
     436             : 
     437      143162 :     if (relid < root->simple_rel_array_size)
     438             :     {
     439             :         RelOptInfo *rel;
     440             :         RangeTblEntry *rte;
     441             : 
     442      143162 :         rel = root->simple_rel_array[relid];
     443      143162 :         if (rel)
     444      126840 :             return rel;
     445             : 
     446             :         /*
     447             :          * We could just return NULL here, but for debugging purposes it seems
     448             :          * best to actually verify that the relid is an outer join and not
     449             :          * something weird.
     450             :          */
     451       16322 :         rte = root->simple_rte_array[relid];
     452       16322 :         if (rte && rte->rtekind == RTE_JOIN && rte->jointype != JOIN_INNER)
     453       16322 :             return NULL;
     454             :     }
     455             : 
     456           0 :     elog(ERROR, "no relation entry for relid %d", relid);
     457             : 
     458             :     return NULL;                /* keep compiler quiet */
     459             : }
     460             : 
     461             : /*
     462             :  * build_join_rel_hash
     463             :  *    Construct the auxiliary hash table for join relations.
     464             :  */
     465             : static void
     466          38 : build_join_rel_hash(PlannerInfo *root)
     467             : {
     468             :     HTAB       *hashtab;
     469             :     HASHCTL     hash_ctl;
     470             :     ListCell   *l;
     471             : 
     472             :     /* Create the hash table */
     473          38 :     hash_ctl.keysize = sizeof(Relids);
     474          38 :     hash_ctl.entrysize = sizeof(JoinHashEntry);
     475          38 :     hash_ctl.hash = bitmap_hash;
     476          38 :     hash_ctl.match = bitmap_match;
     477          38 :     hash_ctl.hcxt = CurrentMemoryContext;
     478          38 :     hashtab = hash_create("JoinRelHashTable",
     479             :                           256L,
     480             :                           &hash_ctl,
     481             :                           HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
     482             : 
     483             :     /* Insert all the already-existing joinrels */
     484        1292 :     foreach(l, root->join_rel_list)
     485             :     {
     486        1254 :         RelOptInfo *rel = (RelOptInfo *) lfirst(l);
     487             :         JoinHashEntry *hentry;
     488             :         bool        found;
     489             : 
     490        1254 :         hentry = (JoinHashEntry *) hash_search(hashtab,
     491        1254 :                                                &(rel->relids),
     492             :                                                HASH_ENTER,
     493             :                                                &found);
     494             :         Assert(!found);
     495        1254 :         hentry->join_rel = rel;
     496             :     }
     497             : 
     498          38 :     root->join_rel_hash = hashtab;
     499          38 : }
     500             : 
     501             : /*
     502             :  * find_join_rel
     503             :  *    Returns relation entry corresponding to 'relids' (a set of RT indexes),
     504             :  *    or NULL if none exists.  This is for join relations.
     505             :  */
     506             : RelOptInfo *
     507      224106 : find_join_rel(PlannerInfo *root, Relids relids)
     508             : {
     509             :     /*
     510             :      * Switch to using hash lookup when list grows "too long".  The threshold
     511             :      * is arbitrary and is known only here.
     512             :      */
     513      224106 :     if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
     514          38 :         build_join_rel_hash(root);
     515             : 
     516             :     /*
     517             :      * Use either hashtable lookup or linear search, as appropriate.
     518             :      *
     519             :      * Note: the seemingly redundant hashkey variable is used to avoid taking
     520             :      * the address of relids; unless the compiler is exceedingly smart, doing
     521             :      * so would force relids out of a register and thus probably slow down the
     522             :      * list-search case.
     523             :      */
     524      224106 :     if (root->join_rel_hash)
     525             :     {
     526        3624 :         Relids      hashkey = relids;
     527             :         JoinHashEntry *hentry;
     528             : 
     529        3624 :         hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
     530             :                                                &hashkey,
     531             :                                                HASH_FIND,
     532             :                                                NULL);
     533        3624 :         if (hentry)
     534        3204 :             return hentry->join_rel;
     535             :     }
     536             :     else
     537             :     {
     538             :         ListCell   *l;
     539             : 
     540     1300554 :         foreach(l, root->join_rel_list)
     541             :         {
     542     1154978 :             RelOptInfo *rel = (RelOptInfo *) lfirst(l);
     543             : 
     544     1154978 :             if (bms_equal(rel->relids, relids))
     545       74906 :                 return rel;
     546             :         }
     547             :     }
     548             : 
     549      145996 :     return NULL;
     550             : }
     551             : 
     552             : /*
     553             :  * set_foreign_rel_properties
     554             :  *      Set up foreign-join fields if outer and inner relation are foreign
     555             :  *      tables (or joins) belonging to the same server and assigned to the same
     556             :  *      user to check access permissions as.
     557             :  *
     558             :  * In addition to an exact match of userid, we allow the case where one side
     559             :  * has zero userid (implying current user) and the other side has explicit
     560             :  * userid that happens to equal the current user; but in that case, pushdown of
     561             :  * the join is only valid for the current user.  The useridiscurrent field
     562             :  * records whether we had to make such an assumption for this join or any
     563             :  * sub-join.
     564             :  *
     565             :  * Otherwise these fields are left invalid, so GetForeignJoinPaths will not be
     566             :  * called for the join relation.
     567             :  */
     568             : static void
     569      148582 : set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel,
     570             :                            RelOptInfo *inner_rel)
     571             : {
     572      148582 :     if (OidIsValid(outer_rel->serverid) &&
     573         584 :         inner_rel->serverid == outer_rel->serverid)
     574             :     {
     575         512 :         if (inner_rel->userid == outer_rel->userid)
     576             :         {
     577         500 :             joinrel->serverid = outer_rel->serverid;
     578         500 :             joinrel->userid = outer_rel->userid;
     579         500 :             joinrel->useridiscurrent = outer_rel->useridiscurrent || inner_rel->useridiscurrent;
     580         500 :             joinrel->fdwroutine = outer_rel->fdwroutine;
     581             :         }
     582          20 :         else if (!OidIsValid(inner_rel->userid) &&
     583           8 :                  outer_rel->userid == GetUserId())
     584             :         {
     585           4 :             joinrel->serverid = outer_rel->serverid;
     586           4 :             joinrel->userid = outer_rel->userid;
     587           4 :             joinrel->useridiscurrent = true;
     588           4 :             joinrel->fdwroutine = outer_rel->fdwroutine;
     589             :         }
     590           8 :         else if (!OidIsValid(outer_rel->userid) &&
     591           0 :                  inner_rel->userid == GetUserId())
     592             :         {
     593           0 :             joinrel->serverid = outer_rel->serverid;
     594           0 :             joinrel->userid = inner_rel->userid;
     595           0 :             joinrel->useridiscurrent = true;
     596           0 :             joinrel->fdwroutine = outer_rel->fdwroutine;
     597             :         }
     598             :     }
     599      148582 : }
     600             : 
     601             : /*
     602             :  * add_join_rel
     603             :  *      Add given join relation to the list of join relations in the given
     604             :  *      PlannerInfo. Also add it to the auxiliary hashtable if there is one.
     605             :  */
     606             : static void
     607      148582 : add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
     608             : {
     609             :     /* GEQO requires us to append the new joinrel to the end of the list! */
     610      148582 :     root->join_rel_list = lappend(root->join_rel_list, joinrel);
     611             : 
     612             :     /* store it into the auxiliary hashtable if there is one. */
     613      148582 :     if (root->join_rel_hash)
     614             :     {
     615             :         JoinHashEntry *hentry;
     616             :         bool        found;
     617             : 
     618         420 :         hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
     619         420 :                                                &(joinrel->relids),
     620             :                                                HASH_ENTER,
     621             :                                                &found);
     622             :         Assert(!found);
     623         420 :         hentry->join_rel = joinrel;
     624             :     }
     625      148582 : }
     626             : 
     627             : /*
     628             :  * build_join_rel
     629             :  *    Returns relation entry corresponding to the union of two given rels,
     630             :  *    creating a new relation entry if none already exists.
     631             :  *
     632             :  * 'joinrelids' is the Relids set that uniquely identifies the join
     633             :  * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
     634             :  *      joined
     635             :  * 'sjinfo': join context info
     636             :  * 'pushed_down_joins': any pushed-down outer joins that are now completed
     637             :  * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
     638             :  *      receives the list of RestrictInfo nodes that apply to this
     639             :  *      particular pair of joinable relations.
     640             :  *
     641             :  * restrictlist_ptr makes the routine's API a little grotty, but it saves
     642             :  * duplicated calculation of the restrictlist...
     643             :  */
     644             : RelOptInfo *
     645      220310 : build_join_rel(PlannerInfo *root,
     646             :                Relids joinrelids,
     647             :                RelOptInfo *outer_rel,
     648             :                RelOptInfo *inner_rel,
     649             :                SpecialJoinInfo *sjinfo,
     650             :                List *pushed_down_joins,
     651             :                List **restrictlist_ptr)
     652             : {
     653             :     RelOptInfo *joinrel;
     654             :     List       *restrictlist;
     655             : 
     656             :     /* This function should be used only for join between parents. */
     657             :     Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel));
     658             : 
     659             :     /*
     660             :      * See if we already have a joinrel for this set of base rels.
     661             :      */
     662      220310 :     joinrel = find_join_rel(root, joinrelids);
     663             : 
     664      220310 :     if (joinrel)
     665             :     {
     666             :         /*
     667             :          * Yes, so we only need to figure the restrictlist for this particular
     668             :          * pair of component relations.
     669             :          */
     670       76028 :         if (restrictlist_ptr)
     671       76028 :             *restrictlist_ptr = build_joinrel_restrictlist(root,
     672             :                                                            joinrel,
     673             :                                                            outer_rel,
     674             :                                                            inner_rel,
     675             :                                                            sjinfo);
     676       76028 :         return joinrel;
     677             :     }
     678             : 
     679             :     /*
     680             :      * Nope, so make one.
     681             :      */
     682      144282 :     joinrel = makeNode(RelOptInfo);
     683      144282 :     joinrel->reloptkind = RELOPT_JOINREL;
     684      144282 :     joinrel->relids = bms_copy(joinrelids);
     685      144282 :     joinrel->rows = 0;
     686             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
     687      144282 :     joinrel->consider_startup = (root->tuple_fraction > 0);
     688      144282 :     joinrel->consider_param_startup = false;
     689      144282 :     joinrel->consider_parallel = false;
     690      144282 :     joinrel->reltarget = create_empty_pathtarget();
     691      144282 :     joinrel->pathlist = NIL;
     692      144282 :     joinrel->ppilist = NIL;
     693      144282 :     joinrel->partial_pathlist = NIL;
     694      144282 :     joinrel->cheapest_startup_path = NULL;
     695      144282 :     joinrel->cheapest_total_path = NULL;
     696      144282 :     joinrel->cheapest_unique_path = NULL;
     697      144282 :     joinrel->cheapest_parameterized_paths = NIL;
     698             :     /* init direct_lateral_relids from children; we'll finish it up below */
     699      144282 :     joinrel->direct_lateral_relids =
     700      144282 :         bms_union(outer_rel->direct_lateral_relids,
     701      144282 :                   inner_rel->direct_lateral_relids);
     702      144282 :     joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids,
     703             :                                                         outer_rel, inner_rel);
     704      144282 :     joinrel->relid = 0;          /* indicates not a baserel */
     705      144282 :     joinrel->rtekind = RTE_JOIN;
     706      144282 :     joinrel->min_attr = 0;
     707      144282 :     joinrel->max_attr = 0;
     708      144282 :     joinrel->attr_needed = NULL;
     709      144282 :     joinrel->attr_widths = NULL;
     710      144282 :     joinrel->nulling_relids = NULL;
     711      144282 :     joinrel->lateral_vars = NIL;
     712      144282 :     joinrel->lateral_referencers = NULL;
     713      144282 :     joinrel->indexlist = NIL;
     714      144282 :     joinrel->statlist = NIL;
     715      144282 :     joinrel->pages = 0;
     716      144282 :     joinrel->tuples = 0;
     717      144282 :     joinrel->allvisfrac = 0;
     718      144282 :     joinrel->eclass_indexes = NULL;
     719      144282 :     joinrel->subroot = NULL;
     720      144282 :     joinrel->subplan_params = NIL;
     721      144282 :     joinrel->rel_parallel_workers = -1;
     722      144282 :     joinrel->amflags = 0;
     723      144282 :     joinrel->serverid = InvalidOid;
     724      144282 :     joinrel->userid = InvalidOid;
     725      144282 :     joinrel->useridiscurrent = false;
     726      144282 :     joinrel->fdwroutine = NULL;
     727      144282 :     joinrel->fdw_private = NULL;
     728      144282 :     joinrel->unique_for_rels = NIL;
     729      144282 :     joinrel->non_unique_for_rels = NIL;
     730      144282 :     joinrel->baserestrictinfo = NIL;
     731      144282 :     joinrel->baserestrictcost.startup = 0;
     732      144282 :     joinrel->baserestrictcost.per_tuple = 0;
     733      144282 :     joinrel->baserestrict_min_security = UINT_MAX;
     734      144282 :     joinrel->joininfo = NIL;
     735      144282 :     joinrel->has_eclass_joins = false;
     736      144282 :     joinrel->consider_partitionwise_join = false;    /* might get changed later */
     737      144282 :     joinrel->parent = NULL;
     738      144282 :     joinrel->top_parent = NULL;
     739      144282 :     joinrel->top_parent_relids = NULL;
     740      144282 :     joinrel->part_scheme = NULL;
     741      144282 :     joinrel->nparts = -1;
     742      144282 :     joinrel->boundinfo = NULL;
     743      144282 :     joinrel->partbounds_merged = false;
     744      144282 :     joinrel->partition_qual = NIL;
     745      144282 :     joinrel->part_rels = NULL;
     746      144282 :     joinrel->live_parts = NULL;
     747      144282 :     joinrel->all_partrels = NULL;
     748      144282 :     joinrel->partexprs = NULL;
     749      144282 :     joinrel->nullable_partexprs = NULL;
     750             : 
     751             :     /* Compute information relevant to the foreign relations. */
     752      144282 :     set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
     753             : 
     754             :     /*
     755             :      * Fill the joinrel's tlist with just the Vars and PHVs that need to be
     756             :      * output from this join (ie, are needed for higher joinclauses or final
     757             :      * output).
     758             :      *
     759             :      * NOTE: the tlist order for a join rel will depend on which pair of outer
     760             :      * and inner rels we first try to build it from.  But the contents should
     761             :      * be the same regardless.
     762             :      */
     763      144282 :     build_joinrel_tlist(root, joinrel, outer_rel, sjinfo, pushed_down_joins,
     764      144282 :                         (sjinfo->jointype == JOIN_FULL));
     765      144282 :     build_joinrel_tlist(root, joinrel, inner_rel, sjinfo, pushed_down_joins,
     766      144282 :                         (sjinfo->jointype != JOIN_INNER));
     767      144282 :     add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel, sjinfo);
     768             : 
     769             :     /*
     770             :      * add_placeholders_to_joinrel also took care of adding the ph_lateral
     771             :      * sets of any PlaceHolderVars computed here to direct_lateral_relids, so
     772             :      * now we can finish computing that.  This is much like the computation of
     773             :      * the transitively-closed lateral_relids in min_join_parameterization,
     774             :      * except that here we *do* have to consider the added PHVs.
     775             :      */
     776      144282 :     joinrel->direct_lateral_relids =
     777      144282 :         bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
     778             : 
     779             :     /*
     780             :      * Construct restrict and join clause lists for the new joinrel. (The
     781             :      * caller might or might not need the restrictlist, but I need it anyway
     782             :      * for set_joinrel_size_estimates().)
     783             :      */
     784      144282 :     restrictlist = build_joinrel_restrictlist(root, joinrel,
     785             :                                               outer_rel, inner_rel,
     786             :                                               sjinfo);
     787      144282 :     if (restrictlist_ptr)
     788      144282 :         *restrictlist_ptr = restrictlist;
     789      144282 :     build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
     790             : 
     791             :     /*
     792             :      * This is also the right place to check whether the joinrel has any
     793             :      * pending EquivalenceClass joins.
     794             :      */
     795      144282 :     joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
     796             : 
     797             :     /* Store the partition information. */
     798      144282 :     build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel, sjinfo,
     799             :                                  restrictlist);
     800             : 
     801             :     /*
     802             :      * Set estimates of the joinrel's size.
     803             :      */
     804      144282 :     set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
     805             :                                sjinfo, restrictlist);
     806             : 
     807             :     /*
     808             :      * Set the consider_parallel flag if this joinrel could potentially be
     809             :      * scanned within a parallel worker.  If this flag is false for either
     810             :      * inner_rel or outer_rel, then it must be false for the joinrel also.
     811             :      * Even if both are true, there might be parallel-restricted expressions
     812             :      * in the targetlist or quals.
     813             :      *
     814             :      * Note that if there are more than two rels in this relation, they could
     815             :      * be divided between inner_rel and outer_rel in any arbitrary way.  We
     816             :      * assume this doesn't matter, because we should hit all the same baserels
     817             :      * and joinclauses while building up to this joinrel no matter which we
     818             :      * take; therefore, we should make the same decision here however we get
     819             :      * here.
     820             :      */
     821      259030 :     if (inner_rel->consider_parallel && outer_rel->consider_parallel &&
     822      229192 :         is_parallel_safe(root, (Node *) restrictlist) &&
     823      114444 :         is_parallel_safe(root, (Node *) joinrel->reltarget->exprs))
     824      114438 :         joinrel->consider_parallel = true;
     825             : 
     826             :     /* Add the joinrel to the PlannerInfo. */
     827      144282 :     add_join_rel(root, joinrel);
     828             : 
     829             :     /*
     830             :      * Also, if dynamic-programming join search is active, add the new joinrel
     831             :      * to the appropriate sublist.  Note: you might think the Assert on number
     832             :      * of members should be for equality, but some of the level 1 rels might
     833             :      * have been joinrels already, so we can only assert <=.
     834             :      */
     835      144282 :     if (root->join_rel_level)
     836             :     {
     837             :         Assert(root->join_cur_level > 0);
     838             :         Assert(root->join_cur_level <= bms_num_members(joinrel->relids));
     839      141186 :         root->join_rel_level[root->join_cur_level] =
     840      141186 :             lappend(root->join_rel_level[root->join_cur_level], joinrel);
     841             :     }
     842             : 
     843      144282 :     return joinrel;
     844             : }
     845             : 
     846             : /*
     847             :  * build_child_join_rel
     848             :  *    Builds RelOptInfo representing join between given two child relations.
     849             :  *
     850             :  * 'outer_rel' and 'inner_rel' are the RelOptInfos of child relations being
     851             :  *      joined
     852             :  * 'parent_joinrel' is the RelOptInfo representing the join between parent
     853             :  *      relations. Some of the members of new RelOptInfo are produced by
     854             :  *      translating corresponding members of this RelOptInfo
     855             :  * 'restrictlist': list of RestrictInfo nodes that apply to this particular
     856             :  *      pair of joinable relations
     857             :  * 'sjinfo': child join's join-type details
     858             :  */
     859             : RelOptInfo *
     860        4300 : build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
     861             :                      RelOptInfo *inner_rel, RelOptInfo *parent_joinrel,
     862             :                      List *restrictlist, SpecialJoinInfo *sjinfo)
     863             : {
     864        4300 :     RelOptInfo *joinrel = makeNode(RelOptInfo);
     865             :     AppendRelInfo **appinfos;
     866             :     int         nappinfos;
     867             : 
     868             :     /* Only joins between "other" relations land here. */
     869             :     Assert(IS_OTHER_REL(outer_rel) && IS_OTHER_REL(inner_rel));
     870             : 
     871             :     /* The parent joinrel should have consider_partitionwise_join set. */
     872             :     Assert(parent_joinrel->consider_partitionwise_join);
     873             : 
     874        4300 :     joinrel->reloptkind = RELOPT_OTHER_JOINREL;
     875        4300 :     joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids);
     876        4300 :     joinrel->relids = add_outer_joins_to_relids(root, joinrel->relids, sjinfo,
     877             :                                                 NULL);
     878        4300 :     joinrel->rows = 0;
     879             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
     880        4300 :     joinrel->consider_startup = (root->tuple_fraction > 0);
     881        4300 :     joinrel->consider_param_startup = false;
     882        4300 :     joinrel->consider_parallel = false;
     883        4300 :     joinrel->reltarget = create_empty_pathtarget();
     884        4300 :     joinrel->pathlist = NIL;
     885        4300 :     joinrel->ppilist = NIL;
     886        4300 :     joinrel->partial_pathlist = NIL;
     887        4300 :     joinrel->cheapest_startup_path = NULL;
     888        4300 :     joinrel->cheapest_total_path = NULL;
     889        4300 :     joinrel->cheapest_unique_path = NULL;
     890        4300 :     joinrel->cheapest_parameterized_paths = NIL;
     891        4300 :     joinrel->direct_lateral_relids = NULL;
     892        4300 :     joinrel->lateral_relids = NULL;
     893        4300 :     joinrel->relid = 0;          /* indicates not a baserel */
     894        4300 :     joinrel->rtekind = RTE_JOIN;
     895        4300 :     joinrel->min_attr = 0;
     896        4300 :     joinrel->max_attr = 0;
     897        4300 :     joinrel->attr_needed = NULL;
     898        4300 :     joinrel->attr_widths = NULL;
     899        4300 :     joinrel->nulling_relids = NULL;
     900        4300 :     joinrel->lateral_vars = NIL;
     901        4300 :     joinrel->lateral_referencers = NULL;
     902        4300 :     joinrel->indexlist = NIL;
     903        4300 :     joinrel->pages = 0;
     904        4300 :     joinrel->tuples = 0;
     905        4300 :     joinrel->allvisfrac = 0;
     906        4300 :     joinrel->eclass_indexes = NULL;
     907        4300 :     joinrel->subroot = NULL;
     908        4300 :     joinrel->subplan_params = NIL;
     909        4300 :     joinrel->amflags = 0;
     910        4300 :     joinrel->serverid = InvalidOid;
     911        4300 :     joinrel->userid = InvalidOid;
     912        4300 :     joinrel->useridiscurrent = false;
     913        4300 :     joinrel->fdwroutine = NULL;
     914        4300 :     joinrel->fdw_private = NULL;
     915        4300 :     joinrel->baserestrictinfo = NIL;
     916        4300 :     joinrel->baserestrictcost.startup = 0;
     917        4300 :     joinrel->baserestrictcost.per_tuple = 0;
     918        4300 :     joinrel->joininfo = NIL;
     919        4300 :     joinrel->has_eclass_joins = false;
     920        4300 :     joinrel->consider_partitionwise_join = false;    /* might get changed later */
     921        4300 :     joinrel->parent = parent_joinrel;
     922        4300 :     joinrel->top_parent = parent_joinrel->top_parent ? parent_joinrel->top_parent : parent_joinrel;
     923        4300 :     joinrel->top_parent_relids = joinrel->top_parent->relids;
     924        4300 :     joinrel->part_scheme = NULL;
     925        4300 :     joinrel->nparts = -1;
     926        4300 :     joinrel->boundinfo = NULL;
     927        4300 :     joinrel->partbounds_merged = false;
     928        4300 :     joinrel->partition_qual = NIL;
     929        4300 :     joinrel->part_rels = NULL;
     930        4300 :     joinrel->live_parts = NULL;
     931        4300 :     joinrel->all_partrels = NULL;
     932        4300 :     joinrel->partexprs = NULL;
     933        4300 :     joinrel->nullable_partexprs = NULL;
     934             : 
     935             :     /* Compute information relevant to foreign relations. */
     936        4300 :     set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
     937             : 
     938             :     /* Compute information needed for mapping Vars to the child rel */
     939        4300 :     appinfos = find_appinfos_by_relids(root, joinrel->relids, &nappinfos);
     940             : 
     941             :     /* Set up reltarget struct */
     942        4300 :     build_child_join_reltarget(root, parent_joinrel, joinrel,
     943             :                                nappinfos, appinfos);
     944             : 
     945             :     /* Construct joininfo list. */
     946        8600 :     joinrel->joininfo = (List *) adjust_appendrel_attrs(root,
     947        4300 :                                                         (Node *) parent_joinrel->joininfo,
     948             :                                                         nappinfos,
     949             :                                                         appinfos);
     950             : 
     951             :     /*
     952             :      * Lateral relids referred in child join will be same as that referred in
     953             :      * the parent relation.
     954             :      */
     955        4300 :     joinrel->direct_lateral_relids = (Relids) bms_copy(parent_joinrel->direct_lateral_relids);
     956        4300 :     joinrel->lateral_relids = (Relids) bms_copy(parent_joinrel->lateral_relids);
     957             : 
     958             :     /*
     959             :      * If the parent joinrel has pending equivalence classes, so does the
     960             :      * child.
     961             :      */
     962        4300 :     joinrel->has_eclass_joins = parent_joinrel->has_eclass_joins;
     963             : 
     964             :     /* Is the join between partitions itself partitioned? */
     965        4300 :     build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel, sjinfo,
     966             :                                  restrictlist);
     967             : 
     968             :     /* Child joinrel is parallel safe if parent is parallel safe. */
     969        4300 :     joinrel->consider_parallel = parent_joinrel->consider_parallel;
     970             : 
     971             :     /* Set estimates of the child-joinrel's size. */
     972        4300 :     set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
     973             :                                sjinfo, restrictlist);
     974             : 
     975             :     /* We build the join only once. */
     976             :     Assert(!find_join_rel(root, joinrel->relids));
     977             : 
     978             :     /* Add the relation to the PlannerInfo. */
     979        4300 :     add_join_rel(root, joinrel);
     980             : 
     981             :     /*
     982             :      * We might need EquivalenceClass members corresponding to the child join,
     983             :      * so that we can represent sort pathkeys for it.  As with children of
     984             :      * baserels, we shouldn't need this unless there are relevant eclass joins
     985             :      * (implying that a merge join might be possible) or pathkeys to sort by.
     986             :      */
     987        4300 :     if (joinrel->has_eclass_joins || has_useful_pathkeys(root, parent_joinrel))
     988        4108 :         add_child_join_rel_equivalences(root,
     989             :                                         nappinfos, appinfos,
     990             :                                         parent_joinrel, joinrel);
     991             : 
     992        4300 :     pfree(appinfos);
     993             : 
     994        4300 :     return joinrel;
     995             : }
     996             : 
     997             : /*
     998             :  * min_join_parameterization
     999             :  *
    1000             :  * Determine the minimum possible parameterization of a joinrel, that is, the
    1001             :  * set of other rels it contains LATERAL references to.  We save this value in
    1002             :  * the join's RelOptInfo.  This function is split out of build_join_rel()
    1003             :  * because join_is_legal() needs the value to check a prospective join.
    1004             :  */
    1005             : Relids
    1006      156104 : min_join_parameterization(PlannerInfo *root,
    1007             :                           Relids joinrelids,
    1008             :                           RelOptInfo *outer_rel,
    1009             :                           RelOptInfo *inner_rel)
    1010             : {
    1011             :     Relids      result;
    1012             : 
    1013             :     /*
    1014             :      * Basically we just need the union of the inputs' lateral_relids, less
    1015             :      * whatever is already in the join.
    1016             :      *
    1017             :      * It's not immediately obvious that this is a valid way to compute the
    1018             :      * result, because it might seem that we're ignoring possible lateral refs
    1019             :      * of PlaceHolderVars that are due to be computed at the join but not in
    1020             :      * either input.  However, because create_lateral_join_info() already
    1021             :      * charged all such PHV refs to each member baserel of the join, they'll
    1022             :      * be accounted for already in the inputs' lateral_relids.  Likewise, we
    1023             :      * do not need to worry about doing transitive closure here, because that
    1024             :      * was already accounted for in the original baserel lateral_relids.
    1025             :      */
    1026      156104 :     result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
    1027      156104 :     result = bms_del_members(result, joinrelids);
    1028      156104 :     return result;
    1029             : }
    1030             : 
    1031             : /*
    1032             :  * build_joinrel_tlist
    1033             :  *    Builds a join relation's target list from an input relation.
    1034             :  *    (This is invoked twice to handle the two input relations.)
    1035             :  *
    1036             :  * The join's targetlist includes all Vars of its member relations that
    1037             :  * will still be needed above the join.  This subroutine adds all such
    1038             :  * Vars from the specified input rel's tlist to the join rel's tlist.
    1039             :  * Likewise for any PlaceHolderVars emitted by the input rel.
    1040             :  *
    1041             :  * We also compute the expected width of the join's output, making use
    1042             :  * of data that was cached at the baserel level by set_rel_width().
    1043             :  *
    1044             :  * Pass can_null as true if the join is an outer join that can null Vars
    1045             :  * from this input relation.  If so, we will (normally) add the join's relid
    1046             :  * to the nulling bitmaps of Vars and PHVs bubbled up from the input.
    1047             :  *
    1048             :  * When forming an outer join's target list, special handling is needed in
    1049             :  * case the outer join was commuted with another one per outer join identity 3
    1050             :  * (see optimizer/README).  We must take steps to ensure that the output Vars
    1051             :  * have the same nulling bitmaps that they would if the two joins had been
    1052             :  * done in syntactic order; else they won't match Vars appearing higher in
    1053             :  * the query tree.  An exception to the match-the-syntactic-order rule is
    1054             :  * that when an outer join is pushed down into another one's RHS per identity
    1055             :  * 3, we can't mark its Vars as nulled until the now-upper outer join is also
    1056             :  * completed.  So we need to do three things:
    1057             :  *
    1058             :  * First, we add the outer join's relid to the nulling bitmap only if the
    1059             :  * outer join has been completely performed and the Var or PHV actually
    1060             :  * comes from within the syntactically nullable side(s) of the outer join.
    1061             :  * This takes care of the possibility that we have transformed
    1062             :  *      (A leftjoin B on (Pab)) leftjoin C on (Pbc)
    1063             :  * to
    1064             :  *      A leftjoin (B leftjoin C on (Pbc)) on (Pab)
    1065             :  * Here the pushed-down B/C join cannot mark C columns as nulled yet,
    1066             :  * while the now-upper A/B join must not mark C columns as nulled by itself.
    1067             :  *
    1068             :  * Second, perform the same operation for each SpecialJoinInfo listed in
    1069             :  * pushed_down_joins (which, in this example, would be the B/C join when
    1070             :  * we are at the now-upper A/B join).  This allows the now-upper join to
    1071             :  * complete the marking of "C" Vars that now have fully valid values.
    1072             :  *
    1073             :  * Third, any relid in sjinfo->commute_above_r that is already part of
    1074             :  * the joinrel is added to the nulling bitmaps of nullable Vars and PHVs.
    1075             :  * This takes care of the reverse case where we implement
    1076             :  *      A leftjoin (B leftjoin C on (Pbc)) on (Pab)
    1077             :  * as
    1078             :  *      (A leftjoin B on (Pab)) leftjoin C on (Pbc)
    1079             :  * The C columns emitted by the B/C join need to be shown as nulled by both
    1080             :  * the B/C and A/B joins, even though they've not physically traversed the
    1081             :  * A/B join.
    1082             :  */
    1083             : static void
    1084      288564 : build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
    1085             :                     RelOptInfo *input_rel,
    1086             :                     SpecialJoinInfo *sjinfo,
    1087             :                     List *pushed_down_joins,
    1088             :                     bool can_null)
    1089             : {
    1090      288564 :     Relids      relids = joinrel->relids;
    1091             :     ListCell   *vars;
    1092             :     ListCell   *lc;
    1093             : 
    1094     1300024 :     foreach(vars, input_rel->reltarget->exprs)
    1095             :     {
    1096     1011460 :         Var        *var = (Var *) lfirst(vars);
    1097             : 
    1098             :         /*
    1099             :          * For a PlaceHolderVar, we have to look up the PlaceHolderInfo.
    1100             :          */
    1101     1011460 :         if (IsA(var, PlaceHolderVar))
    1102             :         {
    1103        1642 :             PlaceHolderVar *phv = (PlaceHolderVar *) var;
    1104        1642 :             PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
    1105             : 
    1106             :             /* Is it still needed above this joinrel? */
    1107        1642 :             if (bms_nonempty_difference(phinfo->ph_needed, relids))
    1108             :             {
    1109             :                 /*
    1110             :                  * Yup, add it to the output.  If this join potentially nulls
    1111             :                  * this input, we have to update the PHV's phnullingrels,
    1112             :                  * which means making a copy.
    1113             :                  */
    1114        1198 :                 if (can_null)
    1115             :                 {
    1116         700 :                     phv = copyObject(phv);
    1117             :                     /* See comments above to understand this logic */
    1118        1400 :                     if (sjinfo->ojrelid != 0 &&
    1119        1382 :                         bms_is_member(sjinfo->ojrelid, relids) &&
    1120         682 :                         (bms_is_subset(phv->phrels, sjinfo->syn_righthand) ||
    1121         234 :                          (sjinfo->jointype == JOIN_FULL &&
    1122         114 :                           bms_is_subset(phv->phrels, sjinfo->syn_lefthand))))
    1123         676 :                         phv->phnullingrels = bms_add_member(phv->phnullingrels,
    1124         676 :                                                             sjinfo->ojrelid);
    1125         712 :                     foreach(lc, pushed_down_joins)
    1126             :                     {
    1127          12 :                         SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
    1128             : 
    1129             :                         Assert(bms_is_member(othersj->ojrelid, relids));
    1130          12 :                         if (bms_is_subset(phv->phrels, othersj->syn_righthand))
    1131           6 :                             phv->phnullingrels = bms_add_member(phv->phnullingrels,
    1132           6 :                                                                 othersj->ojrelid);
    1133             :                     }
    1134         700 :                     phv->phnullingrels =
    1135         700 :                         bms_join(phv->phnullingrels,
    1136         700 :                                  bms_intersect(sjinfo->commute_above_r,
    1137             :                                                relids));
    1138             :                 }
    1139             : 
    1140        1198 :                 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
    1141             :                                                     phv);
    1142             :                 /* Bubbling up the precomputed result has cost zero */
    1143        1198 :                 joinrel->reltarget->width += phinfo->ph_width;
    1144             :             }
    1145        1642 :             continue;
    1146             :         }
    1147             : 
    1148             :         /*
    1149             :          * Otherwise, anything in a baserel or joinrel targetlist ought to be
    1150             :          * a Var.  (More general cases can only appear in appendrel child
    1151             :          * rels, which will never be seen here.)
    1152             :          */
    1153     1009818 :         if (!IsA(var, Var))
    1154           0 :             elog(ERROR, "unexpected node type in rel targetlist: %d",
    1155             :                  (int) nodeTag(var));
    1156             : 
    1157     1009818 :         if (var->varno == ROWID_VAR)
    1158             :         {
    1159             :             /* UPDATE/DELETE/MERGE row identity vars are always needed */
    1160             :             RowIdentityVarInfo *ridinfo = (RowIdentityVarInfo *)
    1161         728 :                 list_nth(root->row_identity_vars, var->varattno - 1);
    1162             : 
    1163             :             /* Update reltarget width estimate from RowIdentityVarInfo */
    1164         728 :             joinrel->reltarget->width += ridinfo->rowidwidth;
    1165             :         }
    1166             :         else
    1167             :         {
    1168             :             RelOptInfo *baserel;
    1169             :             int         ndx;
    1170             : 
    1171             :             /* Get the Var's original base rel */
    1172     1009090 :             baserel = find_base_rel(root, var->varno);
    1173             : 
    1174             :             /* Is it still needed above this joinrel? */
    1175     1009090 :             ndx = var->varattno - baserel->min_attr;
    1176     1009090 :             if (!bms_nonempty_difference(baserel->attr_needed[ndx], relids))
    1177      198118 :                 continue;       /* nope, skip it */
    1178             : 
    1179             :             /* Update reltarget width estimate from baserel's attr_widths */
    1180      810972 :             joinrel->reltarget->width += baserel->attr_widths[ndx];
    1181             :         }
    1182             : 
    1183             :         /*
    1184             :          * Add the Var to the output.  If this join potentially nulls this
    1185             :          * input, we have to update the Var's varnullingrels, which means
    1186             :          * making a copy.  But note that we don't ever add nullingrel bits to
    1187             :          * row identity Vars (cf. comments in setrefs.c).
    1188             :          */
    1189      811700 :         if (can_null && var->varno != ROWID_VAR)
    1190             :         {
    1191       81294 :             var = copyObject(var);
    1192             :             /* See comments above to understand this logic */
    1193      162232 :             if (sjinfo->ojrelid != 0 &&
    1194      158326 :                 bms_is_member(sjinfo->ojrelid, relids) &&
    1195       77388 :                 (bms_is_member(var->varno, sjinfo->syn_righthand) ||
    1196        3450 :                  (sjinfo->jointype == JOIN_FULL &&
    1197        1698 :                   bms_is_member(var->varno, sjinfo->syn_lefthand))))
    1198       77334 :                 var->varnullingrels = bms_add_member(var->varnullingrels,
    1199       77334 :                                                      sjinfo->ojrelid);
    1200       81438 :             foreach(lc, pushed_down_joins)
    1201             :             {
    1202         144 :                 SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
    1203             : 
    1204             :                 Assert(bms_is_member(othersj->ojrelid, relids));
    1205         144 :                 if (bms_is_member(var->varno, othersj->syn_righthand))
    1206          54 :                     var->varnullingrels = bms_add_member(var->varnullingrels,
    1207          54 :                                                          othersj->ojrelid);
    1208             :             }
    1209       81294 :             var->varnullingrels =
    1210       81294 :                 bms_join(var->varnullingrels,
    1211       81294 :                          bms_intersect(sjinfo->commute_above_r,
    1212             :                                        relids));
    1213             :         }
    1214             : 
    1215      811700 :         joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
    1216             :                                             var);
    1217             : 
    1218             :         /* Vars have cost zero, so no need to adjust reltarget->cost */
    1219             :     }
    1220      288564 : }
    1221             : 
    1222             : /*
    1223             :  * build_joinrel_restrictlist
    1224             :  * build_joinrel_joinlist
    1225             :  *    These routines build lists of restriction and join clauses for a
    1226             :  *    join relation from the joininfo lists of the relations it joins.
    1227             :  *
    1228             :  *    These routines are separate because the restriction list must be
    1229             :  *    built afresh for each pair of input sub-relations we consider, whereas
    1230             :  *    the join list need only be computed once for any join RelOptInfo.
    1231             :  *    The join list is fully determined by the set of rels making up the
    1232             :  *    joinrel, so we should get the same results (up to ordering) from any
    1233             :  *    candidate pair of sub-relations.  But the restriction list is whatever
    1234             :  *    is not handled in the sub-relations, so it depends on which
    1235             :  *    sub-relations are considered.
    1236             :  *
    1237             :  *    If a join clause from an input relation refers to base+OJ rels still not
    1238             :  *    present in the joinrel, then it is still a join clause for the joinrel;
    1239             :  *    we put it into the joininfo list for the joinrel.  Otherwise,
    1240             :  *    the clause is now a restrict clause for the joined relation, and we
    1241             :  *    return it to the caller of build_joinrel_restrictlist() to be stored in
    1242             :  *    join paths made from this pair of sub-relations.  (It will not need to
    1243             :  *    be considered further up the join tree.)
    1244             :  *
    1245             :  *    In many cases we will find the same RestrictInfos in both input
    1246             :  *    relations' joinlists, so be careful to eliminate duplicates.
    1247             :  *    Pointer equality should be a sufficient test for dups, since all
    1248             :  *    the various joinlist entries ultimately refer to RestrictInfos
    1249             :  *    pushed into them by distribute_restrictinfo_to_rels().
    1250             :  *
    1251             :  * 'joinrel' is a join relation node
    1252             :  * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
    1253             :  *      to form joinrel.
    1254             :  * 'sjinfo': join context info
    1255             :  *
    1256             :  * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
    1257             :  * whereas build_joinrel_joinlist() stores its results in the joinrel's
    1258             :  * joininfo list.  One or the other must accept each given clause!
    1259             :  *
    1260             :  * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
    1261             :  * up to the join relation.  I believe this is no longer necessary, because
    1262             :  * RestrictInfo nodes are no longer context-dependent.  Instead, just include
    1263             :  * the original nodes in the lists made for the join relation.
    1264             :  */
    1265             : static List *
    1266      220310 : build_joinrel_restrictlist(PlannerInfo *root,
    1267             :                            RelOptInfo *joinrel,
    1268             :                            RelOptInfo *outer_rel,
    1269             :                            RelOptInfo *inner_rel,
    1270             :                            SpecialJoinInfo *sjinfo)
    1271             : {
    1272             :     List       *result;
    1273             :     Relids      both_input_relids;
    1274             : 
    1275      220310 :     both_input_relids = bms_union(outer_rel->relids, inner_rel->relids);
    1276             : 
    1277             :     /*
    1278             :      * Collect all the clauses that syntactically belong at this level,
    1279             :      * eliminating any duplicates (important since we will see many of the
    1280             :      * same clauses arriving from both input relations).
    1281             :      */
    1282      220310 :     result = subbuild_joinrel_restrictlist(root, joinrel, outer_rel,
    1283             :                                            both_input_relids, NIL);
    1284      220310 :     result = subbuild_joinrel_restrictlist(root, joinrel, inner_rel,
    1285             :                                            both_input_relids, result);
    1286             : 
    1287             :     /*
    1288             :      * Add on any clauses derived from EquivalenceClasses.  These cannot be
    1289             :      * redundant with the clauses in the joininfo lists, so don't bother
    1290             :      * checking.
    1291             :      */
    1292      220310 :     result = list_concat(result,
    1293      220310 :                          generate_join_implied_equalities(root,
    1294             :                                                           joinrel->relids,
    1295             :                                                           outer_rel->relids,
    1296             :                                                           inner_rel,
    1297             :                                                           sjinfo));
    1298             : 
    1299      220310 :     return result;
    1300             : }
    1301             : 
    1302             : static void
    1303      144282 : build_joinrel_joinlist(RelOptInfo *joinrel,
    1304             :                        RelOptInfo *outer_rel,
    1305             :                        RelOptInfo *inner_rel)
    1306             : {
    1307             :     List       *result;
    1308             : 
    1309             :     /*
    1310             :      * Collect all the clauses that syntactically belong above this level,
    1311             :      * eliminating any duplicates (important since we will see many of the
    1312             :      * same clauses arriving from both input relations).
    1313             :      */
    1314      144282 :     result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
    1315      144282 :     result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);
    1316             : 
    1317      144282 :     joinrel->joininfo = result;
    1318      144282 : }
    1319             : 
    1320             : static List *
    1321      440620 : subbuild_joinrel_restrictlist(PlannerInfo *root,
    1322             :                               RelOptInfo *joinrel,
    1323             :                               RelOptInfo *input_rel,
    1324             :                               Relids both_input_relids,
    1325             :                               List *new_restrictlist)
    1326             : {
    1327             :     ListCell   *l;
    1328             : 
    1329      862222 :     foreach(l, input_rel->joininfo)
    1330             :     {
    1331      421602 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
    1332             : 
    1333      421602 :         if (bms_is_subset(rinfo->required_relids, joinrel->relids))
    1334             :         {
    1335             :             /*
    1336             :              * This clause should become a restriction clause for the joinrel,
    1337             :              * since it refers to no outside rels.  However, if it's a clone
    1338             :              * clause then it might be too late to evaluate it, so we have to
    1339             :              * check.  (If it is too late, just ignore the clause, taking it
    1340             :              * on faith that another clone was or will be selected.)  Clone
    1341             :              * clauses should always be outer-join clauses, so we compare
    1342             :              * against both_input_relids.
    1343             :              */
    1344      248730 :             if (rinfo->has_clone || rinfo->is_clone)
    1345             :             {
    1346             :                 Assert(!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids));
    1347       37618 :                 if (!bms_is_subset(rinfo->required_relids, both_input_relids))
    1348        6214 :                     continue;
    1349       31404 :                 if (bms_overlap(rinfo->incompatible_relids, both_input_relids))
    1350       12332 :                     continue;
    1351             :             }
    1352             :             else
    1353             :             {
    1354             :                 /*
    1355             :                  * For non-clone clauses, we just Assert it's OK.  These might
    1356             :                  * be either join or filter clauses; if it's a join clause
    1357             :                  * then it should not refer to the current join's output.
    1358             :                  * (There is little point in checking incompatible_relids,
    1359             :                  * because it'll be NULL.)
    1360             :                  */
    1361             :                 Assert(RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids) ||
    1362             :                        bms_is_subset(rinfo->required_relids,
    1363             :                                      both_input_relids));
    1364             :             }
    1365             : 
    1366             :             /*
    1367             :              * OK, so add it to the list, being careful to eliminate
    1368             :              * duplicates.  (Since RestrictInfo nodes in different joinlists
    1369             :              * will have been multiply-linked rather than copied, pointer
    1370             :              * equality should be a sufficient test.)
    1371             :              */
    1372      230184 :             new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
    1373             :         }
    1374             :         else
    1375             :         {
    1376             :             /*
    1377             :              * This clause is still a join clause at this level, so we ignore
    1378             :              * it in this routine.
    1379             :              */
    1380             :         }
    1381             :     }
    1382             : 
    1383      440620 :     return new_restrictlist;
    1384             : }
    1385             : 
    1386             : static List *
    1387      288564 : subbuild_joinrel_joinlist(RelOptInfo *joinrel,
    1388             :                           List *joininfo_list,
    1389             :                           List *new_joininfo)
    1390             : {
    1391             :     ListCell   *l;
    1392             : 
    1393             :     /* Expected to be called only for join between parent relations. */
    1394             :     Assert(joinrel->reloptkind == RELOPT_JOINREL);
    1395             : 
    1396      553692 :     foreach(l, joininfo_list)
    1397             :     {
    1398      265128 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
    1399             : 
    1400      265128 :         if (bms_is_subset(rinfo->required_relids, joinrel->relids))
    1401             :         {
    1402             :             /*
    1403             :              * This clause becomes a restriction clause for the joinrel, since
    1404             :              * it refers to no outside rels.  So we can ignore it in this
    1405             :              * routine.
    1406             :              */
    1407             :         }
    1408             :         else
    1409             :         {
    1410             :             /*
    1411             :              * This clause is still a join clause at this level, so add it to
    1412             :              * the new joininfo list, being careful to eliminate duplicates.
    1413             :              * (Since RestrictInfo nodes in different joinlists will have been
    1414             :              * multiply-linked rather than copied, pointer equality should be
    1415             :              * a sufficient test.)
    1416             :              */
    1417      106054 :             new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
    1418             :         }
    1419             :     }
    1420             : 
    1421      288564 :     return new_joininfo;
    1422             : }
    1423             : 
    1424             : 
    1425             : /*
    1426             :  * fetch_upper_rel
    1427             :  *      Build a RelOptInfo describing some post-scan/join query processing,
    1428             :  *      or return a pre-existing one if somebody already built it.
    1429             :  *
    1430             :  * An "upper" relation is identified by an UpperRelationKind and a Relids set.
    1431             :  * The meaning of the Relids set is not specified here, and very likely will
    1432             :  * vary for different relation kinds.
    1433             :  *
    1434             :  * Most of the fields in an upper-level RelOptInfo are not used and are not
    1435             :  * set here (though makeNode should ensure they're zeroes).  We basically only
    1436             :  * care about fields that are of interest to add_path() and set_cheapest().
    1437             :  */
    1438             : RelOptInfo *
    1439     1493584 : fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
    1440             : {
    1441             :     RelOptInfo *upperrel;
    1442             :     ListCell   *lc;
    1443             : 
    1444             :     /*
    1445             :      * For the moment, our indexing data structure is just a List for each
    1446             :      * relation kind.  If we ever get so many of one kind that this stops
    1447             :      * working well, we can improve it.  No code outside this function should
    1448             :      * assume anything about how to find a particular upperrel.
    1449             :      */
    1450             : 
    1451             :     /* If we already made this upperrel for the query, return it */
    1452     1503730 :     foreach(lc, root->upper_rels[kind])
    1453             :     {
    1454      955504 :         upperrel = (RelOptInfo *) lfirst(lc);
    1455             : 
    1456      955504 :         if (bms_equal(upperrel->relids, relids))
    1457      945358 :             return upperrel;
    1458             :     }
    1459             : 
    1460      548226 :     upperrel = makeNode(RelOptInfo);
    1461      548226 :     upperrel->reloptkind = RELOPT_UPPER_REL;
    1462      548226 :     upperrel->relids = bms_copy(relids);
    1463             : 
    1464             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
    1465      548226 :     upperrel->consider_startup = (root->tuple_fraction > 0);
    1466      548226 :     upperrel->consider_param_startup = false;
    1467      548226 :     upperrel->consider_parallel = false; /* might get changed later */
    1468      548226 :     upperrel->reltarget = create_empty_pathtarget();
    1469      548226 :     upperrel->pathlist = NIL;
    1470      548226 :     upperrel->cheapest_startup_path = NULL;
    1471      548226 :     upperrel->cheapest_total_path = NULL;
    1472      548226 :     upperrel->cheapest_unique_path = NULL;
    1473      548226 :     upperrel->cheapest_parameterized_paths = NIL;
    1474             : 
    1475      548226 :     root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
    1476             : 
    1477      548226 :     return upperrel;
    1478             : }
    1479             : 
    1480             : 
    1481             : /*
    1482             :  * find_childrel_parents
    1483             :  *      Compute the set of parent relids of an appendrel child rel.
    1484             :  *
    1485             :  * Since appendrels can be nested, a child could have multiple levels of
    1486             :  * appendrel ancestors.  This function computes a Relids set of all the
    1487             :  * parent relation IDs.
    1488             :  */
    1489             : Relids
    1490       10082 : find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
    1491             : {
    1492       10082 :     Relids      result = NULL;
    1493             : 
    1494             :     Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
    1495             :     Assert(rel->relid > 0 && rel->relid < root->simple_rel_array_size);
    1496             : 
    1497             :     do
    1498             :     {
    1499       11950 :         AppendRelInfo *appinfo = root->append_rel_array[rel->relid];
    1500       11950 :         Index       prelid = appinfo->parent_relid;
    1501             : 
    1502       11950 :         result = bms_add_member(result, prelid);
    1503             : 
    1504             :         /* traverse up to the parent rel, loop if it's also a child rel */
    1505       11950 :         rel = find_base_rel(root, prelid);
    1506       11950 :     } while (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
    1507             : 
    1508             :     Assert(rel->reloptkind == RELOPT_BASEREL);
    1509             : 
    1510       10082 :     return result;
    1511             : }
    1512             : 
    1513             : 
    1514             : /*
    1515             :  * get_baserel_parampathinfo
    1516             :  *      Get the ParamPathInfo for a parameterized path for a base relation,
    1517             :  *      constructing one if we don't have one already.
    1518             :  *
    1519             :  * This centralizes estimating the rowcounts for parameterized paths.
    1520             :  * We need to cache those to be sure we use the same rowcount for all paths
    1521             :  * of the same parameterization for a given rel.  This is also a convenient
    1522             :  * place to determine which movable join clauses the parameterized path will
    1523             :  * be responsible for evaluating.
    1524             :  */
    1525             : ParamPathInfo *
    1526     1255202 : get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel,
    1527             :                           Relids required_outer)
    1528             : {
    1529             :     ParamPathInfo *ppi;
    1530             :     Relids      joinrelids;
    1531             :     List       *pclauses;
    1532             :     Bitmapset  *pserials;
    1533             :     double      rows;
    1534             :     ListCell   *lc;
    1535             : 
    1536             :     /* If rel has LATERAL refs, every path for it should account for them */
    1537             :     Assert(bms_is_subset(baserel->lateral_relids, required_outer));
    1538             : 
    1539             :     /* Unparameterized paths have no ParamPathInfo */
    1540     1255202 :     if (bms_is_empty(required_outer))
    1541     1042162 :         return NULL;
    1542             : 
    1543             :     Assert(!bms_overlap(baserel->relids, required_outer));
    1544             : 
    1545             :     /* If we already have a PPI for this parameterization, just return it */
    1546      213040 :     if ((ppi = find_param_path_info(baserel, required_outer)))
    1547      111216 :         return ppi;
    1548             : 
    1549             :     /*
    1550             :      * Identify all joinclauses that are movable to this base rel given this
    1551             :      * parameterization.
    1552             :      */
    1553      101824 :     joinrelids = bms_union(baserel->relids, required_outer);
    1554      101824 :     pclauses = NIL;
    1555      171250 :     foreach(lc, baserel->joininfo)
    1556             :     {
    1557       69426 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1558             : 
    1559       69426 :         if (join_clause_is_movable_into(rinfo,
    1560             :                                         baserel->relids,
    1561             :                                         joinrelids))
    1562       31106 :             pclauses = lappend(pclauses, rinfo);
    1563             :     }
    1564             : 
    1565             :     /*
    1566             :      * Add in joinclauses generated by EquivalenceClasses, too.  (These
    1567             :      * necessarily satisfy join_clause_is_movable_into.)
    1568             :      */
    1569      101824 :     pclauses = list_concat(pclauses,
    1570      101824 :                            generate_join_implied_equalities(root,
    1571             :                                                             joinrelids,
    1572             :                                                             required_outer,
    1573             :                                                             baserel,
    1574             :                                                             NULL));
    1575             : 
    1576             :     /* Compute set of serial numbers of the enforced clauses */
    1577      101824 :     pserials = NULL;
    1578      203782 :     foreach(lc, pclauses)
    1579             :     {
    1580      101958 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1581             : 
    1582      101958 :         pserials = bms_add_member(pserials, rinfo->rinfo_serial);
    1583             :     }
    1584             : 
    1585             :     /* Estimate the number of rows returned by the parameterized scan */
    1586      101824 :     rows = get_parameterized_baserel_size(root, baserel, pclauses);
    1587             : 
    1588             :     /* And now we can build the ParamPathInfo */
    1589      101824 :     ppi = makeNode(ParamPathInfo);
    1590      101824 :     ppi->ppi_req_outer = required_outer;
    1591      101824 :     ppi->ppi_rows = rows;
    1592      101824 :     ppi->ppi_clauses = pclauses;
    1593      101824 :     ppi->ppi_serials = pserials;
    1594      101824 :     baserel->ppilist = lappend(baserel->ppilist, ppi);
    1595             : 
    1596      101824 :     return ppi;
    1597             : }
    1598             : 
    1599             : /*
    1600             :  * get_joinrel_parampathinfo
    1601             :  *      Get the ParamPathInfo for a parameterized path for a join relation,
    1602             :  *      constructing one if we don't have one already.
    1603             :  *
    1604             :  * This centralizes estimating the rowcounts for parameterized paths.
    1605             :  * We need to cache those to be sure we use the same rowcount for all paths
    1606             :  * of the same parameterization for a given rel.  This is also a convenient
    1607             :  * place to determine which movable join clauses the parameterized path will
    1608             :  * be responsible for evaluating.
    1609             :  *
    1610             :  * outer_path and inner_path are a pair of input paths that can be used to
    1611             :  * construct the join, and restrict_clauses is the list of regular join
    1612             :  * clauses (including clauses derived from EquivalenceClasses) that must be
    1613             :  * applied at the join node when using these inputs.
    1614             :  *
    1615             :  * Unlike the situation for base rels, the set of movable join clauses to be
    1616             :  * enforced at a join varies with the selected pair of input paths, so we
    1617             :  * must calculate that and pass it back, even if we already have a matching
    1618             :  * ParamPathInfo.  We handle this by adding any clauses moved down to this
    1619             :  * join to *restrict_clauses, which is an in/out parameter.  (The addition
    1620             :  * is done in such a way as to not modify the passed-in List structure.)
    1621             :  *
    1622             :  * Note: when considering a nestloop join, the caller must have removed from
    1623             :  * restrict_clauses any movable clauses that are themselves scheduled to be
    1624             :  * pushed into the right-hand path.  We do not do that here since it's
    1625             :  * unnecessary for other join types.
    1626             :  */
    1627             : ParamPathInfo *
    1628     1244970 : get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
    1629             :                           Path *outer_path,
    1630             :                           Path *inner_path,
    1631             :                           SpecialJoinInfo *sjinfo,
    1632             :                           Relids required_outer,
    1633             :                           List **restrict_clauses)
    1634             : {
    1635             :     ParamPathInfo *ppi;
    1636             :     Relids      join_and_req;
    1637             :     Relids      outer_and_req;
    1638             :     Relids      inner_and_req;
    1639             :     List       *pclauses;
    1640             :     List       *eclauses;
    1641             :     List       *dropped_ecs;
    1642             :     double      rows;
    1643             :     ListCell   *lc;
    1644             : 
    1645             :     /* If rel has LATERAL refs, every path for it should account for them */
    1646             :     Assert(bms_is_subset(joinrel->lateral_relids, required_outer));
    1647             : 
    1648             :     /* Unparameterized paths have no ParamPathInfo or extra join clauses */
    1649     1244970 :     if (bms_is_empty(required_outer))
    1650     1224062 :         return NULL;
    1651             : 
    1652             :     Assert(!bms_overlap(joinrel->relids, required_outer));
    1653             : 
    1654             :     /*
    1655             :      * Identify all joinclauses that are movable to this join rel given this
    1656             :      * parameterization.  These are the clauses that are movable into this
    1657             :      * join, but not movable into either input path.  Treat an unparameterized
    1658             :      * input path as not accepting parameterized clauses (because it won't,
    1659             :      * per the shortcut exit above), even though the joinclause movement rules
    1660             :      * might allow the same clauses to be moved into a parameterized path for
    1661             :      * that rel.
    1662             :      */
    1663       20908 :     join_and_req = bms_union(joinrel->relids, required_outer);
    1664       20908 :     if (outer_path->param_info)
    1665       19222 :         outer_and_req = bms_union(outer_path->parent->relids,
    1666       19222 :                                   PATH_REQ_OUTER(outer_path));
    1667             :     else
    1668        1686 :         outer_and_req = NULL;   /* outer path does not accept parameters */
    1669       20908 :     if (inner_path->param_info)
    1670       11108 :         inner_and_req = bms_union(inner_path->parent->relids,
    1671       11108 :                                   PATH_REQ_OUTER(inner_path));
    1672             :     else
    1673        9800 :         inner_and_req = NULL;   /* inner path does not accept parameters */
    1674             : 
    1675       20908 :     pclauses = NIL;
    1676       54508 :     foreach(lc, joinrel->joininfo)
    1677             :     {
    1678       33600 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1679             : 
    1680       33600 :         if (join_clause_is_movable_into(rinfo,
    1681             :                                         joinrel->relids,
    1682       17264 :                                         join_and_req) &&
    1683       17264 :             !join_clause_is_movable_into(rinfo,
    1684       17264 :                                          outer_path->parent->relids,
    1685         686 :                                          outer_and_req) &&
    1686         686 :             !join_clause_is_movable_into(rinfo,
    1687         686 :                                          inner_path->parent->relids,
    1688             :                                          inner_and_req))
    1689          96 :             pclauses = lappend(pclauses, rinfo);
    1690             :     }
    1691             : 
    1692             :     /* Consider joinclauses generated by EquivalenceClasses, too */
    1693       20908 :     eclauses = generate_join_implied_equalities(root,
    1694             :                                                 join_and_req,
    1695             :                                                 required_outer,
    1696             :                                                 joinrel,
    1697             :                                                 NULL);
    1698             :     /* We only want ones that aren't movable to lower levels */
    1699       20908 :     dropped_ecs = NIL;
    1700       23392 :     foreach(lc, eclauses)
    1701             :     {
    1702        2484 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1703             : 
    1704             :         Assert(join_clause_is_movable_into(rinfo,
    1705             :                                            joinrel->relids,
    1706             :                                            join_and_req));
    1707        2484 :         if (join_clause_is_movable_into(rinfo,
    1708        2484 :                                         outer_path->parent->relids,
    1709             :                                         outer_and_req))
    1710        1232 :             continue;           /* drop if movable into LHS */
    1711        1252 :         if (join_clause_is_movable_into(rinfo,
    1712        1252 :                                         inner_path->parent->relids,
    1713             :                                         inner_and_req))
    1714             :         {
    1715             :             /* drop if movable into RHS, but remember EC for use below */
    1716             :             Assert(rinfo->left_ec == rinfo->right_ec);
    1717         644 :             dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
    1718         644 :             continue;
    1719             :         }
    1720         608 :         pclauses = lappend(pclauses, rinfo);
    1721             :     }
    1722             : 
    1723             :     /*
    1724             :      * EquivalenceClasses are harder to deal with than we could wish, because
    1725             :      * of the fact that a given EC can generate different clauses depending on
    1726             :      * context.  Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
    1727             :      * LHS and RHS of the current join and Z is in required_outer, and further
    1728             :      * suppose that the inner_path is parameterized by both X and Z.  The code
    1729             :      * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
    1730             :      * and in the latter case will have discarded it as being movable into the
    1731             :      * RHS.  However, the EC machinery might have produced either Y.Y = X.X or
    1732             :      * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
    1733             :      * not have produced both, and we can't readily tell from here which one
    1734             :      * it did pick.  If we add no clause to this join, we'll end up with
    1735             :      * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
    1736             :      * constrained to be equal to the other members of the EC.  (When we come
    1737             :      * to join Z to this X/Y path, we will certainly drop whichever EC clause
    1738             :      * is generated at that join, so this omission won't get fixed later.)
    1739             :      *
    1740             :      * To handle this, for each EC we discarded such a clause from, try to
    1741             :      * generate a clause connecting the required_outer rels to the join's LHS
    1742             :      * ("Z.Z = X.X" in the terms of the above example).  If successful, and if
    1743             :      * the clause can't be moved to the LHS, add it to the current join's
    1744             :      * restriction clauses.  (If an EC cannot generate such a clause then it
    1745             :      * has nothing that needs to be enforced here, while if the clause can be
    1746             :      * moved into the LHS then it should have been enforced within that path.)
    1747             :      *
    1748             :      * Note that we don't need similar processing for ECs whose clause was
    1749             :      * considered to be movable into the LHS, because the LHS can't refer to
    1750             :      * the RHS so there is no comparable ambiguity about what it might
    1751             :      * actually be enforcing internally.
    1752             :      */
    1753       20908 :     if (dropped_ecs)
    1754             :     {
    1755             :         Relids      real_outer_and_req;
    1756             : 
    1757         614 :         real_outer_and_req = bms_union(outer_path->parent->relids,
    1758             :                                        required_outer);
    1759             :         eclauses =
    1760         614 :             generate_join_implied_equalities_for_ecs(root,
    1761             :                                                      dropped_ecs,
    1762             :                                                      real_outer_and_req,
    1763             :                                                      required_outer,
    1764             :                                                      outer_path->parent);
    1765         656 :         foreach(lc, eclauses)
    1766             :         {
    1767          42 :             RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1768             : 
    1769             :             Assert(join_clause_is_movable_into(rinfo,
    1770             :                                                outer_path->parent->relids,
    1771             :                                                real_outer_and_req));
    1772          42 :             if (!join_clause_is_movable_into(rinfo,
    1773          42 :                                              outer_path->parent->relids,
    1774             :                                              outer_and_req))
    1775          30 :                 pclauses = lappend(pclauses, rinfo);
    1776             :         }
    1777             :     }
    1778             : 
    1779             :     /*
    1780             :      * Now, attach the identified moved-down clauses to the caller's
    1781             :      * restrict_clauses list.  By using list_concat in this order, we leave
    1782             :      * the original list structure of restrict_clauses undamaged.
    1783             :      */
    1784       20908 :     *restrict_clauses = list_concat(pclauses, *restrict_clauses);
    1785             : 
    1786             :     /* If we already have a PPI for this parameterization, just return it */
    1787       20908 :     if ((ppi = find_param_path_info(joinrel, required_outer)))
    1788       15534 :         return ppi;
    1789             : 
    1790             :     /* Estimate the number of rows returned by the parameterized join */
    1791        5374 :     rows = get_parameterized_joinrel_size(root, joinrel,
    1792             :                                           outer_path,
    1793             :                                           inner_path,
    1794             :                                           sjinfo,
    1795             :                                           *restrict_clauses);
    1796             : 
    1797             :     /*
    1798             :      * And now we can build the ParamPathInfo.  No point in saving the
    1799             :      * input-pair-dependent clause list, though.
    1800             :      *
    1801             :      * Note: in GEQO mode, we'll be called in a temporary memory context, but
    1802             :      * the joinrel structure is there too, so no problem.
    1803             :      */
    1804        5374 :     ppi = makeNode(ParamPathInfo);
    1805        5374 :     ppi->ppi_req_outer = required_outer;
    1806        5374 :     ppi->ppi_rows = rows;
    1807        5374 :     ppi->ppi_clauses = NIL;
    1808        5374 :     ppi->ppi_serials = NULL;
    1809        5374 :     joinrel->ppilist = lappend(joinrel->ppilist, ppi);
    1810             : 
    1811        5374 :     return ppi;
    1812             : }
    1813             : 
    1814             : /*
    1815             :  * get_appendrel_parampathinfo
    1816             :  *      Get the ParamPathInfo for a parameterized path for an append relation.
    1817             :  *
    1818             :  * For an append relation, the rowcount estimate will just be the sum of
    1819             :  * the estimates for its children.  However, we still need a ParamPathInfo
    1820             :  * to flag the fact that the path requires parameters.  So this just creates
    1821             :  * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
    1822             :  * the Append node isn't responsible for checking quals).
    1823             :  */
    1824             : ParamPathInfo *
    1825       38706 : get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer)
    1826             : {
    1827             :     ParamPathInfo *ppi;
    1828             : 
    1829             :     /* If rel has LATERAL refs, every path for it should account for them */
    1830             :     Assert(bms_is_subset(appendrel->lateral_relids, required_outer));
    1831             : 
    1832             :     /* Unparameterized paths have no ParamPathInfo */
    1833       38706 :     if (bms_is_empty(required_outer))
    1834       38252 :         return NULL;
    1835             : 
    1836             :     Assert(!bms_overlap(appendrel->relids, required_outer));
    1837             : 
    1838             :     /* If we already have a PPI for this parameterization, just return it */
    1839         454 :     if ((ppi = find_param_path_info(appendrel, required_outer)))
    1840         102 :         return ppi;
    1841             : 
    1842             :     /* Else build the ParamPathInfo */
    1843         352 :     ppi = makeNode(ParamPathInfo);
    1844         352 :     ppi->ppi_req_outer = required_outer;
    1845         352 :     ppi->ppi_rows = 0;
    1846         352 :     ppi->ppi_clauses = NIL;
    1847         352 :     ppi->ppi_serials = NULL;
    1848         352 :     appendrel->ppilist = lappend(appendrel->ppilist, ppi);
    1849             : 
    1850         352 :     return ppi;
    1851             : }
    1852             : 
    1853             : /*
    1854             :  * Returns a ParamPathInfo for the parameterization given by required_outer, if
    1855             :  * already available in the given rel. Returns NULL otherwise.
    1856             :  */
    1857             : ParamPathInfo *
    1858      242566 : find_param_path_info(RelOptInfo *rel, Relids required_outer)
    1859             : {
    1860             :     ListCell   *lc;
    1861             : 
    1862      289054 :     foreach(lc, rel->ppilist)
    1863             :     {
    1864      179494 :         ParamPathInfo *ppi = (ParamPathInfo *) lfirst(lc);
    1865             : 
    1866      179494 :         if (bms_equal(ppi->ppi_req_outer, required_outer))
    1867      133006 :             return ppi;
    1868             :     }
    1869             : 
    1870      109560 :     return NULL;
    1871             : }
    1872             : 
    1873             : /*
    1874             :  * get_param_path_clause_serials
    1875             :  *      Given a parameterized Path, return the set of pushed-down clauses
    1876             :  *      (identified by rinfo_serial numbers) enforced within the Path.
    1877             :  */
    1878             : Bitmapset *
    1879      253380 : get_param_path_clause_serials(Path *path)
    1880             : {
    1881      253380 :     if (path->param_info == NULL)
    1882         786 :         return NULL;            /* not parameterized */
    1883      252594 :     if (IsA(path, NestPath) ||
    1884      247546 :         IsA(path, MergePath) ||
    1885      247468 :         IsA(path, HashPath))
    1886             :     {
    1887             :         /*
    1888             :          * For a join path, combine clauses enforced within either input path
    1889             :          * with those enforced as joinrestrictinfo in this path.  Note that
    1890             :          * joinrestrictinfo may include some non-pushed-down clauses, but for
    1891             :          * current purposes it's okay if we include those in the result. (To
    1892             :          * be more careful, we could check for clause_relids overlapping the
    1893             :          * path parameterization, but it's not worth the cycles for now.)
    1894             :          */
    1895        5884 :         JoinPath   *jpath = (JoinPath *) path;
    1896             :         Bitmapset  *pserials;
    1897             :         ListCell   *lc;
    1898             : 
    1899        5884 :         pserials = NULL;
    1900        5884 :         pserials = bms_add_members(pserials,
    1901        5884 :                                    get_param_path_clause_serials(jpath->outerjoinpath));
    1902        5884 :         pserials = bms_add_members(pserials,
    1903        5884 :                                    get_param_path_clause_serials(jpath->innerjoinpath));
    1904        7502 :         foreach(lc, jpath->joinrestrictinfo)
    1905             :         {
    1906        1618 :             RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1907             : 
    1908        1618 :             pserials = bms_add_member(pserials, rinfo->rinfo_serial);
    1909             :         }
    1910        5884 :         return pserials;
    1911             :     }
    1912      246710 :     else if (IsA(path, AppendPath))
    1913             :     {
    1914             :         /*
    1915             :          * For an appendrel, take the intersection of the sets of clauses
    1916             :          * enforced in each input path.
    1917             :          */
    1918        1934 :         AppendPath *apath = (AppendPath *) path;
    1919             :         Bitmapset  *pserials;
    1920             :         ListCell   *lc;
    1921             : 
    1922        1934 :         pserials = NULL;
    1923        8138 :         foreach(lc, apath->subpaths)
    1924             :         {
    1925        6204 :             Path       *subpath = (Path *) lfirst(lc);
    1926             :             Bitmapset  *subserials;
    1927             : 
    1928        6204 :             subserials = get_param_path_clause_serials(subpath);
    1929        6204 :             if (lc == list_head(apath->subpaths))
    1930        1922 :                 pserials = bms_copy(subserials);
    1931             :             else
    1932        4282 :                 pserials = bms_int_members(pserials, subserials);
    1933             :         }
    1934        1934 :         return pserials;
    1935             :     }
    1936      244776 :     else if (IsA(path, MergeAppendPath))
    1937             :     {
    1938             :         /* Same as AppendPath case */
    1939           0 :         MergeAppendPath *apath = (MergeAppendPath *) path;
    1940             :         Bitmapset  *pserials;
    1941             :         ListCell   *lc;
    1942             : 
    1943           0 :         pserials = NULL;
    1944           0 :         foreach(lc, apath->subpaths)
    1945             :         {
    1946           0 :             Path       *subpath = (Path *) lfirst(lc);
    1947             :             Bitmapset  *subserials;
    1948             : 
    1949           0 :             subserials = get_param_path_clause_serials(subpath);
    1950           0 :             if (lc == list_head(apath->subpaths))
    1951           0 :                 pserials = bms_copy(subserials);
    1952             :             else
    1953           0 :                 pserials = bms_int_members(pserials, subserials);
    1954             :         }
    1955           0 :         return pserials;
    1956             :     }
    1957             :     else
    1958             :     {
    1959             :         /*
    1960             :          * Otherwise, it's a baserel path and we can use the
    1961             :          * previously-computed set of serial numbers.
    1962             :          */
    1963      244776 :         return path->param_info->ppi_serials;
    1964             :     }
    1965             : }
    1966             : 
    1967             : /*
    1968             :  * build_joinrel_partition_info
    1969             :  *      Checks if the two relations being joined can use partitionwise join
    1970             :  *      and if yes, initialize partitioning information of the resulting
    1971             :  *      partitioned join relation.
    1972             :  */
    1973             : static void
    1974      148582 : build_joinrel_partition_info(PlannerInfo *root,
    1975             :                              RelOptInfo *joinrel, RelOptInfo *outer_rel,
    1976             :                              RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo,
    1977             :                              List *restrictlist)
    1978             : {
    1979             :     PartitionScheme part_scheme;
    1980             : 
    1981             :     /* Nothing to do if partitionwise join technique is disabled. */
    1982      148582 :     if (!enable_partitionwise_join)
    1983             :     {
    1984             :         Assert(!IS_PARTITIONED_REL(joinrel));
    1985      142444 :         return;
    1986             :     }
    1987             : 
    1988             :     /*
    1989             :      * We can only consider this join as an input to further partitionwise
    1990             :      * joins if (a) the input relations are partitioned and have
    1991             :      * consider_partitionwise_join=true, (b) the partition schemes match, and
    1992             :      * (c) we can identify an equi-join between the partition keys.  Note that
    1993             :      * if it were possible for have_partkey_equi_join to return different
    1994             :      * answers for the same joinrel depending on which join ordering we try
    1995             :      * first, this logic would break.  That shouldn't happen, though, because
    1996             :      * of the way the query planner deduces implied equalities and reorders
    1997             :      * the joins.  Please see optimizer/README for details.
    1998             :      */
    1999        6138 :     if (outer_rel->part_scheme == NULL || inner_rel->part_scheme == NULL ||
    2000        2018 :         !outer_rel->consider_partitionwise_join ||
    2001        1974 :         !inner_rel->consider_partitionwise_join ||
    2002        1974 :         outer_rel->part_scheme != inner_rel->part_scheme ||
    2003        1950 :         !have_partkey_equi_join(root, joinrel, outer_rel, inner_rel,
    2004             :                                 sjinfo->jointype, restrictlist))
    2005             :     {
    2006             :         Assert(!IS_PARTITIONED_REL(joinrel));
    2007        4344 :         return;
    2008             :     }
    2009             : 
    2010        1794 :     part_scheme = outer_rel->part_scheme;
    2011             : 
    2012             :     /*
    2013             :      * This function will be called only once for each joinrel, hence it
    2014             :      * should not have partitioning fields filled yet.
    2015             :      */
    2016             :     Assert(!joinrel->part_scheme && !joinrel->partexprs &&
    2017             :            !joinrel->nullable_partexprs && !joinrel->part_rels &&
    2018             :            !joinrel->boundinfo);
    2019             : 
    2020             :     /*
    2021             :      * If the join relation is partitioned, it uses the same partitioning
    2022             :      * scheme as the joining relations.
    2023             :      *
    2024             :      * Note: we calculate the partition bounds, number of partitions, and
    2025             :      * child-join relations of the join relation in try_partitionwise_join().
    2026             :      */
    2027        1794 :     joinrel->part_scheme = part_scheme;
    2028        1794 :     set_joinrel_partition_key_exprs(joinrel, outer_rel, inner_rel,
    2029             :                                     sjinfo->jointype);
    2030             : 
    2031             :     /*
    2032             :      * Set the consider_partitionwise_join flag.
    2033             :      */
    2034             :     Assert(outer_rel->consider_partitionwise_join);
    2035             :     Assert(inner_rel->consider_partitionwise_join);
    2036        1794 :     joinrel->consider_partitionwise_join = true;
    2037             : }
    2038             : 
    2039             : /*
    2040             :  * have_partkey_equi_join
    2041             :  *
    2042             :  * Returns true if there exist equi-join conditions involving pairs
    2043             :  * of matching partition keys of the relations being joined for all
    2044             :  * partition keys.
    2045             :  */
    2046             : static bool
    2047        1950 : have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel,
    2048             :                        RelOptInfo *rel1, RelOptInfo *rel2,
    2049             :                        JoinType jointype, List *restrictlist)
    2050             : {
    2051        1950 :     PartitionScheme part_scheme = rel1->part_scheme;
    2052             :     ListCell   *lc;
    2053             :     int         cnt_pks;
    2054             :     bool        pk_has_clause[PARTITION_MAX_KEYS];
    2055             :     bool        strict_op;
    2056             : 
    2057             :     /*
    2058             :      * This function must only be called when the joined relations have same
    2059             :      * partitioning scheme.
    2060             :      */
    2061             :     Assert(rel1->part_scheme == rel2->part_scheme);
    2062             :     Assert(part_scheme);
    2063             : 
    2064        1950 :     memset(pk_has_clause, 0, sizeof(pk_has_clause));
    2065        5134 :     foreach(lc, restrictlist)
    2066             :     {
    2067        3184 :         RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
    2068             :         OpExpr     *opexpr;
    2069             :         Expr       *expr1;
    2070             :         Expr       *expr2;
    2071             :         int         ipk1;
    2072             :         int         ipk2;
    2073             : 
    2074             :         /* If processing an outer join, only use its own join clauses. */
    2075        3184 :         if (IS_OUTER_JOIN(jointype) &&
    2076        1872 :             RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
    2077         318 :             continue;
    2078             : 
    2079             :         /* Skip clauses which can not be used for a join. */
    2080        2866 :         if (!rinfo->can_join)
    2081          36 :             continue;
    2082             : 
    2083             :         /* Skip clauses which are not equality conditions. */
    2084        2830 :         if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
    2085           6 :             continue;
    2086             : 
    2087             :         /* Should be OK to assume it's an OpExpr. */
    2088        2824 :         opexpr = castNode(OpExpr, rinfo->clause);
    2089             : 
    2090             :         /* Match the operands to the relation. */
    2091        5440 :         if (bms_is_subset(rinfo->left_relids, rel1->relids) &&
    2092        2616 :             bms_is_subset(rinfo->right_relids, rel2->relids))
    2093             :         {
    2094        2616 :             expr1 = linitial(opexpr->args);
    2095        2616 :             expr2 = lsecond(opexpr->args);
    2096             :         }
    2097         416 :         else if (bms_is_subset(rinfo->left_relids, rel2->relids) &&
    2098         208 :                  bms_is_subset(rinfo->right_relids, rel1->relids))
    2099             :         {
    2100         208 :             expr1 = lsecond(opexpr->args);
    2101         208 :             expr2 = linitial(opexpr->args);
    2102             :         }
    2103             :         else
    2104           0 :             continue;
    2105             : 
    2106             :         /*
    2107             :          * Now we need to know whether the join operator is strict; see
    2108             :          * comments in pathnodes.h.
    2109             :          */
    2110        2824 :         strict_op = op_strict(opexpr->opno);
    2111             : 
    2112             :         /*
    2113             :          * Vars appearing in the relation's partition keys will not have any
    2114             :          * varnullingrels, but those in expr1 and expr2 will if we're above
    2115             :          * outer joins that could null the respective rels.  It's okay to
    2116             :          * match anyway, if the join operator is strict.
    2117             :          */
    2118        2824 :         if (strict_op)
    2119             :         {
    2120        2824 :             if (bms_overlap(rel1->relids, root->outer_join_rels))
    2121         210 :                 expr1 = (Expr *) remove_nulling_relids((Node *) expr1,
    2122         210 :                                                        root->outer_join_rels,
    2123             :                                                        NULL);
    2124        2824 :             if (bms_overlap(rel2->relids, root->outer_join_rels))
    2125           0 :                 expr2 = (Expr *) remove_nulling_relids((Node *) expr2,
    2126           0 :                                                        root->outer_join_rels,
    2127             :                                                        NULL);
    2128             :         }
    2129             : 
    2130             :         /*
    2131             :          * Only clauses referencing the partition keys are useful for
    2132             :          * partitionwise join.
    2133             :          */
    2134        2824 :         ipk1 = match_expr_to_partition_keys(expr1, rel1, strict_op);
    2135        2824 :         if (ipk1 < 0)
    2136        1006 :             continue;
    2137        1818 :         ipk2 = match_expr_to_partition_keys(expr2, rel2, strict_op);
    2138        1818 :         if (ipk2 < 0)
    2139           0 :             continue;
    2140             : 
    2141             :         /*
    2142             :          * If the clause refers to keys at different ordinal positions, it can
    2143             :          * not be used for partitionwise join.
    2144             :          */
    2145        1818 :         if (ipk1 != ipk2)
    2146           6 :             continue;
    2147             : 
    2148             :         /*
    2149             :          * The clause allows partitionwise join only if it uses the same
    2150             :          * operator family as that specified by the partition key.
    2151             :          */
    2152        1812 :         if (rel1->part_scheme->strategy == PARTITION_STRATEGY_HASH)
    2153             :         {
    2154          48 :             if (!OidIsValid(rinfo->hashjoinoperator) ||
    2155          48 :                 !op_in_opfamily(rinfo->hashjoinoperator,
    2156          48 :                                 part_scheme->partopfamily[ipk1]))
    2157           0 :                 continue;
    2158             :         }
    2159        1764 :         else if (!list_member_oid(rinfo->mergeopfamilies,
    2160        1764 :                                   part_scheme->partopfamily[ipk1]))
    2161           0 :             continue;
    2162             : 
    2163             :         /* Mark the partition key as having an equi-join clause. */
    2164        1812 :         pk_has_clause[ipk1] = true;
    2165             :     }
    2166             : 
    2167             :     /* Check whether every partition key has an equi-join condition. */
    2168        3762 :     for (cnt_pks = 0; cnt_pks < part_scheme->partnatts; cnt_pks++)
    2169             :     {
    2170        1968 :         if (!pk_has_clause[cnt_pks])
    2171         156 :             return false;
    2172             :     }
    2173             : 
    2174        1794 :     return true;
    2175             : }
    2176             : 
    2177             : /*
    2178             :  * match_expr_to_partition_keys
    2179             :  *
    2180             :  * Tries to match an expression to one of the nullable or non-nullable
    2181             :  * partition keys of "rel".  Returns the matched key's ordinal position,
    2182             :  * or -1 if the expression could not be matched to any of the keys.
    2183             :  *
    2184             :  * strict_op must be true if the expression will be compared with the
    2185             :  * partition key using a strict operator.  This allows us to consider
    2186             :  * nullable as well as nonnullable partition keys.
    2187             :  */
    2188             : static int
    2189        4642 : match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
    2190             : {
    2191             :     int         cnt;
    2192             : 
    2193             :     /* This function should be called only for partitioned relations. */
    2194             :     Assert(rel->part_scheme);
    2195             :     Assert(rel->partexprs);
    2196             :     Assert(rel->nullable_partexprs);
    2197             : 
    2198             :     /* Remove any relabel decorations. */
    2199        4888 :     while (IsA(expr, RelabelType))
    2200         246 :         expr = (Expr *) (castNode(RelabelType, expr))->arg;
    2201             : 
    2202        5684 :     for (cnt = 0; cnt < rel->part_scheme->partnatts; cnt++)
    2203             :     {
    2204             :         ListCell   *lc;
    2205             : 
    2206             :         /* We can always match to the non-nullable partition keys. */
    2207        5708 :         foreach(lc, rel->partexprs[cnt])
    2208             :         {
    2209        4594 :             if (equal(lfirst(lc), expr))
    2210        3564 :                 return cnt;
    2211             :         }
    2212             : 
    2213        1114 :         if (!strict_op)
    2214           0 :             continue;
    2215             : 
    2216             :         /*
    2217             :          * If it's a strict join operator then a NULL partition key on one
    2218             :          * side will not join to any partition key on the other side, and in
    2219             :          * particular such a row can't join to a row from a different
    2220             :          * partition on the other side.  So, it's okay to search the nullable
    2221             :          * partition keys as well.
    2222             :          */
    2223        1414 :         foreach(lc, rel->nullable_partexprs[cnt])
    2224             :         {
    2225         372 :             if (equal(lfirst(lc), expr))
    2226          72 :                 return cnt;
    2227             :         }
    2228             :     }
    2229             : 
    2230        1006 :     return -1;
    2231             : }
    2232             : 
    2233             : /*
    2234             :  * set_joinrel_partition_key_exprs
    2235             :  *      Initialize partition key expressions for a partitioned joinrel.
    2236             :  */
    2237             : static void
    2238        1794 : set_joinrel_partition_key_exprs(RelOptInfo *joinrel,
    2239             :                                 RelOptInfo *outer_rel, RelOptInfo *inner_rel,
    2240             :                                 JoinType jointype)
    2241             : {
    2242        1794 :     PartitionScheme part_scheme = joinrel->part_scheme;
    2243        1794 :     int         partnatts = part_scheme->partnatts;
    2244             : 
    2245        1794 :     joinrel->partexprs = (List **) palloc0(sizeof(List *) * partnatts);
    2246        1794 :     joinrel->nullable_partexprs =
    2247        1794 :         (List **) palloc0(sizeof(List *) * partnatts);
    2248             : 
    2249             :     /*
    2250             :      * The joinrel's partition expressions are the same as those of the input
    2251             :      * rels, but we must properly classify them as nullable or not in the
    2252             :      * joinrel's output.  (Also, we add some more partition expressions if
    2253             :      * it's a FULL JOIN.)
    2254             :      */
    2255        3600 :     for (int cnt = 0; cnt < partnatts; cnt++)
    2256             :     {
    2257             :         /* mark these const to enforce that we copy them properly */
    2258        1806 :         const List *outer_expr = outer_rel->partexprs[cnt];
    2259        1806 :         const List *outer_null_expr = outer_rel->nullable_partexprs[cnt];
    2260        1806 :         const List *inner_expr = inner_rel->partexprs[cnt];
    2261        1806 :         const List *inner_null_expr = inner_rel->nullable_partexprs[cnt];
    2262        1806 :         List       *partexpr = NIL;
    2263        1806 :         List       *nullable_partexpr = NIL;
    2264             :         ListCell   *lc;
    2265             : 
    2266        1806 :         switch (jointype)
    2267             :         {
    2268             :                 /*
    2269             :                  * A join relation resulting from an INNER join may be
    2270             :                  * regarded as partitioned by either of the inner and outer
    2271             :                  * relation keys.  For example, A INNER JOIN B ON A.a = B.b
    2272             :                  * can be regarded as partitioned on either A.a or B.b.  So we
    2273             :                  * add both keys to the joinrel's partexpr lists.  However,
    2274             :                  * anything that was already nullable still has to be treated
    2275             :                  * as nullable.
    2276             :                  */
    2277         700 :             case JOIN_INNER:
    2278         700 :                 partexpr = list_concat_copy(outer_expr, inner_expr);
    2279         700 :                 nullable_partexpr = list_concat_copy(outer_null_expr,
    2280             :                                                      inner_null_expr);
    2281         700 :                 break;
    2282             : 
    2283             :                 /*
    2284             :                  * A join relation resulting from a SEMI or ANTI join may be
    2285             :                  * regarded as partitioned by the outer relation keys.  The
    2286             :                  * inner relation's keys are no longer interesting; since they
    2287             :                  * aren't visible in the join output, nothing could join to
    2288             :                  * them.
    2289             :                  */
    2290         264 :             case JOIN_SEMI:
    2291             :             case JOIN_ANTI:
    2292         264 :                 partexpr = list_copy(outer_expr);
    2293         264 :                 nullable_partexpr = list_copy(outer_null_expr);
    2294         264 :                 break;
    2295             : 
    2296             :                 /*
    2297             :                  * A join relation resulting from a LEFT OUTER JOIN likewise
    2298             :                  * may be regarded as partitioned on the (non-nullable) outer
    2299             :                  * relation keys.  The inner (nullable) relation keys are okay
    2300             :                  * as partition keys for further joins as long as they involve
    2301             :                  * strict join operators.
    2302             :                  */
    2303         556 :             case JOIN_LEFT:
    2304         556 :                 partexpr = list_copy(outer_expr);
    2305         556 :                 nullable_partexpr = list_concat_copy(inner_expr,
    2306             :                                                      outer_null_expr);
    2307         556 :                 nullable_partexpr = list_concat(nullable_partexpr,
    2308             :                                                 inner_null_expr);
    2309         556 :                 break;
    2310             : 
    2311             :                 /*
    2312             :                  * For FULL OUTER JOINs, both relations are nullable, so the
    2313             :                  * resulting join relation may be regarded as partitioned on
    2314             :                  * either of inner and outer relation keys, but only for joins
    2315             :                  * that involve strict join operators.
    2316             :                  */
    2317         286 :             case JOIN_FULL:
    2318         286 :                 nullable_partexpr = list_concat_copy(outer_expr,
    2319             :                                                      inner_expr);
    2320         286 :                 nullable_partexpr = list_concat(nullable_partexpr,
    2321             :                                                 outer_null_expr);
    2322         286 :                 nullable_partexpr = list_concat(nullable_partexpr,
    2323             :                                                 inner_null_expr);
    2324             : 
    2325             :                 /*
    2326             :                  * Also add CoalesceExprs corresponding to each possible
    2327             :                  * full-join output variable (that is, left side coalesced to
    2328             :                  * right side), so that we can match equijoin expressions
    2329             :                  * using those variables.  We really only need these for
    2330             :                  * columns merged by JOIN USING, and only with the pairs of
    2331             :                  * input items that correspond to the data structures that
    2332             :                  * parse analysis would build for such variables.  But it's
    2333             :                  * hard to tell which those are, so just make all the pairs.
    2334             :                  * Extra items in the nullable_partexprs list won't cause big
    2335             :                  * problems.  (It's possible that such items will get matched
    2336             :                  * to user-written COALESCEs, but it should still be valid to
    2337             :                  * partition on those, since they're going to be either the
    2338             :                  * partition column or NULL; it's the same argument as for
    2339             :                  * partitionwise nesting of any outer join.)  We assume no
    2340             :                  * type coercions are needed to make the coalesce expressions,
    2341             :                  * since columns of different types won't have gotten
    2342             :                  * classified as the same PartitionScheme.  Note that we
    2343             :                  * intentionally leave out the varnullingrels decoration that
    2344             :                  * would ordinarily appear on the Vars inside these
    2345             :                  * CoalesceExprs, because have_partkey_equi_join will strip
    2346             :                  * varnullingrels from the expressions it will compare to the
    2347             :                  * partexprs.
    2348             :                  */
    2349         728 :                 foreach(lc, list_concat_copy(outer_expr, outer_null_expr))
    2350             :                 {
    2351         442 :                     Node       *larg = (Node *) lfirst(lc);
    2352             :                     ListCell   *lc2;
    2353             : 
    2354         884 :                     foreach(lc2, list_concat_copy(inner_expr, inner_null_expr))
    2355             :                     {
    2356         442 :                         Node       *rarg = (Node *) lfirst(lc2);
    2357         442 :                         CoalesceExpr *c = makeNode(CoalesceExpr);
    2358             : 
    2359         442 :                         c->coalescetype = exprType(larg);
    2360         442 :                         c->coalescecollid = exprCollation(larg);
    2361         442 :                         c->args = list_make2(larg, rarg);
    2362         442 :                         c->location = -1;
    2363         442 :                         nullable_partexpr = lappend(nullable_partexpr, c);
    2364             :                     }
    2365             :                 }
    2366         286 :                 break;
    2367             : 
    2368           0 :             default:
    2369           0 :                 elog(ERROR, "unrecognized join type: %d", (int) jointype);
    2370             :         }
    2371             : 
    2372        1806 :         joinrel->partexprs[cnt] = partexpr;
    2373        1806 :         joinrel->nullable_partexprs[cnt] = nullable_partexpr;
    2374             :     }
    2375        1794 : }
    2376             : 
    2377             : /*
    2378             :  * build_child_join_reltarget
    2379             :  *    Set up a child-join relation's reltarget from a parent-join relation.
    2380             :  */
    2381             : static void
    2382        4300 : build_child_join_reltarget(PlannerInfo *root,
    2383             :                            RelOptInfo *parentrel,
    2384             :                            RelOptInfo *childrel,
    2385             :                            int nappinfos,
    2386             :                            AppendRelInfo **appinfos)
    2387             : {
    2388             :     /* Build the targetlist */
    2389        8600 :     childrel->reltarget->exprs = (List *)
    2390        4300 :         adjust_appendrel_attrs(root,
    2391        4300 :                                (Node *) parentrel->reltarget->exprs,
    2392             :                                nappinfos, appinfos);
    2393             : 
    2394             :     /* Set the cost and width fields */
    2395        4300 :     childrel->reltarget->cost.startup = parentrel->reltarget->cost.startup;
    2396        4300 :     childrel->reltarget->cost.per_tuple = parentrel->reltarget->cost.per_tuple;
    2397        4300 :     childrel->reltarget->width = parentrel->reltarget->width;
    2398        4300 : }

Generated by: LCOV version 1.14