LCOV - code coverage report
Current view: top level - src/backend/optimizer/util - relnode.c (source / functions) Hit Total Coverage
Test: PostgreSQL 14devel Lines: 619 637 97.2 %
Date: 2021-01-26 01:06:44 Functions: 27 27 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-2021, 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 "utils/hsearch.h"
      32             : #include "utils/lsyscache.h"
      33             : 
      34             : 
      35             : typedef struct JoinHashEntry
      36             : {
      37             :     Relids      join_relids;    /* hash key --- MUST BE FIRST */
      38             :     RelOptInfo *join_rel;
      39             : } JoinHashEntry;
      40             : 
      41             : static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
      42             :                                 RelOptInfo *input_rel);
      43             : static List *build_joinrel_restrictlist(PlannerInfo *root,
      44             :                                         RelOptInfo *joinrel,
      45             :                                         RelOptInfo *outer_rel,
      46             :                                         RelOptInfo *inner_rel);
      47             : static void build_joinrel_joinlist(RelOptInfo *joinrel,
      48             :                                    RelOptInfo *outer_rel,
      49             :                                    RelOptInfo *inner_rel);
      50             : static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
      51             :                                            List *joininfo_list,
      52             :                                            List *new_restrictlist);
      53             : static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
      54             :                                        List *joininfo_list,
      55             :                                        List *new_joininfo);
      56             : static void set_foreign_rel_properties(RelOptInfo *joinrel,
      57             :                                        RelOptInfo *outer_rel, RelOptInfo *inner_rel);
      58             : static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel);
      59             : static void build_joinrel_partition_info(RelOptInfo *joinrel,
      60             :                                          RelOptInfo *outer_rel, RelOptInfo *inner_rel,
      61             :                                          List *restrictlist, JoinType jointype);
      62             : static bool have_partkey_equi_join(RelOptInfo *joinrel,
      63             :                                    RelOptInfo *rel1, RelOptInfo *rel2,
      64             :                                    JoinType jointype, List *restrictlist);
      65             : static int  match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel,
      66             :                                          bool strict_op);
      67             : static void set_joinrel_partition_key_exprs(RelOptInfo *joinrel,
      68             :                                             RelOptInfo *outer_rel, RelOptInfo *inner_rel,
      69             :                                             JoinType jointype);
      70             : static void build_child_join_reltarget(PlannerInfo *root,
      71             :                                        RelOptInfo *parentrel,
      72             :                                        RelOptInfo *childrel,
      73             :                                        int nappinfos,
      74             :                                        AppendRelInfo **appinfos);
      75             : 
      76             : 
      77             : /*
      78             :  * setup_simple_rel_arrays
      79             :  *    Prepare the arrays we use for quickly accessing base relations
      80             :  *    and AppendRelInfos.
      81             :  */
      82             : void
      83      356072 : setup_simple_rel_arrays(PlannerInfo *root)
      84             : {
      85             :     int         size;
      86             :     Index       rti;
      87             :     ListCell   *lc;
      88             : 
      89             :     /* Arrays are accessed using RT indexes (1..N) */
      90      356072 :     size = list_length(root->parse->rtable) + 1;
      91      356072 :     root->simple_rel_array_size = size;
      92             : 
      93             :     /*
      94             :      * simple_rel_array is initialized to all NULLs, since no RelOptInfos
      95             :      * exist yet.  It'll be filled by later calls to build_simple_rel().
      96             :      */
      97      356072 :     root->simple_rel_array = (RelOptInfo **)
      98      356072 :         palloc0(size * sizeof(RelOptInfo *));
      99             : 
     100             :     /* simple_rte_array is an array equivalent of the rtable list */
     101      356072 :     root->simple_rte_array = (RangeTblEntry **)
     102      356072 :         palloc0(size * sizeof(RangeTblEntry *));
     103      356072 :     rti = 1;
     104     1001724 :     foreach(lc, root->parse->rtable)
     105             :     {
     106      645652 :         RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
     107             : 
     108      645652 :         root->simple_rte_array[rti++] = rte;
     109             :     }
     110             : 
     111             :     /* append_rel_array is not needed if there are no AppendRelInfos */
     112      356072 :     if (root->append_rel_list == NIL)
     113             :     {
     114      353920 :         root->append_rel_array = NULL;
     115      353920 :         return;
     116             :     }
     117             : 
     118        2152 :     root->append_rel_array = (AppendRelInfo **)
     119        2152 :         palloc0(size * sizeof(AppendRelInfo *));
     120             : 
     121             :     /*
     122             :      * append_rel_array is filled with any already-existing AppendRelInfos,
     123             :      * which currently could only come from UNION ALL flattening.  We might
     124             :      * add more later during inheritance expansion, but it's the
     125             :      * responsibility of the expansion code to update the array properly.
     126             :      */
     127        6808 :     foreach(lc, root->append_rel_list)
     128             :     {
     129        4656 :         AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc);
     130        4656 :         int         child_relid = appinfo->child_relid;
     131             : 
     132             :         /* Sanity check */
     133             :         Assert(child_relid < size);
     134             : 
     135        4656 :         if (root->append_rel_array[child_relid])
     136           0 :             elog(ERROR, "child relation already exists");
     137             : 
     138        4656 :         root->append_rel_array[child_relid] = appinfo;
     139             :     }
     140             : }
     141             : 
     142             : /*
     143             :  * expand_planner_arrays
     144             :  *      Expand the PlannerInfo's per-RTE arrays by add_size members
     145             :  *      and initialize the newly added entries to NULLs
     146             :  *
     147             :  * Note: this causes the append_rel_array to become allocated even if
     148             :  * it was not before.  This is okay for current uses, because we only call
     149             :  * this when adding child relations, which always have AppendRelInfos.
     150             :  */
     151             : void
     152       11472 : expand_planner_arrays(PlannerInfo *root, int add_size)
     153             : {
     154             :     int         new_size;
     155             : 
     156             :     Assert(add_size > 0);
     157             : 
     158       11472 :     new_size = root->simple_rel_array_size + add_size;
     159             : 
     160       11472 :     root->simple_rel_array = (RelOptInfo **)
     161       11472 :         repalloc(root->simple_rel_array,
     162             :                  sizeof(RelOptInfo *) * new_size);
     163       35158 :     MemSet(root->simple_rel_array + root->simple_rel_array_size,
     164             :            0, sizeof(RelOptInfo *) * add_size);
     165             : 
     166       11472 :     root->simple_rte_array = (RangeTblEntry **)
     167       11472 :         repalloc(root->simple_rte_array,
     168             :                  sizeof(RangeTblEntry *) * new_size);
     169       35158 :     MemSet(root->simple_rte_array + root->simple_rel_array_size,
     170             :            0, sizeof(RangeTblEntry *) * add_size);
     171             : 
     172       11472 :     if (root->append_rel_array)
     173             :     {
     174        3228 :         root->append_rel_array = (AppendRelInfo **)
     175        3228 :             repalloc(root->append_rel_array,
     176             :                      sizeof(AppendRelInfo *) * new_size);
     177       10614 :         MemSet(root->append_rel_array + root->simple_rel_array_size,
     178             :                0, sizeof(AppendRelInfo *) * add_size);
     179             :     }
     180             :     else
     181             :     {
     182        8244 :         root->append_rel_array = (AppendRelInfo **)
     183        8244 :             palloc0(sizeof(AppendRelInfo *) * new_size);
     184             :     }
     185             : 
     186       11472 :     root->simple_rel_array_size = new_size;
     187       11472 : }
     188             : 
     189             : /*
     190             :  * build_simple_rel
     191             :  *    Construct a new RelOptInfo for a base relation or 'other' relation.
     192             :  */
     193             : RelOptInfo *
     194      462472 : build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
     195             : {
     196             :     RelOptInfo *rel;
     197             :     RangeTblEntry *rte;
     198             : 
     199             :     /* Rel should not exist already */
     200             :     Assert(relid > 0 && relid < root->simple_rel_array_size);
     201      462472 :     if (root->simple_rel_array[relid] != NULL)
     202           0 :         elog(ERROR, "rel %d already exists", relid);
     203             : 
     204             :     /* Fetch RTE for relation */
     205      462472 :     rte = root->simple_rte_array[relid];
     206             :     Assert(rte != NULL);
     207             : 
     208      462472 :     rel = makeNode(RelOptInfo);
     209      462472 :     rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL;
     210      462472 :     rel->relids = bms_make_singleton(relid);
     211      462472 :     rel->rows = 0;
     212             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
     213      462472 :     rel->consider_startup = (root->tuple_fraction > 0);
     214      462472 :     rel->consider_param_startup = false; /* might get changed later */
     215      462472 :     rel->consider_parallel = false; /* might get changed later */
     216      462472 :     rel->reltarget = create_empty_pathtarget();
     217      462472 :     rel->pathlist = NIL;
     218      462472 :     rel->ppilist = NIL;
     219      462472 :     rel->partial_pathlist = NIL;
     220      462472 :     rel->cheapest_startup_path = NULL;
     221      462472 :     rel->cheapest_total_path = NULL;
     222      462472 :     rel->cheapest_unique_path = NULL;
     223      462472 :     rel->cheapest_parameterized_paths = NIL;
     224      462472 :     rel->relid = relid;
     225      462472 :     rel->rtekind = rte->rtekind;
     226             :     /* min_attr, max_attr, attr_needed, attr_widths are set below */
     227      462472 :     rel->lateral_vars = NIL;
     228      462472 :     rel->indexlist = NIL;
     229      462472 :     rel->statlist = NIL;
     230      462472 :     rel->pages = 0;
     231      462472 :     rel->tuples = 0;
     232      462472 :     rel->allvisfrac = 0;
     233      462472 :     rel->eclass_indexes = NULL;
     234      462472 :     rel->subroot = NULL;
     235      462472 :     rel->subplan_params = NIL;
     236      462472 :     rel->rel_parallel_workers = -1; /* set up in get_relation_info */
     237      462472 :     rel->serverid = InvalidOid;
     238      462472 :     rel->userid = rte->checkAsUser;
     239      462472 :     rel->useridiscurrent = false;
     240      462472 :     rel->fdwroutine = NULL;
     241      462472 :     rel->fdw_private = NULL;
     242      462472 :     rel->unique_for_rels = NIL;
     243      462472 :     rel->non_unique_for_rels = NIL;
     244      462472 :     rel->baserestrictinfo = NIL;
     245      462472 :     rel->baserestrictcost.startup = 0;
     246      462472 :     rel->baserestrictcost.per_tuple = 0;
     247      462472 :     rel->baserestrict_min_security = UINT_MAX;
     248      462472 :     rel->joininfo = NIL;
     249      462472 :     rel->has_eclass_joins = false;
     250      462472 :     rel->consider_partitionwise_join = false;    /* might get changed later */
     251      462472 :     rel->part_scheme = NULL;
     252      462472 :     rel->nparts = -1;
     253      462472 :     rel->boundinfo = NULL;
     254      462472 :     rel->partbounds_merged = false;
     255      462472 :     rel->partition_qual = NIL;
     256      462472 :     rel->part_rels = NULL;
     257      462472 :     rel->all_partrels = NULL;
     258      462472 :     rel->partexprs = NULL;
     259      462472 :     rel->nullable_partexprs = NULL;
     260             : 
     261             :     /*
     262             :      * Pass assorted information down the inheritance hierarchy.
     263             :      */
     264      462472 :     if (parent)
     265             :     {
     266             :         /*
     267             :          * Each direct or indirect child wants to know the relids of its
     268             :          * topmost parent.
     269             :          */
     270       28298 :         if (parent->top_parent_relids)
     271        4098 :             rel->top_parent_relids = parent->top_parent_relids;
     272             :         else
     273       24200 :             rel->top_parent_relids = bms_copy(parent->relids);
     274             : 
     275             :         /*
     276             :          * Also propagate lateral-reference information from appendrel parent
     277             :          * rels to their child rels.  We intentionally give each child rel the
     278             :          * same minimum parameterization, even though it's quite possible that
     279             :          * some don't reference all the lateral rels.  This is because any
     280             :          * append path for the parent will have to have the same
     281             :          * parameterization for every child anyway, and there's no value in
     282             :          * forcing extra reparameterize_path() calls.  Similarly, a lateral
     283             :          * reference to the parent prevents use of otherwise-movable join rels
     284             :          * for each child.
     285             :          *
     286             :          * It's possible for child rels to have their own children, in which
     287             :          * case the topmost parent's lateral info propagates all the way down.
     288             :          */
     289       28298 :         rel->direct_lateral_relids = parent->direct_lateral_relids;
     290       28298 :         rel->lateral_relids = parent->lateral_relids;
     291       28298 :         rel->lateral_referencers = parent->lateral_referencers;
     292             :     }
     293             :     else
     294             :     {
     295      434174 :         rel->top_parent_relids = NULL;
     296      434174 :         rel->direct_lateral_relids = NULL;
     297      434174 :         rel->lateral_relids = NULL;
     298      434174 :         rel->lateral_referencers = NULL;
     299             :     }
     300             : 
     301             :     /* Check type of rtable entry */
     302      462472 :     switch (rte->rtekind)
     303             :     {
     304      286404 :         case RTE_RELATION:
     305             :             /* Table --- retrieve statistics from the system catalogs */
     306      286404 :             get_relation_info(root, rte->relid, rte->inh, rel);
     307      286394 :             break;
     308       52446 :         case RTE_SUBQUERY:
     309             :         case RTE_FUNCTION:
     310             :         case RTE_TABLEFUNC:
     311             :         case RTE_VALUES:
     312             :         case RTE_CTE:
     313             :         case RTE_NAMEDTUPLESTORE:
     314             : 
     315             :             /*
     316             :              * Subquery, function, tablefunc, values list, CTE, or ENR --- set
     317             :              * up attr range and arrays
     318             :              *
     319             :              * Note: 0 is included in range to support whole-row Vars
     320             :              */
     321       52446 :             rel->min_attr = 0;
     322       52446 :             rel->max_attr = list_length(rte->eref->colnames);
     323       52446 :             rel->attr_needed = (Relids *)
     324       52446 :                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
     325       52446 :             rel->attr_widths = (int32 *)
     326       52446 :                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
     327       52446 :             break;
     328      123622 :         case RTE_RESULT:
     329             :             /* RTE_RESULT has no columns, nor could it have whole-row Var */
     330      123622 :             rel->min_attr = 0;
     331      123622 :             rel->max_attr = -1;
     332      123622 :             rel->attr_needed = NULL;
     333      123622 :             rel->attr_widths = NULL;
     334      123622 :             break;
     335           0 :         default:
     336           0 :             elog(ERROR, "unrecognized RTE kind: %d",
     337             :                  (int) rte->rtekind);
     338             :             break;
     339             :     }
     340             : 
     341             :     /*
     342             :      * Copy the parent's quals to the child, with appropriate substitution of
     343             :      * variables.  If any constant false or NULL clauses turn up, we can mark
     344             :      * the child as dummy right away.  (We must do this immediately so that
     345             :      * pruning works correctly when recursing in expand_partitioned_rtentry.)
     346             :      */
     347      462462 :     if (parent)
     348             :     {
     349       28298 :         AppendRelInfo *appinfo = root->append_rel_array[relid];
     350             : 
     351             :         Assert(appinfo != NULL);
     352       28298 :         if (!apply_child_basequals(root, parent, rel, rte, appinfo))
     353             :         {
     354             :             /*
     355             :              * Some restriction clause reduced to constant FALSE or NULL after
     356             :              * substitution, so this child need not be scanned.
     357             :              */
     358          52 :             mark_dummy_rel(rel);
     359             :         }
     360             :     }
     361             : 
     362             :     /* Save the finished struct in the query's simple_rel_array */
     363      462462 :     root->simple_rel_array[relid] = rel;
     364             : 
     365      462462 :     return rel;
     366             : }
     367             : 
     368             : /*
     369             :  * find_base_rel
     370             :  *    Find a base or other relation entry, which must already exist.
     371             :  */
     372             : RelOptInfo *
     373     3840782 : find_base_rel(PlannerInfo *root, int relid)
     374             : {
     375             :     RelOptInfo *rel;
     376             : 
     377             :     Assert(relid > 0);
     378             : 
     379     3840782 :     if (relid < root->simple_rel_array_size)
     380             :     {
     381     3840782 :         rel = root->simple_rel_array[relid];
     382     3840782 :         if (rel)
     383     3840782 :             return rel;
     384             :     }
     385             : 
     386           0 :     elog(ERROR, "no relation entry for relid %d", relid);
     387             : 
     388             :     return NULL;                /* keep compiler quiet */
     389             : }
     390             : 
     391             : /*
     392             :  * build_join_rel_hash
     393             :  *    Construct the auxiliary hash table for join relations.
     394             :  */
     395             : static void
     396          20 : build_join_rel_hash(PlannerInfo *root)
     397             : {
     398             :     HTAB       *hashtab;
     399             :     HASHCTL     hash_ctl;
     400             :     ListCell   *l;
     401             : 
     402             :     /* Create the hash table */
     403          20 :     hash_ctl.keysize = sizeof(Relids);
     404          20 :     hash_ctl.entrysize = sizeof(JoinHashEntry);
     405          20 :     hash_ctl.hash = bitmap_hash;
     406          20 :     hash_ctl.match = bitmap_match;
     407          20 :     hash_ctl.hcxt = CurrentMemoryContext;
     408          20 :     hashtab = hash_create("JoinRelHashTable",
     409             :                           256L,
     410             :                           &hash_ctl,
     411             :                           HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
     412             : 
     413             :     /* Insert all the already-existing joinrels */
     414         680 :     foreach(l, root->join_rel_list)
     415             :     {
     416         660 :         RelOptInfo *rel = (RelOptInfo *) lfirst(l);
     417             :         JoinHashEntry *hentry;
     418             :         bool        found;
     419             : 
     420         660 :         hentry = (JoinHashEntry *) hash_search(hashtab,
     421         660 :                                                &(rel->relids),
     422             :                                                HASH_ENTER,
     423             :                                                &found);
     424             :         Assert(!found);
     425         660 :         hentry->join_rel = rel;
     426             :     }
     427             : 
     428          20 :     root->join_rel_hash = hashtab;
     429          20 : }
     430             : 
     431             : /*
     432             :  * find_join_rel
     433             :  *    Returns relation entry corresponding to 'relids' (a set of RT indexes),
     434             :  *    or NULL if none exists.  This is for join relations.
     435             :  */
     436             : RelOptInfo *
     437      161314 : find_join_rel(PlannerInfo *root, Relids relids)
     438             : {
     439             :     /*
     440             :      * Switch to using hash lookup when list grows "too long".  The threshold
     441             :      * is arbitrary and is known only here.
     442             :      */
     443      161314 :     if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
     444          20 :         build_join_rel_hash(root);
     445             : 
     446             :     /*
     447             :      * Use either hashtable lookup or linear search, as appropriate.
     448             :      *
     449             :      * Note: the seemingly redundant hashkey variable is used to avoid taking
     450             :      * the address of relids; unless the compiler is exceedingly smart, doing
     451             :      * so would force relids out of a register and thus probably slow down the
     452             :      * list-search case.
     453             :      */
     454      161314 :     if (root->join_rel_hash)
     455             :     {
     456        2312 :         Relids      hashkey = relids;
     457             :         JoinHashEntry *hentry;
     458             : 
     459        2312 :         hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
     460             :                                                &hashkey,
     461             :                                                HASH_FIND,
     462             :                                                NULL);
     463        2312 :         if (hentry)
     464        2052 :             return hentry->join_rel;
     465             :     }
     466             :     else
     467             :     {
     468             :         ListCell   *l;
     469             : 
     470      942474 :         foreach(l, root->join_rel_list)
     471             :         {
     472      840428 :             RelOptInfo *rel = (RelOptInfo *) lfirst(l);
     473             : 
     474      840428 :             if (bms_equal(rel->relids, relids))
     475       56956 :                 return rel;
     476             :         }
     477             :     }
     478             : 
     479      102306 :     return NULL;
     480             : }
     481             : 
     482             : /*
     483             :  * set_foreign_rel_properties
     484             :  *      Set up foreign-join fields if outer and inner relation are foreign
     485             :  *      tables (or joins) belonging to the same server and assigned to the same
     486             :  *      user to check access permissions as.
     487             :  *
     488             :  * In addition to an exact match of userid, we allow the case where one side
     489             :  * has zero userid (implying current user) and the other side has explicit
     490             :  * userid that happens to equal the current user; but in that case, pushdown of
     491             :  * the join is only valid for the current user.  The useridiscurrent field
     492             :  * records whether we had to make such an assumption for this join or any
     493             :  * sub-join.
     494             :  *
     495             :  * Otherwise these fields are left invalid, so GetForeignJoinPaths will not be
     496             :  * called for the join relation.
     497             :  *
     498             :  */
     499             : static void
     500      103552 : set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel,
     501             :                            RelOptInfo *inner_rel)
     502             : {
     503      103552 :     if (OidIsValid(outer_rel->serverid) &&
     504         580 :         inner_rel->serverid == outer_rel->serverid)
     505             :     {
     506         496 :         if (inner_rel->userid == outer_rel->userid)
     507             :         {
     508         484 :             joinrel->serverid = outer_rel->serverid;
     509         484 :             joinrel->userid = outer_rel->userid;
     510         484 :             joinrel->useridiscurrent = outer_rel->useridiscurrent || inner_rel->useridiscurrent;
     511         484 :             joinrel->fdwroutine = outer_rel->fdwroutine;
     512             :         }
     513          20 :         else if (!OidIsValid(inner_rel->userid) &&
     514           8 :                  outer_rel->userid == GetUserId())
     515             :         {
     516           4 :             joinrel->serverid = outer_rel->serverid;
     517           4 :             joinrel->userid = outer_rel->userid;
     518           4 :             joinrel->useridiscurrent = true;
     519           4 :             joinrel->fdwroutine = outer_rel->fdwroutine;
     520             :         }
     521           8 :         else if (!OidIsValid(outer_rel->userid) &&
     522           0 :                  inner_rel->userid == GetUserId())
     523             :         {
     524           0 :             joinrel->serverid = outer_rel->serverid;
     525           0 :             joinrel->userid = inner_rel->userid;
     526           0 :             joinrel->useridiscurrent = true;
     527           0 :             joinrel->fdwroutine = outer_rel->fdwroutine;
     528             :         }
     529             :     }
     530      103552 : }
     531             : 
     532             : /*
     533             :  * add_join_rel
     534             :  *      Add given join relation to the list of join relations in the given
     535             :  *      PlannerInfo. Also add it to the auxiliary hashtable if there is one.
     536             :  */
     537             : static void
     538      103552 : add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
     539             : {
     540             :     /* GEQO requires us to append the new joinrel to the end of the list! */
     541      103552 :     root->join_rel_list = lappend(root->join_rel_list, joinrel);
     542             : 
     543             :     /* store it into the auxiliary hashtable if there is one. */
     544      103552 :     if (root->join_rel_hash)
     545             :     {
     546             :         JoinHashEntry *hentry;
     547             :         bool        found;
     548             : 
     549         260 :         hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
     550         260 :                                                &(joinrel->relids),
     551             :                                                HASH_ENTER,
     552             :                                                &found);
     553             :         Assert(!found);
     554         260 :         hentry->join_rel = joinrel;
     555             :     }
     556      103552 : }
     557             : 
     558             : /*
     559             :  * build_join_rel
     560             :  *    Returns relation entry corresponding to the union of two given rels,
     561             :  *    creating a new relation entry if none already exists.
     562             :  *
     563             :  * 'joinrelids' is the Relids set that uniquely identifies the join
     564             :  * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
     565             :  *      joined
     566             :  * 'sjinfo': join context info
     567             :  * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
     568             :  *      receives the list of RestrictInfo nodes that apply to this
     569             :  *      particular pair of joinable relations.
     570             :  *
     571             :  * restrictlist_ptr makes the routine's API a little grotty, but it saves
     572             :  * duplicated calculation of the restrictlist...
     573             :  */
     574             : RelOptInfo *
     575      157486 : build_join_rel(PlannerInfo *root,
     576             :                Relids joinrelids,
     577             :                RelOptInfo *outer_rel,
     578             :                RelOptInfo *inner_rel,
     579             :                SpecialJoinInfo *sjinfo,
     580             :                List **restrictlist_ptr)
     581             : {
     582             :     RelOptInfo *joinrel;
     583             :     List       *restrictlist;
     584             : 
     585             :     /* This function should be used only for join between parents. */
     586             :     Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel));
     587             : 
     588             :     /*
     589             :      * See if we already have a joinrel for this set of base rels.
     590             :      */
     591      157486 :     joinrel = find_join_rel(root, joinrelids);
     592             : 
     593      157486 :     if (joinrel)
     594             :     {
     595             :         /*
     596             :          * Yes, so we only need to figure the restrictlist for this particular
     597             :          * pair of component relations.
     598             :          */
     599       56778 :         if (restrictlist_ptr)
     600       56778 :             *restrictlist_ptr = build_joinrel_restrictlist(root,
     601             :                                                            joinrel,
     602             :                                                            outer_rel,
     603             :                                                            inner_rel);
     604       56778 :         return joinrel;
     605             :     }
     606             : 
     607             :     /*
     608             :      * Nope, so make one.
     609             :      */
     610      100708 :     joinrel = makeNode(RelOptInfo);
     611      100708 :     joinrel->reloptkind = RELOPT_JOINREL;
     612      100708 :     joinrel->relids = bms_copy(joinrelids);
     613      100708 :     joinrel->rows = 0;
     614             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
     615      100708 :     joinrel->consider_startup = (root->tuple_fraction > 0);
     616      100708 :     joinrel->consider_param_startup = false;
     617      100708 :     joinrel->consider_parallel = false;
     618      100708 :     joinrel->reltarget = create_empty_pathtarget();
     619      100708 :     joinrel->pathlist = NIL;
     620      100708 :     joinrel->ppilist = NIL;
     621      100708 :     joinrel->partial_pathlist = NIL;
     622      100708 :     joinrel->cheapest_startup_path = NULL;
     623      100708 :     joinrel->cheapest_total_path = NULL;
     624      100708 :     joinrel->cheapest_unique_path = NULL;
     625      100708 :     joinrel->cheapest_parameterized_paths = NIL;
     626             :     /* init direct_lateral_relids from children; we'll finish it up below */
     627      100708 :     joinrel->direct_lateral_relids =
     628      100708 :         bms_union(outer_rel->direct_lateral_relids,
     629      100708 :                   inner_rel->direct_lateral_relids);
     630      100708 :     joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids,
     631             :                                                         outer_rel, inner_rel);
     632      100708 :     joinrel->relid = 0;          /* indicates not a baserel */
     633      100708 :     joinrel->rtekind = RTE_JOIN;
     634      100708 :     joinrel->min_attr = 0;
     635      100708 :     joinrel->max_attr = 0;
     636      100708 :     joinrel->attr_needed = NULL;
     637      100708 :     joinrel->attr_widths = NULL;
     638      100708 :     joinrel->lateral_vars = NIL;
     639      100708 :     joinrel->lateral_referencers = NULL;
     640      100708 :     joinrel->indexlist = NIL;
     641      100708 :     joinrel->statlist = NIL;
     642      100708 :     joinrel->pages = 0;
     643      100708 :     joinrel->tuples = 0;
     644      100708 :     joinrel->allvisfrac = 0;
     645      100708 :     joinrel->eclass_indexes = NULL;
     646      100708 :     joinrel->subroot = NULL;
     647      100708 :     joinrel->subplan_params = NIL;
     648      100708 :     joinrel->rel_parallel_workers = -1;
     649      100708 :     joinrel->serverid = InvalidOid;
     650      100708 :     joinrel->userid = InvalidOid;
     651      100708 :     joinrel->useridiscurrent = false;
     652      100708 :     joinrel->fdwroutine = NULL;
     653      100708 :     joinrel->fdw_private = NULL;
     654      100708 :     joinrel->unique_for_rels = NIL;
     655      100708 :     joinrel->non_unique_for_rels = NIL;
     656      100708 :     joinrel->baserestrictinfo = NIL;
     657      100708 :     joinrel->baserestrictcost.startup = 0;
     658      100708 :     joinrel->baserestrictcost.per_tuple = 0;
     659      100708 :     joinrel->baserestrict_min_security = UINT_MAX;
     660      100708 :     joinrel->joininfo = NIL;
     661      100708 :     joinrel->has_eclass_joins = false;
     662      100708 :     joinrel->consider_partitionwise_join = false;    /* might get changed later */
     663      100708 :     joinrel->top_parent_relids = NULL;
     664      100708 :     joinrel->part_scheme = NULL;
     665      100708 :     joinrel->nparts = -1;
     666      100708 :     joinrel->boundinfo = NULL;
     667      100708 :     joinrel->partbounds_merged = false;
     668      100708 :     joinrel->partition_qual = NIL;
     669      100708 :     joinrel->part_rels = NULL;
     670      100708 :     joinrel->all_partrels = NULL;
     671      100708 :     joinrel->partexprs = NULL;
     672      100708 :     joinrel->nullable_partexprs = NULL;
     673             : 
     674             :     /* Compute information relevant to the foreign relations. */
     675      100708 :     set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
     676             : 
     677             :     /*
     678             :      * Create a new tlist containing just the vars that need to be output from
     679             :      * this join (ie, are needed for higher joinclauses or final output).
     680             :      *
     681             :      * NOTE: the tlist order for a join rel will depend on which pair of outer
     682             :      * and inner rels we first try to build it from.  But the contents should
     683             :      * be the same regardless.
     684             :      */
     685      100708 :     build_joinrel_tlist(root, joinrel, outer_rel);
     686      100708 :     build_joinrel_tlist(root, joinrel, inner_rel);
     687      100708 :     add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel);
     688             : 
     689             :     /*
     690             :      * add_placeholders_to_joinrel also took care of adding the ph_lateral
     691             :      * sets of any PlaceHolderVars computed here to direct_lateral_relids, so
     692             :      * now we can finish computing that.  This is much like the computation of
     693             :      * the transitively-closed lateral_relids in min_join_parameterization,
     694             :      * except that here we *do* have to consider the added PHVs.
     695             :      */
     696      100708 :     joinrel->direct_lateral_relids =
     697      100708 :         bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
     698      100708 :     if (bms_is_empty(joinrel->direct_lateral_relids))
     699      100322 :         joinrel->direct_lateral_relids = NULL;
     700             : 
     701             :     /*
     702             :      * Construct restrict and join clause lists for the new joinrel. (The
     703             :      * caller might or might not need the restrictlist, but I need it anyway
     704             :      * for set_joinrel_size_estimates().)
     705             :      */
     706      100708 :     restrictlist = build_joinrel_restrictlist(root, joinrel,
     707             :                                               outer_rel, inner_rel);
     708      100708 :     if (restrictlist_ptr)
     709      100708 :         *restrictlist_ptr = restrictlist;
     710      100708 :     build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
     711             : 
     712             :     /*
     713             :      * This is also the right place to check whether the joinrel has any
     714             :      * pending EquivalenceClass joins.
     715             :      */
     716      100708 :     joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
     717             : 
     718             :     /* Store the partition information. */
     719      100708 :     build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist,
     720             :                                  sjinfo->jointype);
     721             : 
     722             :     /*
     723             :      * Set estimates of the joinrel's size.
     724             :      */
     725      100708 :     set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
     726             :                                sjinfo, restrictlist);
     727             : 
     728             :     /*
     729             :      * Set the consider_parallel flag if this joinrel could potentially be
     730             :      * scanned within a parallel worker.  If this flag is false for either
     731             :      * inner_rel or outer_rel, then it must be false for the joinrel also.
     732             :      * Even if both are true, there might be parallel-restricted expressions
     733             :      * in the targetlist or quals.
     734             :      *
     735             :      * Note that if there are more than two rels in this relation, they could
     736             :      * be divided between inner_rel and outer_rel in any arbitrary way.  We
     737             :      * assume this doesn't matter, because we should hit all the same baserels
     738             :      * and joinclauses while building up to this joinrel no matter which we
     739             :      * take; therefore, we should make the same decision here however we get
     740             :      * here.
     741             :      */
     742      177926 :     if (inner_rel->consider_parallel && outer_rel->consider_parallel &&
     743      153734 :         is_parallel_safe(root, (Node *) restrictlist) &&
     744       76516 :         is_parallel_safe(root, (Node *) joinrel->reltarget->exprs))
     745       76512 :         joinrel->consider_parallel = true;
     746             : 
     747             :     /* Add the joinrel to the PlannerInfo. */
     748      100708 :     add_join_rel(root, joinrel);
     749             : 
     750             :     /*
     751             :      * Also, if dynamic-programming join search is active, add the new joinrel
     752             :      * to the appropriate sublist.  Note: you might think the Assert on number
     753             :      * of members should be for equality, but some of the level 1 rels might
     754             :      * have been joinrels already, so we can only assert <=.
     755             :      */
     756      100708 :     if (root->join_rel_level)
     757             :     {
     758             :         Assert(root->join_cur_level > 0);
     759             :         Assert(root->join_cur_level <= bms_num_members(joinrel->relids));
     760       98644 :         root->join_rel_level[root->join_cur_level] =
     761       98644 :             lappend(root->join_rel_level[root->join_cur_level], joinrel);
     762             :     }
     763             : 
     764      100708 :     return joinrel;
     765             : }
     766             : 
     767             : /*
     768             :  * build_child_join_rel
     769             :  *    Builds RelOptInfo representing join between given two child relations.
     770             :  *
     771             :  * 'outer_rel' and 'inner_rel' are the RelOptInfos of child relations being
     772             :  *      joined
     773             :  * 'parent_joinrel' is the RelOptInfo representing the join between parent
     774             :  *      relations. Some of the members of new RelOptInfo are produced by
     775             :  *      translating corresponding members of this RelOptInfo
     776             :  * 'sjinfo': child-join context info
     777             :  * 'restrictlist': list of RestrictInfo nodes that apply to this particular
     778             :  *      pair of joinable relations
     779             :  * 'jointype' is the join type (inner, left, full, etc)
     780             :  */
     781             : RelOptInfo *
     782        2844 : build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
     783             :                      RelOptInfo *inner_rel, RelOptInfo *parent_joinrel,
     784             :                      List *restrictlist, SpecialJoinInfo *sjinfo,
     785             :                      JoinType jointype)
     786             : {
     787        2844 :     RelOptInfo *joinrel = makeNode(RelOptInfo);
     788             :     AppendRelInfo **appinfos;
     789             :     int         nappinfos;
     790             : 
     791             :     /* Only joins between "other" relations land here. */
     792             :     Assert(IS_OTHER_REL(outer_rel) && IS_OTHER_REL(inner_rel));
     793             : 
     794             :     /* The parent joinrel should have consider_partitionwise_join set. */
     795             :     Assert(parent_joinrel->consider_partitionwise_join);
     796             : 
     797        2844 :     joinrel->reloptkind = RELOPT_OTHER_JOINREL;
     798        2844 :     joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids);
     799        2844 :     joinrel->rows = 0;
     800             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
     801        2844 :     joinrel->consider_startup = (root->tuple_fraction > 0);
     802        2844 :     joinrel->consider_param_startup = false;
     803        2844 :     joinrel->consider_parallel = false;
     804        2844 :     joinrel->reltarget = create_empty_pathtarget();
     805        2844 :     joinrel->pathlist = NIL;
     806        2844 :     joinrel->ppilist = NIL;
     807        2844 :     joinrel->partial_pathlist = NIL;
     808        2844 :     joinrel->cheapest_startup_path = NULL;
     809        2844 :     joinrel->cheapest_total_path = NULL;
     810        2844 :     joinrel->cheapest_unique_path = NULL;
     811        2844 :     joinrel->cheapest_parameterized_paths = NIL;
     812        2844 :     joinrel->direct_lateral_relids = NULL;
     813        2844 :     joinrel->lateral_relids = NULL;
     814        2844 :     joinrel->relid = 0;          /* indicates not a baserel */
     815        2844 :     joinrel->rtekind = RTE_JOIN;
     816        2844 :     joinrel->min_attr = 0;
     817        2844 :     joinrel->max_attr = 0;
     818        2844 :     joinrel->attr_needed = NULL;
     819        2844 :     joinrel->attr_widths = NULL;
     820        2844 :     joinrel->lateral_vars = NIL;
     821        2844 :     joinrel->lateral_referencers = NULL;
     822        2844 :     joinrel->indexlist = NIL;
     823        2844 :     joinrel->pages = 0;
     824        2844 :     joinrel->tuples = 0;
     825        2844 :     joinrel->allvisfrac = 0;
     826        2844 :     joinrel->eclass_indexes = NULL;
     827        2844 :     joinrel->subroot = NULL;
     828        2844 :     joinrel->subplan_params = NIL;
     829        2844 :     joinrel->serverid = InvalidOid;
     830        2844 :     joinrel->userid = InvalidOid;
     831        2844 :     joinrel->useridiscurrent = false;
     832        2844 :     joinrel->fdwroutine = NULL;
     833        2844 :     joinrel->fdw_private = NULL;
     834        2844 :     joinrel->baserestrictinfo = NIL;
     835        2844 :     joinrel->baserestrictcost.startup = 0;
     836        2844 :     joinrel->baserestrictcost.per_tuple = 0;
     837        2844 :     joinrel->joininfo = NIL;
     838        2844 :     joinrel->has_eclass_joins = false;
     839        2844 :     joinrel->consider_partitionwise_join = false;    /* might get changed later */
     840        2844 :     joinrel->top_parent_relids = NULL;
     841        2844 :     joinrel->part_scheme = NULL;
     842        2844 :     joinrel->nparts = -1;
     843        2844 :     joinrel->boundinfo = NULL;
     844        2844 :     joinrel->partbounds_merged = false;
     845        2844 :     joinrel->partition_qual = NIL;
     846        2844 :     joinrel->part_rels = NULL;
     847        2844 :     joinrel->all_partrels = NULL;
     848        2844 :     joinrel->partexprs = NULL;
     849        2844 :     joinrel->nullable_partexprs = NULL;
     850             : 
     851        5688 :     joinrel->top_parent_relids = bms_union(outer_rel->top_parent_relids,
     852        2844 :                                            inner_rel->top_parent_relids);
     853             : 
     854             :     /* Compute information relevant to foreign relations. */
     855        2844 :     set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
     856             : 
     857             :     /* Compute information needed for mapping Vars to the child rel */
     858        2844 :     appinfos = find_appinfos_by_relids(root, joinrel->relids, &nappinfos);
     859             : 
     860             :     /* Set up reltarget struct */
     861        2844 :     build_child_join_reltarget(root, parent_joinrel, joinrel,
     862             :                                nappinfos, appinfos);
     863             : 
     864             :     /* Construct joininfo list. */
     865        8532 :     joinrel->joininfo = (List *) adjust_appendrel_attrs(root,
     866        2844 :                                                         (Node *) parent_joinrel->joininfo,
     867             :                                                         nappinfos,
     868             :                                                         appinfos);
     869             : 
     870             :     /*
     871             :      * Lateral relids referred in child join will be same as that referred in
     872             :      * the parent relation.
     873             :      */
     874        2844 :     joinrel->direct_lateral_relids = (Relids) bms_copy(parent_joinrel->direct_lateral_relids);
     875        2844 :     joinrel->lateral_relids = (Relids) bms_copy(parent_joinrel->lateral_relids);
     876             : 
     877             :     /*
     878             :      * If the parent joinrel has pending equivalence classes, so does the
     879             :      * child.
     880             :      */
     881        2844 :     joinrel->has_eclass_joins = parent_joinrel->has_eclass_joins;
     882             : 
     883             :     /* Is the join between partitions itself partitioned? */
     884        2844 :     build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist,
     885             :                                  jointype);
     886             : 
     887             :     /* Child joinrel is parallel safe if parent is parallel safe. */
     888        2844 :     joinrel->consider_parallel = parent_joinrel->consider_parallel;
     889             : 
     890             :     /* Set estimates of the child-joinrel's size. */
     891        2844 :     set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
     892             :                                sjinfo, restrictlist);
     893             : 
     894             :     /* We build the join only once. */
     895             :     Assert(!find_join_rel(root, joinrel->relids));
     896             : 
     897             :     /* Add the relation to the PlannerInfo. */
     898        2844 :     add_join_rel(root, joinrel);
     899             : 
     900             :     /*
     901             :      * We might need EquivalenceClass members corresponding to the child join,
     902             :      * so that we can represent sort pathkeys for it.  As with children of
     903             :      * baserels, we shouldn't need this unless there are relevant eclass joins
     904             :      * (implying that a merge join might be possible) or pathkeys to sort by.
     905             :      */
     906        2844 :     if (joinrel->has_eclass_joins || has_useful_pathkeys(root, parent_joinrel))
     907        2740 :         add_child_join_rel_equivalences(root,
     908             :                                         nappinfos, appinfos,
     909             :                                         parent_joinrel, joinrel);
     910             : 
     911        2844 :     pfree(appinfos);
     912             : 
     913        2844 :     return joinrel;
     914             : }
     915             : 
     916             : /*
     917             :  * min_join_parameterization
     918             :  *
     919             :  * Determine the minimum possible parameterization of a joinrel, that is, the
     920             :  * set of other rels it contains LATERAL references to.  We save this value in
     921             :  * the join's RelOptInfo.  This function is split out of build_join_rel()
     922             :  * because join_is_legal() needs the value to check a prospective join.
     923             :  */
     924             : Relids
     925      104186 : min_join_parameterization(PlannerInfo *root,
     926             :                           Relids joinrelids,
     927             :                           RelOptInfo *outer_rel,
     928             :                           RelOptInfo *inner_rel)
     929             : {
     930             :     Relids      result;
     931             : 
     932             :     /*
     933             :      * Basically we just need the union of the inputs' lateral_relids, less
     934             :      * whatever is already in the join.
     935             :      *
     936             :      * It's not immediately obvious that this is a valid way to compute the
     937             :      * result, because it might seem that we're ignoring possible lateral refs
     938             :      * of PlaceHolderVars that are due to be computed at the join but not in
     939             :      * either input.  However, because create_lateral_join_info() already
     940             :      * charged all such PHV refs to each member baserel of the join, they'll
     941             :      * be accounted for already in the inputs' lateral_relids.  Likewise, we
     942             :      * do not need to worry about doing transitive closure here, because that
     943             :      * was already accounted for in the original baserel lateral_relids.
     944             :      */
     945      104186 :     result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
     946      104186 :     result = bms_del_members(result, joinrelids);
     947             : 
     948             :     /* Maintain invariant that result is exactly NULL if empty */
     949      104186 :     if (bms_is_empty(result))
     950      103084 :         result = NULL;
     951             : 
     952      104186 :     return result;
     953             : }
     954             : 
     955             : /*
     956             :  * build_joinrel_tlist
     957             :  *    Builds a join relation's target list from an input relation.
     958             :  *    (This is invoked twice to handle the two input relations.)
     959             :  *
     960             :  * The join's targetlist includes all Vars of its member relations that
     961             :  * will still be needed above the join.  This subroutine adds all such
     962             :  * Vars from the specified input rel's tlist to the join rel's tlist.
     963             :  *
     964             :  * We also compute the expected width of the join's output, making use
     965             :  * of data that was cached at the baserel level by set_rel_width().
     966             :  */
     967             : static void
     968      201416 : build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
     969             :                     RelOptInfo *input_rel)
     970             : {
     971      201416 :     Relids      relids = joinrel->relids;
     972             :     ListCell   *vars;
     973             : 
     974     1150356 :     foreach(vars, input_rel->reltarget->exprs)
     975             :     {
     976      948940 :         Var        *var = (Var *) lfirst(vars);
     977             :         RelOptInfo *baserel;
     978             :         int         ndx;
     979             : 
     980             :         /*
     981             :          * Ignore PlaceHolderVars in the input tlists; we'll make our own
     982             :          * decisions about whether to copy them.
     983             :          */
     984      948940 :         if (IsA(var, PlaceHolderVar))
     985         828 :             continue;
     986             : 
     987             :         /*
     988             :          * Otherwise, anything in a baserel or joinrel targetlist ought to be
     989             :          * a Var.  (More general cases can only appear in appendrel child
     990             :          * rels, which will never be seen here.)
     991             :          */
     992      948112 :         if (!IsA(var, Var))
     993           0 :             elog(ERROR, "unexpected node type in rel targetlist: %d",
     994             :                  (int) nodeTag(var));
     995             : 
     996             :         /* Get the Var's original base rel */
     997      948112 :         baserel = find_base_rel(root, var->varno);
     998             : 
     999             :         /* Is it still needed above this joinrel? */
    1000      948112 :         ndx = var->varattno - baserel->min_attr;
    1001      948112 :         if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
    1002             :         {
    1003             :             /* Yup, add it to the output */
    1004      801966 :             joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, var);
    1005             :             /* Vars have cost zero, so no need to adjust reltarget->cost */
    1006      801966 :             joinrel->reltarget->width += baserel->attr_widths[ndx];
    1007             :         }
    1008             :     }
    1009      201416 : }
    1010             : 
    1011             : /*
    1012             :  * build_joinrel_restrictlist
    1013             :  * build_joinrel_joinlist
    1014             :  *    These routines build lists of restriction and join clauses for a
    1015             :  *    join relation from the joininfo lists of the relations it joins.
    1016             :  *
    1017             :  *    These routines are separate because the restriction list must be
    1018             :  *    built afresh for each pair of input sub-relations we consider, whereas
    1019             :  *    the join list need only be computed once for any join RelOptInfo.
    1020             :  *    The join list is fully determined by the set of rels making up the
    1021             :  *    joinrel, so we should get the same results (up to ordering) from any
    1022             :  *    candidate pair of sub-relations.  But the restriction list is whatever
    1023             :  *    is not handled in the sub-relations, so it depends on which
    1024             :  *    sub-relations are considered.
    1025             :  *
    1026             :  *    If a join clause from an input relation refers to base rels still not
    1027             :  *    present in the joinrel, then it is still a join clause for the joinrel;
    1028             :  *    we put it into the joininfo list for the joinrel.  Otherwise,
    1029             :  *    the clause is now a restrict clause for the joined relation, and we
    1030             :  *    return it to the caller of build_joinrel_restrictlist() to be stored in
    1031             :  *    join paths made from this pair of sub-relations.  (It will not need to
    1032             :  *    be considered further up the join tree.)
    1033             :  *
    1034             :  *    In many cases we will find the same RestrictInfos in both input
    1035             :  *    relations' joinlists, so be careful to eliminate duplicates.
    1036             :  *    Pointer equality should be a sufficient test for dups, since all
    1037             :  *    the various joinlist entries ultimately refer to RestrictInfos
    1038             :  *    pushed into them by distribute_restrictinfo_to_rels().
    1039             :  *
    1040             :  * 'joinrel' is a join relation node
    1041             :  * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
    1042             :  *      to form joinrel.
    1043             :  *
    1044             :  * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
    1045             :  * whereas build_joinrel_joinlist() stores its results in the joinrel's
    1046             :  * joininfo list.  One or the other must accept each given clause!
    1047             :  *
    1048             :  * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
    1049             :  * up to the join relation.  I believe this is no longer necessary, because
    1050             :  * RestrictInfo nodes are no longer context-dependent.  Instead, just include
    1051             :  * the original nodes in the lists made for the join relation.
    1052             :  */
    1053             : static List *
    1054      157486 : build_joinrel_restrictlist(PlannerInfo *root,
    1055             :                            RelOptInfo *joinrel,
    1056             :                            RelOptInfo *outer_rel,
    1057             :                            RelOptInfo *inner_rel)
    1058             : {
    1059             :     List       *result;
    1060             : 
    1061             :     /*
    1062             :      * Collect all the clauses that syntactically belong at this level,
    1063             :      * eliminating any duplicates (important since we will see many of the
    1064             :      * same clauses arriving from both input relations).
    1065             :      */
    1066      157486 :     result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
    1067      157486 :     result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);
    1068             : 
    1069             :     /*
    1070             :      * Add on any clauses derived from EquivalenceClasses.  These cannot be
    1071             :      * redundant with the clauses in the joininfo lists, so don't bother
    1072             :      * checking.
    1073             :      */
    1074      157486 :     result = list_concat(result,
    1075      157486 :                          generate_join_implied_equalities(root,
    1076             :                                                           joinrel->relids,
    1077             :                                                           outer_rel->relids,
    1078             :                                                           inner_rel));
    1079             : 
    1080      157486 :     return result;
    1081             : }
    1082             : 
    1083             : static void
    1084      100708 : build_joinrel_joinlist(RelOptInfo *joinrel,
    1085             :                        RelOptInfo *outer_rel,
    1086             :                        RelOptInfo *inner_rel)
    1087             : {
    1088             :     List       *result;
    1089             : 
    1090             :     /*
    1091             :      * Collect all the clauses that syntactically belong above this level,
    1092             :      * eliminating any duplicates (important since we will see many of the
    1093             :      * same clauses arriving from both input relations).
    1094             :      */
    1095      100708 :     result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
    1096      100708 :     result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);
    1097             : 
    1098      100708 :     joinrel->joininfo = result;
    1099      100708 : }
    1100             : 
    1101             : static List *
    1102      314972 : subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
    1103             :                               List *joininfo_list,
    1104             :                               List *new_restrictlist)
    1105             : {
    1106             :     ListCell   *l;
    1107             : 
    1108      672960 :     foreach(l, joininfo_list)
    1109             :     {
    1110      357988 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
    1111             : 
    1112      357988 :         if (bms_is_subset(rinfo->required_relids, joinrel->relids))
    1113             :         {
    1114             :             /*
    1115             :              * This clause becomes a restriction clause for the joinrel, since
    1116             :              * it refers to no outside rels.  Add it to the list, being
    1117             :              * careful to eliminate duplicates. (Since RestrictInfo nodes in
    1118             :              * different joinlists will have been multiply-linked rather than
    1119             :              * copied, pointer equality should be a sufficient test.)
    1120             :              */
    1121      221460 :             new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
    1122             :         }
    1123             :         else
    1124             :         {
    1125             :             /*
    1126             :              * This clause is still a join clause at this level, so we ignore
    1127             :              * it in this routine.
    1128             :              */
    1129             :         }
    1130             :     }
    1131             : 
    1132      314972 :     return new_restrictlist;
    1133             : }
    1134             : 
    1135             : static List *
    1136      201416 : subbuild_joinrel_joinlist(RelOptInfo *joinrel,
    1137             :                           List *joininfo_list,
    1138             :                           List *new_joininfo)
    1139             : {
    1140             :     ListCell   *l;
    1141             : 
    1142             :     /* Expected to be called only for join between parent relations. */
    1143             :     Assert(joinrel->reloptkind == RELOPT_JOINREL);
    1144             : 
    1145      427038 :     foreach(l, joininfo_list)
    1146             :     {
    1147      225622 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
    1148             : 
    1149      225622 :         if (bms_is_subset(rinfo->required_relids, joinrel->relids))
    1150             :         {
    1151             :             /*
    1152             :              * This clause becomes a restriction clause for the joinrel, since
    1153             :              * it refers to no outside rels.  So we can ignore it in this
    1154             :              * routine.
    1155             :              */
    1156             :         }
    1157             :         else
    1158             :         {
    1159             :             /*
    1160             :              * This clause is still a join clause at this level, so add it to
    1161             :              * the new joininfo list, being careful to eliminate duplicates.
    1162             :              * (Since RestrictInfo nodes in different joinlists will have been
    1163             :              * multiply-linked rather than copied, pointer equality should be
    1164             :              * a sufficient test.)
    1165             :              */
    1166       80034 :             new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
    1167             :         }
    1168             :     }
    1169             : 
    1170      201416 :     return new_joininfo;
    1171             : }
    1172             : 
    1173             : 
    1174             : /*
    1175             :  * fetch_upper_rel
    1176             :  *      Build a RelOptInfo describing some post-scan/join query processing,
    1177             :  *      or return a pre-existing one if somebody already built it.
    1178             :  *
    1179             :  * An "upper" relation is identified by an UpperRelationKind and a Relids set.
    1180             :  * The meaning of the Relids set is not specified here, and very likely will
    1181             :  * vary for different relation kinds.
    1182             :  *
    1183             :  * Most of the fields in an upper-level RelOptInfo are not used and are not
    1184             :  * set here (though makeNode should ensure they're zeroes).  We basically only
    1185             :  * care about fields that are of interest to add_path() and set_cheapest().
    1186             :  */
    1187             : RelOptInfo *
    1188     1095402 : fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
    1189             : {
    1190             :     RelOptInfo *upperrel;
    1191             :     ListCell   *lc;
    1192             : 
    1193             :     /*
    1194             :      * For the moment, our indexing data structure is just a List for each
    1195             :      * relation kind.  If we ever get so many of one kind that this stops
    1196             :      * working well, we can improve it.  No code outside this function should
    1197             :      * assume anything about how to find a particular upperrel.
    1198             :      */
    1199             : 
    1200             :     /* If we already made this upperrel for the query, return it */
    1201     1100702 :     foreach(lc, root->upper_rels[kind])
    1202             :     {
    1203      690120 :         upperrel = (RelOptInfo *) lfirst(lc);
    1204             : 
    1205      690120 :         if (bms_equal(upperrel->relids, relids))
    1206      684820 :             return upperrel;
    1207             :     }
    1208             : 
    1209      410582 :     upperrel = makeNode(RelOptInfo);
    1210      410582 :     upperrel->reloptkind = RELOPT_UPPER_REL;
    1211      410582 :     upperrel->relids = bms_copy(relids);
    1212             : 
    1213             :     /* cheap startup cost is interesting iff not all tuples to be retrieved */
    1214      410582 :     upperrel->consider_startup = (root->tuple_fraction > 0);
    1215      410582 :     upperrel->consider_param_startup = false;
    1216      410582 :     upperrel->consider_parallel = false; /* might get changed later */
    1217      410582 :     upperrel->reltarget = create_empty_pathtarget();
    1218      410582 :     upperrel->pathlist = NIL;
    1219      410582 :     upperrel->cheapest_startup_path = NULL;
    1220      410582 :     upperrel->cheapest_total_path = NULL;
    1221      410582 :     upperrel->cheapest_unique_path = NULL;
    1222      410582 :     upperrel->cheapest_parameterized_paths = NIL;
    1223             : 
    1224      410582 :     root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
    1225             : 
    1226      410582 :     return upperrel;
    1227             : }
    1228             : 
    1229             : 
    1230             : /*
    1231             :  * find_childrel_parents
    1232             :  *      Compute the set of parent relids of an appendrel child rel.
    1233             :  *
    1234             :  * Since appendrels can be nested, a child could have multiple levels of
    1235             :  * appendrel ancestors.  This function computes a Relids set of all the
    1236             :  * parent relation IDs.
    1237             :  */
    1238             : Relids
    1239        6984 : find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
    1240             : {
    1241        6984 :     Relids      result = NULL;
    1242             : 
    1243             :     Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
    1244             :     Assert(rel->relid > 0 && rel->relid < root->simple_rel_array_size);
    1245             : 
    1246             :     do
    1247             :     {
    1248        8472 :         AppendRelInfo *appinfo = root->append_rel_array[rel->relid];
    1249        8472 :         Index       prelid = appinfo->parent_relid;
    1250             : 
    1251        8472 :         result = bms_add_member(result, prelid);
    1252             : 
    1253             :         /* traverse up to the parent rel, loop if it's also a child rel */
    1254        8472 :         rel = find_base_rel(root, prelid);
    1255        8472 :     } while (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
    1256             : 
    1257             :     Assert(rel->reloptkind == RELOPT_BASEREL);
    1258             : 
    1259        6984 :     return result;
    1260             : }
    1261             : 
    1262             : 
    1263             : /*
    1264             :  * get_baserel_parampathinfo
    1265             :  *      Get the ParamPathInfo for a parameterized path for a base relation,
    1266             :  *      constructing one if we don't have one already.
    1267             :  *
    1268             :  * This centralizes estimating the rowcounts for parameterized paths.
    1269             :  * We need to cache those to be sure we use the same rowcount for all paths
    1270             :  * of the same parameterization for a given rel.  This is also a convenient
    1271             :  * place to determine which movable join clauses the parameterized path will
    1272             :  * be responsible for evaluating.
    1273             :  */
    1274             : ParamPathInfo *
    1275      968578 : get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel,
    1276             :                           Relids required_outer)
    1277             : {
    1278             :     ParamPathInfo *ppi;
    1279             :     Relids      joinrelids;
    1280             :     List       *pclauses;
    1281             :     double      rows;
    1282             :     ListCell   *lc;
    1283             : 
    1284             :     /* If rel has LATERAL refs, every path for it should account for them */
    1285             :     Assert(bms_is_subset(baserel->lateral_relids, required_outer));
    1286             : 
    1287             :     /* Unparameterized paths have no ParamPathInfo */
    1288      968578 :     if (bms_is_empty(required_outer))
    1289      832814 :         return NULL;
    1290             : 
    1291             :     Assert(!bms_overlap(baserel->relids, required_outer));
    1292             : 
    1293             :     /* If we already have a PPI for this parameterization, just return it */
    1294      135764 :     if ((ppi = find_param_path_info(baserel, required_outer)))
    1295       71068 :         return ppi;
    1296             : 
    1297             :     /*
    1298             :      * Identify all joinclauses that are movable to this base rel given this
    1299             :      * parameterization.
    1300             :      */
    1301       64696 :     joinrelids = bms_union(baserel->relids, required_outer);
    1302       64696 :     pclauses = NIL;
    1303      109994 :     foreach(lc, baserel->joininfo)
    1304             :     {
    1305       45298 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1306             : 
    1307       45298 :         if (join_clause_is_movable_into(rinfo,
    1308             :                                         baserel->relids,
    1309             :                                         joinrelids))
    1310       28898 :             pclauses = lappend(pclauses, rinfo);
    1311             :     }
    1312             : 
    1313             :     /*
    1314             :      * Add in joinclauses generated by EquivalenceClasses, too.  (These
    1315             :      * necessarily satisfy join_clause_is_movable_into.)
    1316             :      */
    1317       64696 :     pclauses = list_concat(pclauses,
    1318       64696 :                            generate_join_implied_equalities(root,
    1319             :                                                             joinrelids,
    1320             :                                                             required_outer,
    1321             :                                                             baserel));
    1322             : 
    1323             :     /* Estimate the number of rows returned by the parameterized scan */
    1324       64696 :     rows = get_parameterized_baserel_size(root, baserel, pclauses);
    1325             : 
    1326             :     /* And now we can build the ParamPathInfo */
    1327       64696 :     ppi = makeNode(ParamPathInfo);
    1328       64696 :     ppi->ppi_req_outer = required_outer;
    1329       64696 :     ppi->ppi_rows = rows;
    1330       64696 :     ppi->ppi_clauses = pclauses;
    1331       64696 :     baserel->ppilist = lappend(baserel->ppilist, ppi);
    1332             : 
    1333       64696 :     return ppi;
    1334             : }
    1335             : 
    1336             : /*
    1337             :  * get_joinrel_parampathinfo
    1338             :  *      Get the ParamPathInfo for a parameterized path for a join relation,
    1339             :  *      constructing one if we don't have one already.
    1340             :  *
    1341             :  * This centralizes estimating the rowcounts for parameterized paths.
    1342             :  * We need to cache those to be sure we use the same rowcount for all paths
    1343             :  * of the same parameterization for a given rel.  This is also a convenient
    1344             :  * place to determine which movable join clauses the parameterized path will
    1345             :  * be responsible for evaluating.
    1346             :  *
    1347             :  * outer_path and inner_path are a pair of input paths that can be used to
    1348             :  * construct the join, and restrict_clauses is the list of regular join
    1349             :  * clauses (including clauses derived from EquivalenceClasses) that must be
    1350             :  * applied at the join node when using these inputs.
    1351             :  *
    1352             :  * Unlike the situation for base rels, the set of movable join clauses to be
    1353             :  * enforced at a join varies with the selected pair of input paths, so we
    1354             :  * must calculate that and pass it back, even if we already have a matching
    1355             :  * ParamPathInfo.  We handle this by adding any clauses moved down to this
    1356             :  * join to *restrict_clauses, which is an in/out parameter.  (The addition
    1357             :  * is done in such a way as to not modify the passed-in List structure.)
    1358             :  *
    1359             :  * Note: when considering a nestloop join, the caller must have removed from
    1360             :  * restrict_clauses any movable clauses that are themselves scheduled to be
    1361             :  * pushed into the right-hand path.  We do not do that here since it's
    1362             :  * unnecessary for other join types.
    1363             :  */
    1364             : ParamPathInfo *
    1365      913280 : get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
    1366             :                           Path *outer_path,
    1367             :                           Path *inner_path,
    1368             :                           SpecialJoinInfo *sjinfo,
    1369             :                           Relids required_outer,
    1370             :                           List **restrict_clauses)
    1371             : {
    1372             :     ParamPathInfo *ppi;
    1373             :     Relids      join_and_req;
    1374             :     Relids      outer_and_req;
    1375             :     Relids      inner_and_req;
    1376             :     List       *pclauses;
    1377             :     List       *eclauses;
    1378             :     List       *dropped_ecs;
    1379             :     double      rows;
    1380             :     ListCell   *lc;
    1381             : 
    1382             :     /* If rel has LATERAL refs, every path for it should account for them */
    1383             :     Assert(bms_is_subset(joinrel->lateral_relids, required_outer));
    1384             : 
    1385             :     /* Unparameterized paths have no ParamPathInfo or extra join clauses */
    1386      913280 :     if (bms_is_empty(required_outer))
    1387      906986 :         return NULL;
    1388             : 
    1389             :     Assert(!bms_overlap(joinrel->relids, required_outer));
    1390             : 
    1391             :     /*
    1392             :      * Identify all joinclauses that are movable to this join rel given this
    1393             :      * parameterization.  These are the clauses that are movable into this
    1394             :      * join, but not movable into either input path.  Treat an unparameterized
    1395             :      * input path as not accepting parameterized clauses (because it won't,
    1396             :      * per the shortcut exit above), even though the joinclause movement rules
    1397             :      * might allow the same clauses to be moved into a parameterized path for
    1398             :      * that rel.
    1399             :      */
    1400        6294 :     join_and_req = bms_union(joinrel->relids, required_outer);
    1401        6294 :     if (outer_path->param_info)
    1402        5424 :         outer_and_req = bms_union(outer_path->parent->relids,
    1403        5424 :                                   PATH_REQ_OUTER(outer_path));
    1404             :     else
    1405         870 :         outer_and_req = NULL;   /* outer path does not accept parameters */
    1406        6294 :     if (inner_path->param_info)
    1407        2924 :         inner_and_req = bms_union(inner_path->parent->relids,
    1408        2924 :                                   PATH_REQ_OUTER(inner_path));
    1409             :     else
    1410        3370 :         inner_and_req = NULL;   /* inner path does not accept parameters */
    1411             : 
    1412        6294 :     pclauses = NIL;
    1413       12202 :     foreach(lc, joinrel->joininfo)
    1414             :     {
    1415        5908 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1416             : 
    1417        5908 :         if (join_clause_is_movable_into(rinfo,
    1418             :                                         joinrel->relids,
    1419        4428 :                                         join_and_req) &&
    1420        4428 :             !join_clause_is_movable_into(rinfo,
    1421        4428 :                                          outer_path->parent->relids,
    1422         554 :                                          outer_and_req) &&
    1423         554 :             !join_clause_is_movable_into(rinfo,
    1424         554 :                                          inner_path->parent->relids,
    1425             :                                          inner_and_req))
    1426          48 :             pclauses = lappend(pclauses, rinfo);
    1427             :     }
    1428             : 
    1429             :     /* Consider joinclauses generated by EquivalenceClasses, too */
    1430        6294 :     eclauses = generate_join_implied_equalities(root,
    1431             :                                                 join_and_req,
    1432             :                                                 required_outer,
    1433             :                                                 joinrel);
    1434             :     /* We only want ones that aren't movable to lower levels */
    1435        6294 :     dropped_ecs = NIL;
    1436        7644 :     foreach(lc, eclauses)
    1437             :     {
    1438        1350 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1439             : 
    1440             :         /*
    1441             :          * In principle, join_clause_is_movable_into() should accept anything
    1442             :          * returned by generate_join_implied_equalities(); but because its
    1443             :          * analysis is only approximate, sometimes it doesn't.  So we
    1444             :          * currently cannot use this Assert; instead just assume it's okay to
    1445             :          * apply the joinclause at this level.
    1446             :          */
    1447             : #ifdef NOT_USED
    1448             :         Assert(join_clause_is_movable_into(rinfo,
    1449             :                                            joinrel->relids,
    1450             :                                            join_and_req));
    1451             : #endif
    1452        1350 :         if (join_clause_is_movable_into(rinfo,
    1453        1350 :                                         outer_path->parent->relids,
    1454             :                                         outer_and_req))
    1455         616 :             continue;           /* drop if movable into LHS */
    1456         734 :         if (join_clause_is_movable_into(rinfo,
    1457         734 :                                         inner_path->parent->relids,
    1458             :                                         inner_and_req))
    1459             :         {
    1460             :             /* drop if movable into RHS, but remember EC for use below */
    1461             :             Assert(rinfo->left_ec == rinfo->right_ec);
    1462         478 :             dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
    1463         478 :             continue;
    1464             :         }
    1465         256 :         pclauses = lappend(pclauses, rinfo);
    1466             :     }
    1467             : 
    1468             :     /*
    1469             :      * EquivalenceClasses are harder to deal with than we could wish, because
    1470             :      * of the fact that a given EC can generate different clauses depending on
    1471             :      * context.  Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
    1472             :      * LHS and RHS of the current join and Z is in required_outer, and further
    1473             :      * suppose that the inner_path is parameterized by both X and Z.  The code
    1474             :      * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
    1475             :      * and in the latter case will have discarded it as being movable into the
    1476             :      * RHS.  However, the EC machinery might have produced either Y.Y = X.X or
    1477             :      * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
    1478             :      * not have produced both, and we can't readily tell from here which one
    1479             :      * it did pick.  If we add no clause to this join, we'll end up with
    1480             :      * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
    1481             :      * constrained to be equal to the other members of the EC.  (When we come
    1482             :      * to join Z to this X/Y path, we will certainly drop whichever EC clause
    1483             :      * is generated at that join, so this omission won't get fixed later.)
    1484             :      *
    1485             :      * To handle this, for each EC we discarded such a clause from, try to
    1486             :      * generate a clause connecting the required_outer rels to the join's LHS
    1487             :      * ("Z.Z = X.X" in the terms of the above example).  If successful, and if
    1488             :      * the clause can't be moved to the LHS, add it to the current join's
    1489             :      * restriction clauses.  (If an EC cannot generate such a clause then it
    1490             :      * has nothing that needs to be enforced here, while if the clause can be
    1491             :      * moved into the LHS then it should have been enforced within that path.)
    1492             :      *
    1493             :      * Note that we don't need similar processing for ECs whose clause was
    1494             :      * considered to be movable into the LHS, because the LHS can't refer to
    1495             :      * the RHS so there is no comparable ambiguity about what it might
    1496             :      * actually be enforcing internally.
    1497             :      */
    1498        6294 :     if (dropped_ecs)
    1499             :     {
    1500             :         Relids      real_outer_and_req;
    1501             : 
    1502         458 :         real_outer_and_req = bms_union(outer_path->parent->relids,
    1503             :                                        required_outer);
    1504             :         eclauses =
    1505         458 :             generate_join_implied_equalities_for_ecs(root,
    1506             :                                                      dropped_ecs,
    1507             :                                                      real_outer_and_req,
    1508             :                                                      required_outer,
    1509             :                                                      outer_path->parent);
    1510         486 :         foreach(lc, eclauses)
    1511             :         {
    1512          28 :             RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
    1513             : 
    1514             :             /* As above, can't quite assert this here */
    1515             : #ifdef NOT_USED
    1516             :             Assert(join_clause_is_movable_into(rinfo,
    1517             :                                                outer_path->parent->relids,
    1518             :                                                real_outer_and_req));
    1519             : #endif
    1520          28 :             if (!join_clause_is_movable_into(rinfo,
    1521          28 :                                              outer_path->parent->relids,
    1522             :                                              outer_and_req))
    1523          20 :                 pclauses = lappend(pclauses, rinfo);
    1524             :         }
    1525             :     }
    1526             : 
    1527             :     /*
    1528             :      * Now, attach the identified moved-down clauses to the caller's
    1529             :      * restrict_clauses list.  By using list_concat in this order, we leave
    1530             :      * the original list structure of restrict_clauses undamaged.
    1531             :      */
    1532        6294 :     *restrict_clauses = list_concat(pclauses, *restrict_clauses);
    1533             : 
    1534             :     /* If we already have a PPI for this parameterization, just return it */
    1535        6294 :     if ((ppi = find_param_path_info(joinrel, required_outer)))
    1536        4406 :         return ppi;
    1537             : 
    1538             :     /* Estimate the number of rows returned by the parameterized join */
    1539        1888 :     rows = get_parameterized_joinrel_size(root, joinrel,
    1540             :                                           outer_path,
    1541             :                                           inner_path,
    1542             :                                           sjinfo,
    1543             :                                           *restrict_clauses);
    1544             : 
    1545             :     /*
    1546             :      * And now we can build the ParamPathInfo.  No point in saving the
    1547             :      * input-pair-dependent clause list, though.
    1548             :      *
    1549             :      * Note: in GEQO mode, we'll be called in a temporary memory context, but
    1550             :      * the joinrel structure is there too, so no problem.
    1551             :      */
    1552        1888 :     ppi = makeNode(ParamPathInfo);
    1553        1888 :     ppi->ppi_req_outer = required_outer;
    1554        1888 :     ppi->ppi_rows = rows;
    1555        1888 :     ppi->ppi_clauses = NIL;
    1556        1888 :     joinrel->ppilist = lappend(joinrel->ppilist, ppi);
    1557             : 
    1558        1888 :     return ppi;
    1559             : }
    1560             : 
    1561             : /*
    1562             :  * get_appendrel_parampathinfo
    1563             :  *      Get the ParamPathInfo for a parameterized path for an append relation.
    1564             :  *
    1565             :  * For an append relation, the rowcount estimate will just be the sum of
    1566             :  * the estimates for its children.  However, we still need a ParamPathInfo
    1567             :  * to flag the fact that the path requires parameters.  So this just creates
    1568             :  * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
    1569             :  * the Append node isn't responsible for checking quals).
    1570             :  */
    1571             : ParamPathInfo *
    1572       20680 : get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer)
    1573             : {
    1574             :     ParamPathInfo *ppi;
    1575             : 
    1576             :     /* If rel has LATERAL refs, every path for it should account for them */
    1577             :     Assert(bms_is_subset(appendrel->lateral_relids, required_outer));
    1578             : 
    1579             :     /* Unparameterized paths have no ParamPathInfo */
    1580       20680 :     if (bms_is_empty(required_outer))
    1581       20224 :         return NULL;
    1582             : 
    1583             :     Assert(!bms_overlap(appendrel->relids, required_outer));
    1584             : 
    1585             :     /* If we already have a PPI for this parameterization, just return it */
    1586         456 :     if ((ppi = find_param_path_info(appendrel, required_outer)))
    1587          64 :         return ppi;
    1588             : 
    1589             :     /* Else build the ParamPathInfo */
    1590         392 :     ppi = makeNode(ParamPathInfo);
    1591         392 :     ppi->ppi_req_outer = required_outer;
    1592         392 :     ppi->ppi_rows = 0;
    1593         392 :     ppi->ppi_clauses = NIL;
    1594         392 :     appendrel->ppilist = lappend(appendrel->ppilist, ppi);
    1595             : 
    1596         392 :     return ppi;
    1597             : }
    1598             : 
    1599             : /*
    1600             :  * Returns a ParamPathInfo for the parameterization given by required_outer, if
    1601             :  * already available in the given rel. Returns NULL otherwise.
    1602             :  */
    1603             : ParamPathInfo *
    1604      145358 : find_param_path_info(RelOptInfo *rel, Relids required_outer)
    1605             : {
    1606             :     ListCell   *lc;
    1607             : 
    1608      162100 :     foreach(lc, rel->ppilist)
    1609             :     {
    1610       93808 :         ParamPathInfo *ppi = (ParamPathInfo *) lfirst(lc);
    1611             : 
    1612       93808 :         if (bms_equal(ppi->ppi_req_outer, required_outer))
    1613       77066 :             return ppi;
    1614             :     }
    1615             : 
    1616       68292 :     return NULL;
    1617             : }
    1618             : 
    1619             : /*
    1620             :  * build_joinrel_partition_info
    1621             :  *      Checks if the two relations being joined can use partitionwise join
    1622             :  *      and if yes, initialize partitioning information of the resulting
    1623             :  *      partitioned join relation.
    1624             :  */
    1625             : static void
    1626      103552 : build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
    1627             :                              RelOptInfo *inner_rel, List *restrictlist,
    1628             :                              JoinType jointype)
    1629             : {
    1630             :     PartitionScheme part_scheme;
    1631             : 
    1632             :     /* Nothing to do if partitionwise join technique is disabled. */
    1633      103552 :     if (!enable_partitionwise_join)
    1634             :     {
    1635             :         Assert(!IS_PARTITIONED_REL(joinrel));
    1636       99464 :         return;
    1637             :     }
    1638             : 
    1639             :     /*
    1640             :      * We can only consider this join as an input to further partitionwise
    1641             :      * joins if (a) the input relations are partitioned and have
    1642             :      * consider_partitionwise_join=true, (b) the partition schemes match, and
    1643             :      * (c) we can identify an equi-join between the partition keys.  Note that
    1644             :      * if it were possible for have_partkey_equi_join to return different
    1645             :      * answers for the same joinrel depending on which join ordering we try
    1646             :      * first, this logic would break.  That shouldn't happen, though, because
    1647             :      * of the way the query planner deduces implied equalities and reorders
    1648             :      * the joins.  Please see optimizer/README for details.
    1649             :      */
    1650        4088 :     if (outer_rel->part_scheme == NULL || inner_rel->part_scheme == NULL ||
    1651        1340 :         !outer_rel->consider_partitionwise_join ||
    1652        1308 :         !inner_rel->consider_partitionwise_join ||
    1653        1308 :         outer_rel->part_scheme != inner_rel->part_scheme ||
    1654        1292 :         !have_partkey_equi_join(joinrel, outer_rel, inner_rel,
    1655             :                                 jointype, restrictlist))
    1656             :     {
    1657             :         Assert(!IS_PARTITIONED_REL(joinrel));
    1658        2888 :         return;
    1659             :     }
    1660             : 
    1661        1200 :     part_scheme = outer_rel->part_scheme;
    1662             : 
    1663             :     /*
    1664             :      * This function will be called only once for each joinrel, hence it
    1665             :      * should not have partitioning fields filled yet.
    1666             :      */
    1667             :     Assert(!joinrel->part_scheme && !joinrel->partexprs &&
    1668             :            !joinrel->nullable_partexprs && !joinrel->part_rels &&
    1669             :            !joinrel->boundinfo);
    1670             : 
    1671             :     /*
    1672             :      * If the join relation is partitioned, it uses the same partitioning
    1673             :      * scheme as the joining relations.
    1674             :      *
    1675             :      * Note: we calculate the partition bounds, number of partitions, and
    1676             :      * child-join relations of the join relation in try_partitionwise_join().
    1677             :      */
    1678        1200 :     joinrel->part_scheme = part_scheme;
    1679        1200 :     set_joinrel_partition_key_exprs(joinrel, outer_rel, inner_rel, jointype);
    1680             : 
    1681             :     /*
    1682             :      * Set the consider_partitionwise_join flag.
    1683             :      */
    1684             :     Assert(outer_rel->consider_partitionwise_join);
    1685             :     Assert(inner_rel->consider_partitionwise_join);
    1686        1200 :     joinrel->consider_partitionwise_join = true;
    1687             : }
    1688             : 
    1689             : /*
    1690             :  * have_partkey_equi_join
    1691             :  *
    1692             :  * Returns true if there exist equi-join conditions involving pairs
    1693             :  * of matching partition keys of the relations being joined for all
    1694             :  * partition keys.
    1695             :  */
    1696             : static bool
    1697        1292 : have_partkey_equi_join(RelOptInfo *joinrel,
    1698             :                        RelOptInfo *rel1, RelOptInfo *rel2,
    1699             :                        JoinType jointype, List *restrictlist)
    1700             : {
    1701        1292 :     PartitionScheme part_scheme = rel1->part_scheme;
    1702             :     ListCell   *lc;
    1703             :     int         cnt_pks;
    1704             :     bool        pk_has_clause[PARTITION_MAX_KEYS];
    1705             :     bool        strict_op;
    1706             : 
    1707             :     /*
    1708             :      * This function must only be called when the joined relations have same
    1709             :      * partitioning scheme.
    1710             :      */
    1711             :     Assert(rel1->part_scheme == rel2->part_scheme);
    1712             :     Assert(part_scheme);
    1713             : 
    1714        1292 :     memset(pk_has_clause, 0, sizeof(pk_has_clause));
    1715        3404 :     foreach(lc, restrictlist)
    1716             :     {
    1717        2112 :         RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
    1718             :         OpExpr     *opexpr;
    1719             :         Expr       *expr1;
    1720             :         Expr       *expr2;
    1721             :         int         ipk1;
    1722             :         int         ipk2;
    1723             : 
    1724             :         /* If processing an outer join, only use its own join clauses. */
    1725        2112 :         if (IS_OUTER_JOIN(jointype) &&
    1726        1244 :             RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
    1727         212 :             continue;
    1728             : 
    1729             :         /* Skip clauses which can not be used for a join. */
    1730        1900 :         if (!rinfo->can_join)
    1731          12 :             continue;
    1732             : 
    1733             :         /* Skip clauses which are not equality conditions. */
    1734        1888 :         if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
    1735           4 :             continue;
    1736             : 
    1737             :         /* Should be OK to assume it's an OpExpr. */
    1738        1884 :         opexpr = castNode(OpExpr, rinfo->clause);
    1739             : 
    1740             :         /* Match the operands to the relation. */
    1741        3636 :         if (bms_is_subset(rinfo->left_relids, rel1->relids) &&
    1742        1752 :             bms_is_subset(rinfo->right_relids, rel2->relids))
    1743             :         {
    1744        1752 :             expr1 = linitial(opexpr->args);
    1745        1752 :             expr2 = lsecond(opexpr->args);
    1746             :         }
    1747         264 :         else if (bms_is_subset(rinfo->left_relids, rel2->relids) &&
    1748         132 :                  bms_is_subset(rinfo->right_relids, rel1->relids))
    1749             :         {
    1750         132 :             expr1 = lsecond(opexpr->args);
    1751         132 :             expr2 = linitial(opexpr->args);
    1752             :         }
    1753             :         else
    1754           0 :             continue;
    1755             : 
    1756             :         /*
    1757             :          * Now we need to know whether the join operator is strict; see
    1758             :          * comments in pathnodes.h.
    1759             :          */
    1760        1884 :         strict_op = op_strict(opexpr->opno);
    1761             : 
    1762             :         /*
    1763             :          * Only clauses referencing the partition keys are useful for
    1764             :          * partitionwise join.
    1765             :          */
    1766        1884 :         ipk1 = match_expr_to_partition_keys(expr1, rel1, strict_op);
    1767        1884 :         if (ipk1 < 0)
    1768         668 :             continue;
    1769        1216 :         ipk2 = match_expr_to_partition_keys(expr2, rel2, strict_op);
    1770        1216 :         if (ipk2 < 0)
    1771           0 :             continue;
    1772             : 
    1773             :         /*
    1774             :          * If the clause refers to keys at different ordinal positions, it can
    1775             :          * not be used for partitionwise join.
    1776             :          */
    1777        1216 :         if (ipk1 != ipk2)
    1778           4 :             continue;
    1779             : 
    1780             :         /*
    1781             :          * The clause allows partitionwise join only if it uses the same
    1782             :          * operator family as that specified by the partition key.
    1783             :          */
    1784        1212 :         if (rel1->part_scheme->strategy == PARTITION_STRATEGY_HASH)
    1785             :         {
    1786          32 :             if (!OidIsValid(rinfo->hashjoinoperator) ||
    1787          32 :                 !op_in_opfamily(rinfo->hashjoinoperator,
    1788          32 :                                 part_scheme->partopfamily[ipk1]))
    1789           0 :                 continue;
    1790             :         }
    1791        1180 :         else if (!list_member_oid(rinfo->mergeopfamilies,
    1792        1180 :                                   part_scheme->partopfamily[ipk1]))
    1793           0 :             continue;
    1794             : 
    1795             :         /* Mark the partition key as having an equi-join clause. */
    1796        1212 :         pk_has_clause[ipk1] = true;
    1797             :     }
    1798             : 
    1799             :     /* Check whether every partition key has an equi-join condition. */
    1800        2504 :     for (cnt_pks = 0; cnt_pks < part_scheme->partnatts; cnt_pks++)
    1801             :     {
    1802        1304 :         if (!pk_has_clause[cnt_pks])
    1803          92 :             return false;
    1804             :     }
    1805             : 
    1806        1200 :     return true;
    1807             : }
    1808             : 
    1809             : /*
    1810             :  * match_expr_to_partition_keys
    1811             :  *
    1812             :  * Tries to match an expression to one of the nullable or non-nullable
    1813             :  * partition keys of "rel".  Returns the matched key's ordinal position,
    1814             :  * or -1 if the expression could not be matched to any of the keys.
    1815             :  *
    1816             :  * strict_op must be true if the expression will be compared with the
    1817             :  * partition key using a strict operator.  This allows us to consider
    1818             :  * nullable as well as nonnullable partition keys.
    1819             :  */
    1820             : static int
    1821        3100 : match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
    1822             : {
    1823             :     int         cnt;
    1824             : 
    1825             :     /* This function should be called only for partitioned relations. */
    1826             :     Assert(rel->part_scheme);
    1827             :     Assert(rel->partexprs);
    1828             :     Assert(rel->nullable_partexprs);
    1829             : 
    1830             :     /* Remove any relabel decorations. */
    1831        3264 :     while (IsA(expr, RelabelType))
    1832         164 :         expr = (Expr *) (castNode(RelabelType, expr))->arg;
    1833             : 
    1834        3792 :     for (cnt = 0; cnt < rel->part_scheme->partnatts; cnt++)
    1835             :     {
    1836             :         ListCell   *lc;
    1837             : 
    1838             :         /* We can always match to the non-nullable partition keys. */
    1839        3808 :         foreach(lc, rel->partexprs[cnt])
    1840             :         {
    1841        3068 :             if (equal(lfirst(lc), expr))
    1842        2384 :                 return cnt;
    1843             :         }
    1844             : 
    1845         740 :         if (!strict_op)
    1846           0 :             continue;
    1847             : 
    1848             :         /*
    1849             :          * If it's a strict join operator then a NULL partition key on one
    1850             :          * side will not join to any partition key on the other side, and in
    1851             :          * particular such a row can't join to a row from a different
    1852             :          * partition on the other side.  So, it's okay to search the nullable
    1853             :          * partition keys as well.
    1854             :          */
    1855         940 :         foreach(lc, rel->nullable_partexprs[cnt])
    1856             :         {
    1857         248 :             if (equal(lfirst(lc), expr))
    1858          48 :                 return cnt;
    1859             :         }
    1860             :     }
    1861             : 
    1862         668 :     return -1;
    1863             : }
    1864             : 
    1865             : /*
    1866             :  * set_joinrel_partition_key_exprs
    1867             :  *      Initialize partition key expressions for a partitioned joinrel.
    1868             :  */
    1869             : static void
    1870        1200 : set_joinrel_partition_key_exprs(RelOptInfo *joinrel,
    1871             :                                 RelOptInfo *outer_rel, RelOptInfo *inner_rel,
    1872             :                                 JoinType jointype)
    1873             : {
    1874        1200 :     PartitionScheme part_scheme = joinrel->part_scheme;
    1875        1200 :     int         partnatts = part_scheme->partnatts;
    1876             : 
    1877        1200 :     joinrel->partexprs = (List **) palloc0(sizeof(List *) * partnatts);
    1878        1200 :     joinrel->nullable_partexprs =
    1879        1200 :         (List **) palloc0(sizeof(List *) * partnatts);
    1880             : 
    1881             :     /*
    1882             :      * The joinrel's partition expressions are the same as those of the input
    1883             :      * rels, but we must properly classify them as nullable or not in the
    1884             :      * joinrel's output.  (Also, we add some more partition expressions if
    1885             :      * it's a FULL JOIN.)
    1886             :      */
    1887        2408 :     for (int cnt = 0; cnt < partnatts; cnt++)
    1888             :     {
    1889             :         /* mark these const to enforce that we copy them properly */
    1890        1208 :         const List *outer_expr = outer_rel->partexprs[cnt];
    1891        1208 :         const List *outer_null_expr = outer_rel->nullable_partexprs[cnt];
    1892        1208 :         const List *inner_expr = inner_rel->partexprs[cnt];
    1893        1208 :         const List *inner_null_expr = inner_rel->nullable_partexprs[cnt];
    1894        1208 :         List       *partexpr = NIL;
    1895        1208 :         List       *nullable_partexpr = NIL;
    1896             :         ListCell   *lc;
    1897             : 
    1898        1208 :         switch (jointype)
    1899             :         {
    1900             :                 /*
    1901             :                  * A join relation resulting from an INNER join may be
    1902             :                  * regarded as partitioned by either of the inner and outer
    1903             :                  * relation keys.  For example, A INNER JOIN B ON A.a = B.b
    1904             :                  * can be regarded as partitioned on either A.a or B.b.  So we
    1905             :                  * add both keys to the joinrel's partexpr lists.  However,
    1906             :                  * anything that was already nullable still has to be treated
    1907             :                  * as nullable.
    1908             :                  */
    1909         464 :             case JOIN_INNER:
    1910         464 :                 partexpr = list_concat_copy(outer_expr, inner_expr);
    1911         464 :                 nullable_partexpr = list_concat_copy(outer_null_expr,
    1912             :                                                      inner_null_expr);
    1913         464 :                 break;
    1914             : 
    1915             :                 /*
    1916             :                  * A join relation resulting from a SEMI or ANTI join may be
    1917             :                  * regarded as partitioned by the outer relation keys.  The
    1918             :                  * inner relation's keys are no longer interesting; since they
    1919             :                  * aren't visible in the join output, nothing could join to
    1920             :                  * them.
    1921             :                  */
    1922         176 :             case JOIN_SEMI:
    1923             :             case JOIN_ANTI:
    1924         176 :                 partexpr = list_copy(outer_expr);
    1925         176 :                 nullable_partexpr = list_copy(outer_null_expr);
    1926         176 :                 break;
    1927             : 
    1928             :                 /*
    1929             :                  * A join relation resulting from a LEFT OUTER JOIN likewise
    1930             :                  * may be regarded as partitioned on the (non-nullable) outer
    1931             :                  * relation keys.  The inner (nullable) relation keys are okay
    1932             :                  * as partition keys for further joins as long as they involve
    1933             :                  * strict join operators.
    1934             :                  */
    1935         376 :             case JOIN_LEFT:
    1936         376 :                 partexpr = list_copy(outer_expr);
    1937         376 :                 nullable_partexpr = list_concat_copy(inner_expr,
    1938             :                                                      outer_null_expr);
    1939         376 :                 nullable_partexpr = list_concat(nullable_partexpr,
    1940             :                                                 inner_null_expr);
    1941         376 :                 break;
    1942             : 
    1943             :                 /*
    1944             :                  * For FULL OUTER JOINs, both relations are nullable, so the
    1945             :                  * resulting join relation may be regarded as partitioned on
    1946             :                  * either of inner and outer relation keys, but only for joins
    1947             :                  * that involve strict join operators.
    1948             :                  */
    1949         192 :             case JOIN_FULL:
    1950         192 :                 nullable_partexpr = list_concat_copy(outer_expr,
    1951             :                                                      inner_expr);
    1952         192 :                 nullable_partexpr = list_concat(nullable_partexpr,
    1953             :                                                 outer_null_expr);
    1954         192 :                 nullable_partexpr = list_concat(nullable_partexpr,
    1955             :                                                 inner_null_expr);
    1956             : 
    1957             :                 /*
    1958             :                  * Also add CoalesceExprs corresponding to each possible
    1959             :                  * full-join output variable (that is, left side coalesced to
    1960             :                  * right side), so that we can match equijoin expressions
    1961             :                  * using those variables.  We really only need these for
    1962             :                  * columns merged by JOIN USING, and only with the pairs of
    1963             :                  * input items that correspond to the data structures that
    1964             :                  * parse analysis would build for such variables.  But it's
    1965             :                  * hard to tell which those are, so just make all the pairs.
    1966             :                  * Extra items in the nullable_partexprs list won't cause big
    1967             :                  * problems.  (It's possible that such items will get matched
    1968             :                  * to user-written COALESCEs, but it should still be valid to
    1969             :                  * partition on those, since they're going to be either the
    1970             :                  * partition column or NULL; it's the same argument as for
    1971             :                  * partitionwise nesting of any outer join.)  We assume no
    1972             :                  * type coercions are needed to make the coalesce expressions,
    1973             :                  * since columns of different types won't have gotten
    1974             :                  * classified as the same PartitionScheme.
    1975             :                  */
    1976         488 :                 foreach(lc, list_concat_copy(outer_expr, outer_null_expr))
    1977             :                 {
    1978         296 :                     Node       *larg = (Node *) lfirst(lc);
    1979             :                     ListCell   *lc2;
    1980             : 
    1981         592 :                     foreach(lc2, list_concat_copy(inner_expr, inner_null_expr))
    1982             :                     {
    1983         296 :                         Node       *rarg = (Node *) lfirst(lc2);
    1984         296 :                         CoalesceExpr *c = makeNode(CoalesceExpr);
    1985             : 
    1986         296 :                         c->coalescetype = exprType(larg);
    1987         296 :                         c->coalescecollid = exprCollation(larg);
    1988         296 :                         c->args = list_make2(larg, rarg);
    1989         296 :                         c->location = -1;
    1990         296 :                         nullable_partexpr = lappend(nullable_partexpr, c);
    1991             :                     }
    1992             :                 }
    1993         192 :                 break;
    1994             : 
    1995           0 :             default:
    1996           0 :                 elog(ERROR, "unrecognized join type: %d", (int) jointype);
    1997             :         }
    1998             : 
    1999        1208 :         joinrel->partexprs[cnt] = partexpr;
    2000        1208 :         joinrel->nullable_partexprs[cnt] = nullable_partexpr;
    2001             :     }
    2002        1200 : }
    2003             : 
    2004             : /*
    2005             :  * build_child_join_reltarget
    2006             :  *    Set up a child-join relation's reltarget from a parent-join relation.
    2007             :  */
    2008             : static void
    2009        2844 : build_child_join_reltarget(PlannerInfo *root,
    2010             :                            RelOptInfo *parentrel,
    2011             :                            RelOptInfo *childrel,
    2012             :                            int nappinfos,
    2013             :                            AppendRelInfo **appinfos)
    2014             : {
    2015             :     /* Build the targetlist */
    2016        5688 :     childrel->reltarget->exprs = (List *)
    2017        2844 :         adjust_appendrel_attrs(root,
    2018        2844 :                                (Node *) parentrel->reltarget->exprs,
    2019             :                                nappinfos, appinfos);
    2020             : 
    2021             :     /* Set the cost and width fields */
    2022        2844 :     childrel->reltarget->cost.startup = parentrel->reltarget->cost.startup;
    2023        2844 :     childrel->reltarget->cost.per_tuple = parentrel->reltarget->cost.per_tuple;
    2024        2844 :     childrel->reltarget->width = parentrel->reltarget->width;
    2025        2844 : }

Generated by: LCOV version 1.13