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

Generated by: LCOV version 1.13