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

Generated by: LCOV version 1.14