granicus.if.org Git - postgresql/blob - src/backend/optimizer/prep/prepjointree.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * prepjointree.c
   4  *        Planner preprocessing for subqueries and join tree manipulation.
   5  *
   6  * NOTE: the intended sequence for invoking these operations is
   7  *              pull_up_sublinks
   8  *              inline_set_returning_functions
   9  *              pull_up_subqueries
  10  *              flatten_simple_union_all
  11  *              do expression preprocessing (including flattening JOIN alias vars)
  12  *              reduce_outer_joins
  13  *
  14  *
  15  * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
  16  * Portions Copyright (c) 1994, Regents of the University of California
  17  *
  18  *
  19  * IDENTIFICATION
  20  *        src/backend/optimizer/prep/prepjointree.c
  21  *
  22  *-------------------------------------------------------------------------
  23  */
  24 #include "postgres.h"
  25
  26 #include "catalog/pg_type.h"
  27 #include "nodes/makefuncs.h"
  28 #include "nodes/nodeFuncs.h"
  29 #include "optimizer/clauses.h"
  30 #include "optimizer/placeholder.h"
  31 #include "optimizer/prep.h"
  32 #include "optimizer/subselect.h"
  33 #include "optimizer/tlist.h"
  34 #include "parser/parse_relation.h"
  35 #include "parser/parsetree.h"
  36 #include "rewrite/rewriteManip.h"
  37
  38
  39 typedef struct pullup_replace_vars_context
  40 {
  41         PlannerInfo *root;
  42         List       *targetlist;         /* tlist of subquery being pulled up */
  43         RangeTblEntry *target_rte;      /* RTE of subquery */
  44         Relids          relids;                 /* relids within subquery, as numbered after
  45                                                                  * pullup (set only if target_rte->lateral) */
  46         bool       *outer_hasSubLinks;          /* -> outer query's hasSubLinks */
  47         int                     varno;                  /* varno of subquery */
  48         bool            need_phvs;              /* do we need PlaceHolderVars? */
  49         bool            wrap_non_vars;  /* do we need 'em on *all* non-Vars? */
  50         Node      **rv_cache;           /* cache for results with PHVs */
  51 } pullup_replace_vars_context;
  52
  53 typedef struct reduce_outer_joins_state
  54 {
  55         Relids          relids;                 /* base relids within this subtree */
  56         bool            contains_outer; /* does subtree contain outer join(s)? */
  57         List       *sub_states;         /* List of states for subtree components */
  58 } reduce_outer_joins_state;
  59
  60 static Node *pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
  61                                                                   Relids *relids);
  62 static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
  63                                                           Node **jtlink1, Relids available_rels1,
  64                                                           Node **jtlink2, Relids available_rels2);
  65 static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
  66                                                    JoinExpr *lowest_outer_join,
  67                                                    JoinExpr *lowest_nulling_outer_join,
  68                                                    AppendRelInfo *containing_appendrel,
  69                                                    bool deletion_ok);
  70 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
  71                                                 RangeTblEntry *rte,
  72                                                 JoinExpr *lowest_outer_join,
  73                                                 JoinExpr *lowest_nulling_outer_join,
  74                                                 AppendRelInfo *containing_appendrel,
  75                                                 bool deletion_ok);
  76 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
  77                                                  RangeTblEntry *rte);
  78 static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,
  79                                                    int parentRTindex, Query *setOpQuery,
  80                                                    int childRToffset);
  81 static void make_setop_translation_list(Query *query, Index newvarno,
  82                                                         List **translated_vars);
  83 static bool is_simple_subquery(Query *subquery, RangeTblEntry *rte,
  84                                    JoinExpr *lowest_outer_join,
  85                                    bool deletion_ok);
  86 static Node *pull_up_simple_values(PlannerInfo *root, Node *jtnode,
  87                                           RangeTblEntry *rte);
  88 static bool is_simple_values(PlannerInfo *root, RangeTblEntry *rte,
  89                                  bool deletion_ok);
  90 static bool is_simple_union_all(Query *subquery);
  91 static bool is_simple_union_all_recurse(Node *setOp, Query *setOpQuery,
  92                                                         List *colTypes);
  93 static bool is_safe_append_member(Query *subquery);
  94 static bool jointree_contains_lateral_outer_refs(Node *jtnode, bool restricted,
  95                                                                          Relids safe_upper_varnos);
  96 static void replace_vars_in_jointree(Node *jtnode,
  97                                                  pullup_replace_vars_context *context,
  98                                                  JoinExpr *lowest_nulling_outer_join);
  99 static Node *pullup_replace_vars(Node *expr,
 100                                         pullup_replace_vars_context *context);
 101 static Node *pullup_replace_vars_callback(Var *var,
 102                                                          replace_rte_variables_context *context);
 103 static Query *pullup_replace_vars_subquery(Query *query,
 104                                                          pullup_replace_vars_context *context);
 105 static Node *pull_up_subqueries_cleanup(Node *jtnode);
 106 static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
 107 static void reduce_outer_joins_pass2(Node *jtnode,
 108                                                  reduce_outer_joins_state *state,
 109                                                  PlannerInfo *root,
 110                                                  Relids nonnullable_rels,
 111                                                  List *nonnullable_vars,
 112                                                  List *forced_null_vars);
 113 static void substitute_multiple_relids(Node *node,
 114                                                    int varno, Relids subrelids);
 115 static void fix_append_rel_relids(List *append_rel_list, int varno,
 116                                           Relids subrelids);
 117 static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
 118
 119
 120 /*
 121  * pull_up_sublinks
 122  *              Attempt to pull up ANY and EXISTS SubLinks to be treated as
 123  *              semijoins or anti-semijoins.
 124  *
 125  * A clause "foo op ANY (sub-SELECT)" can be processed by pulling the
 126  * sub-SELECT up to become a rangetable entry and treating the implied
 127  * comparisons as quals of a semijoin.  However, this optimization *only*
 128  * works at the top level of WHERE or a JOIN/ON clause, because we cannot
 129  * distinguish whether the ANY ought to return FALSE or NULL in cases
 130  * involving NULL inputs.  Also, in an outer join's ON clause we can only
 131  * do this if the sublink is degenerate (ie, references only the nullable
 132  * side of the join).  In that case it is legal to push the semijoin
 133  * down into the nullable side of the join.  If the sublink references any
 134  * nonnullable-side variables then it would have to be evaluated as part
 135  * of the outer join, which makes things way too complicated.
 136  *
 137  * Under similar conditions, EXISTS and NOT EXISTS clauses can be handled
 138  * by pulling up the sub-SELECT and creating a semijoin or anti-semijoin.
 139  *
 140  * This routine searches for such clauses and does the necessary parsetree
 141  * transformations if any are found.
 142  *
 143  * This routine has to run before preprocess_expression(), so the quals
 144  * clauses are not yet reduced to implicit-AND format, and are not guaranteed
 145  * to be AND/OR-flat either.  That means we need to recursively search through
 146  * explicit AND clauses.  We stop as soon as we hit a non-AND item.
 147  */
 148 void
 149 pull_up_sublinks(PlannerInfo *root)
 150 {
 151         Node       *jtnode;
 152         Relids          relids;
 153
 154         /* Begin recursion through the jointree */
 155         jtnode = pull_up_sublinks_jointree_recurse(root,
 156                                                                                            (Node *) root->parse->jointree,
 157                                                                                            &relids);
 158
 159         /*
 160          * root->parse->jointree must always be a FromExpr, so insert a dummy one
 161          * if we got a bare RangeTblRef or JoinExpr out of the recursion.
 162          */
 163         if (IsA(jtnode, FromExpr))
 164                 root->parse->jointree = (FromExpr *) jtnode;
 165         else
 166                 root->parse->jointree = makeFromExpr(list_make1(jtnode), NULL);
 167 }
 168
 169 /*
 170  * Recurse through jointree nodes for pull_up_sublinks()
 171  *
 172  * In addition to returning the possibly-modified jointree node, we return
 173  * a relids set of the contained rels into *relids.
 174  */
 175 static Node *
 176 pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
 177                                                                   Relids *relids)
 178 {
 179         if (jtnode == NULL)
 180         {
 181                 *relids = NULL;
 182         }
 183         else if (IsA(jtnode, RangeTblRef))
 184         {
 185                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 186
 187                 *relids = bms_make_singleton(varno);
 188                 /* jtnode is returned unmodified */
 189         }
 190         else if (IsA(jtnode, FromExpr))
 191         {
 192                 FromExpr   *f = (FromExpr *) jtnode;
 193                 List       *newfromlist = NIL;
 194                 Relids          frelids = NULL;
 195                 FromExpr   *newf;
 196                 Node       *jtlink;
 197                 ListCell   *l;
 198
 199                 /* First, recurse to process children and collect their relids */
 200                 foreach(l, f->fromlist)
 201                 {
 202                         Node       *newchild;
 203                         Relids          childrelids;
 204
 205                         newchild = pull_up_sublinks_jointree_recurse(root,
 206                                                                                                                  lfirst(l),
 207                                                                                                                  &childrelids);
 208                         newfromlist = lappend(newfromlist, newchild);
 209                         frelids = bms_join(frelids, childrelids);
 210                 }
 211                 /* Build the replacement FromExpr; no quals yet */
 212                 newf = makeFromExpr(newfromlist, NULL);
 213                 /* Set up a link representing the rebuilt jointree */
 214                 jtlink = (Node *) newf;
 215                 /* Now process qual --- all children are available for use */
 216                 newf->quals = pull_up_sublinks_qual_recurse(root, f->quals,
 217                                                                                                         &jtlink, frelids,
 218                                                                                                         NULL, NULL);
 219
 220                 /*
 221                  * Note that the result will be either newf, or a stack of JoinExprs
 222                  * with newf at the base.  We rely on subsequent optimization steps to
 223                  * flatten this and rearrange the joins as needed.
 224                  *
 225                  * Although we could include the pulled-up subqueries in the returned
 226                  * relids, there's no need since upper quals couldn't refer to their
 227                  * outputs anyway.
 228                  */
 229                 *relids = frelids;
 230                 jtnode = jtlink;
 231         }
 232         else if (IsA(jtnode, JoinExpr))
 233         {
 234                 JoinExpr   *j;
 235                 Relids          leftrelids;
 236                 Relids          rightrelids;
 237                 Node       *jtlink;
 238
 239                 /*
 240                  * Make a modifiable copy of join node, but don't bother copying its
 241                  * subnodes (yet).
 242                  */
 243                 j = (JoinExpr *) palloc(sizeof(JoinExpr));
 244                 memcpy(j, jtnode, sizeof(JoinExpr));
 245                 jtlink = (Node *) j;
 246
 247                 /* Recurse to process children and collect their relids */
 248                 j->larg = pull_up_sublinks_jointree_recurse(root, j->larg,
 249                                                                                                         &leftrelids);
 250                 j->rarg = pull_up_sublinks_jointree_recurse(root, j->rarg,
 251                                                                                                         &rightrelids);
 252
 253                 /*
 254                  * Now process qual, showing appropriate child relids as available,
 255                  * and attach any pulled-up jointree items at the right place. In the
 256                  * inner-join case we put new JoinExprs above the existing one (much
 257                  * as for a FromExpr-style join).  In outer-join cases the new
 258                  * JoinExprs must go into the nullable side of the outer join. The
 259                  * point of the available_rels machinations is to ensure that we only
 260                  * pull up quals for which that's okay.
 261                  *
 262                  * We don't expect to see any pre-existing JOIN_SEMI or JOIN_ANTI
 263                  * nodes here.
 264                  */
 265                 switch (j->jointype)
 266                 {
 267                         case JOIN_INNER:
 268                                 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
 269                                                                                                                  &jtlink,
 270                                                                                                                  bms_union(leftrelids,
 271                                                                                                                                 rightrelids),
 272                                                                                                                  NULL, NULL);
 273                                 break;
 274                         case JOIN_LEFT:
 275                                 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
 276                                                                                                                  &j->rarg,
 277                                                                                                                  rightrelids,
 278                                                                                                                  NULL, NULL);
 279                                 break;
 280                         case JOIN_FULL:
 281                                 /* can't do anything with full-join quals */
 282                                 break;
 283                         case JOIN_RIGHT:
 284                                 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
 285                                                                                                                  &j->larg,
 286                                                                                                                  leftrelids,
 287                                                                                                                  NULL, NULL);
 288                                 break;
 289                         default:
 290                                 elog(ERROR, "unrecognized join type: %d",
 291                                          (int) j->jointype);
 292                                 break;
 293                 }
 294
 295                 /*
 296                  * Although we could include the pulled-up subqueries in the returned
 297                  * relids, there's no need since upper quals couldn't refer to their
 298                  * outputs anyway.  But we *do* need to include the join's own rtindex
 299                  * because we haven't yet collapsed join alias variables, so upper
 300                  * levels would mistakenly think they couldn't use references to this
 301                  * join.
 302                  */
 303                 *relids = bms_join(leftrelids, rightrelids);
 304                 if (j->rtindex)
 305                         *relids = bms_add_member(*relids, j->rtindex);
 306                 jtnode = jtlink;
 307         }
 308         else
 309                 elog(ERROR, "unrecognized node type: %d",
 310                          (int) nodeTag(jtnode));
 311         return jtnode;
 312 }
 313
 314 /*
 315  * Recurse through top-level qual nodes for pull_up_sublinks()
 316  *
 317  * jtlink1 points to the link in the jointree where any new JoinExprs should
 318  * be inserted if they reference available_rels1 (i.e., available_rels1
 319  * denotes the relations present underneath jtlink1).  Optionally, jtlink2 can
 320  * point to a second link where new JoinExprs should be inserted if they
 321  * reference available_rels2 (pass NULL for both those arguments if not used).
 322  * Note that SubLinks referencing both sets of variables cannot be optimized.
 323  * If we find multiple pull-up-able SubLinks, they'll get stacked onto jtlink1
 324  * and/or jtlink2 in the order we encounter them.  We rely on subsequent
 325  * optimization to rearrange the stack if appropriate.
 326  *
 327  * Returns the replacement qual node, or NULL if the qual should be removed.
 328  */
 329 static Node *
 330 pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 331                                                           Node **jtlink1, Relids available_rels1,
 332                                                           Node **jtlink2, Relids available_rels2)
 333 {
 334         if (node == NULL)
 335                 return NULL;
 336         if (IsA(node, SubLink))
 337         {
 338                 SubLink    *sublink = (SubLink *) node;
 339                 JoinExpr   *j;
 340                 Relids          child_rels;
 341
 342                 /* Is it a convertible ANY or EXISTS clause? */
 343                 if (sublink->subLinkType == ANY_SUBLINK)
 344                 {
 345                         if ((j = convert_ANY_sublink_to_join(root, sublink,
 346                                                                                                  available_rels1)) != NULL)
 347                         {
 348                                 /* Yes; insert the new join node into the join tree */
 349                                 j->larg = *jtlink1;
 350                                 *jtlink1 = (Node *) j;
 351                                 /* Recursively process pulled-up jointree nodes */
 352                                 j->rarg = pull_up_sublinks_jointree_recurse(root,
 353                                                                                                                         j->rarg,
 354                                                                                                                         &child_rels);
 355
 356                                 /*
 357                                  * Now recursively process the pulled-up quals.  Any inserted
 358                                  * joins can get stacked onto either j->larg or j->rarg,
 359                                  * depending on which rels they reference.
 360                                  */
 361                                 j->quals = pull_up_sublinks_qual_recurse(root,
 362                                                                                                                  j->quals,
 363                                                                                                                  &j->larg,
 364                                                                                                                  available_rels1,
 365                                                                                                                  &j->rarg,
 366                                                                                                                  child_rels);
 367                                 /* Return NULL representing constant TRUE */
 368                                 return NULL;
 369                         }
 370                         if (available_rels2 != NULL &&
 371                                 (j = convert_ANY_sublink_to_join(root, sublink,
 372                                                                                                  available_rels2)) != NULL)
 373                         {
 374                                 /* Yes; insert the new join node into the join tree */
 375                                 j->larg = *jtlink2;
 376                                 *jtlink2 = (Node *) j;
 377                                 /* Recursively process pulled-up jointree nodes */
 378                                 j->rarg = pull_up_sublinks_jointree_recurse(root,
 379                                                                                                                         j->rarg,
 380                                                                                                                         &child_rels);
 381
 382                                 /*
 383                                  * Now recursively process the pulled-up quals.  Any inserted
 384                                  * joins can get stacked onto either j->larg or j->rarg,
 385                                  * depending on which rels they reference.
 386                                  */
 387                                 j->quals = pull_up_sublinks_qual_recurse(root,
 388                                                                                                                  j->quals,
 389                                                                                                                  &j->larg,
 390                                                                                                                  available_rels2,
 391                                                                                                                  &j->rarg,
 392                                                                                                                  child_rels);
 393                                 /* Return NULL representing constant TRUE */
 394                                 return NULL;
 395                         }
 396                 }
 397                 else if (sublink->subLinkType == EXISTS_SUBLINK)
 398                 {
 399                         if ((j = convert_EXISTS_sublink_to_join(root, sublink, false,
 400                                                                                                         available_rels1)) != NULL)
 401                         {
 402                                 /* Yes; insert the new join node into the join tree */
 403                                 j->larg = *jtlink1;
 404                                 *jtlink1 = (Node *) j;
 405                                 /* Recursively process pulled-up jointree nodes */
 406                                 j->rarg = pull_up_sublinks_jointree_recurse(root,
 407                                                                                                                         j->rarg,
 408                                                                                                                         &child_rels);
 409
 410                                 /*
 411                                  * Now recursively process the pulled-up quals.  Any inserted
 412                                  * joins can get stacked onto either j->larg or j->rarg,
 413                                  * depending on which rels they reference.
 414                                  */
 415                                 j->quals = pull_up_sublinks_qual_recurse(root,
 416                                                                                                                  j->quals,
 417                                                                                                                  &j->larg,
 418                                                                                                                  available_rels1,
 419                                                                                                                  &j->rarg,
 420                                                                                                                  child_rels);
 421                                 /* Return NULL representing constant TRUE */
 422                                 return NULL;
 423                         }
 424                         if (available_rels2 != NULL &&
 425                                 (j = convert_EXISTS_sublink_to_join(root, sublink, false,
 426                                                                                                         available_rels2)) != NULL)
 427                         {
 428                                 /* Yes; insert the new join node into the join tree */
 429                                 j->larg = *jtlink2;
 430                                 *jtlink2 = (Node *) j;
 431                                 /* Recursively process pulled-up jointree nodes */
 432                                 j->rarg = pull_up_sublinks_jointree_recurse(root,
 433                                                                                                                         j->rarg,
 434                                                                                                                         &child_rels);
 435
 436                                 /*
 437                                  * Now recursively process the pulled-up quals.  Any inserted
 438                                  * joins can get stacked onto either j->larg or j->rarg,
 439                                  * depending on which rels they reference.
 440                                  */
 441                                 j->quals = pull_up_sublinks_qual_recurse(root,
 442                                                                                                                  j->quals,
 443                                                                                                                  &j->larg,
 444                                                                                                                  available_rels2,
 445                                                                                                                  &j->rarg,
 446                                                                                                                  child_rels);
 447                                 /* Return NULL representing constant TRUE */
 448                                 return NULL;
 449                         }
 450                 }
 451                 /* Else return it unmodified */
 452                 return node;
 453         }
 454         if (not_clause(node))
 455         {
 456                 /* If the immediate argument of NOT is EXISTS, try to convert */
 457                 SubLink    *sublink = (SubLink *) get_notclausearg((Expr *) node);
 458                 JoinExpr   *j;
 459                 Relids          child_rels;
 460
 461                 if (sublink && IsA(sublink, SubLink))
 462                 {
 463                         if (sublink->subLinkType == EXISTS_SUBLINK)
 464                         {
 465                                 if ((j = convert_EXISTS_sublink_to_join(root, sublink, true,
 466                                                                                                    available_rels1)) != NULL)
 467                                 {
 468                                         /* Yes; insert the new join node into the join tree */
 469                                         j->larg = *jtlink1;
 470                                         *jtlink1 = (Node *) j;
 471                                         /* Recursively process pulled-up jointree nodes */
 472                                         j->rarg = pull_up_sublinks_jointree_recurse(root,
 473                                                                                                                                 j->rarg,
 474                                                                                                                                 &child_rels);
 475
 476                                         /*
 477                                          * Now recursively process the pulled-up quals.  Because
 478                                          * we are underneath a NOT, we can't pull up sublinks that
 479                                          * reference the left-hand stuff, but it's still okay to
 480                                          * pull up sublinks referencing j->rarg.
 481                                          */
 482                                         j->quals = pull_up_sublinks_qual_recurse(root,
 483                                                                                                                          j->quals,
 484                                                                                                                          &j->rarg,
 485                                                                                                                          child_rels,
 486                                                                                                                          NULL, NULL);
 487                                         /* Return NULL representing constant TRUE */
 488                                         return NULL;
 489                                 }
 490                                 if (available_rels2 != NULL &&
 491                                         (j = convert_EXISTS_sublink_to_join(root, sublink, true,
 492                                                                                                    available_rels2)) != NULL)
 493                                 {
 494                                         /* Yes; insert the new join node into the join tree */
 495                                         j->larg = *jtlink2;
 496                                         *jtlink2 = (Node *) j;
 497                                         /* Recursively process pulled-up jointree nodes */
 498                                         j->rarg = pull_up_sublinks_jointree_recurse(root,
 499                                                                                                                                 j->rarg,
 500                                                                                                                                 &child_rels);
 501
 502                                         /*
 503                                          * Now recursively process the pulled-up quals.  Because
 504                                          * we are underneath a NOT, we can't pull up sublinks that
 505                                          * reference the left-hand stuff, but it's still okay to
 506                                          * pull up sublinks referencing j->rarg.
 507                                          */
 508                                         j->quals = pull_up_sublinks_qual_recurse(root,
 509                                                                                                                          j->quals,
 510                                                                                                                          &j->rarg,
 511                                                                                                                          child_rels,
 512                                                                                                                          NULL, NULL);
 513                                         /* Return NULL representing constant TRUE */
 514                                         return NULL;
 515                                 }
 516                         }
 517                 }
 518                 /* Else return it unmodified */
 519                 return node;
 520         }
 521         if (and_clause(node))
 522         {
 523                 /* Recurse into AND clause */
 524                 List       *newclauses = NIL;
 525                 ListCell   *l;
 526
 527                 foreach(l, ((BoolExpr *) node)->args)
 528                 {
 529                         Node       *oldclause = (Node *) lfirst(l);
 530                         Node       *newclause;
 531
 532                         newclause = pull_up_sublinks_qual_recurse(root,
 533                                                                                                           oldclause,
 534                                                                                                           jtlink1,
 535                                                                                                           available_rels1,
 536                                                                                                           jtlink2,
 537                                                                                                           available_rels2);
 538                         if (newclause)
 539                                 newclauses = lappend(newclauses, newclause);
 540                 }
 541                 /* We might have got back fewer clauses than we started with */
 542                 if (newclauses == NIL)
 543                         return NULL;
 544                 else if (list_length(newclauses) == 1)
 545                         return (Node *) linitial(newclauses);
 546                 else
 547                         return (Node *) make_andclause(newclauses);
 548         }
 549         /* Stop if not an AND */
 550         return node;
 551 }
 552
 553 /*
 554  * inline_set_returning_functions
 555  *              Attempt to "inline" set-returning functions in the FROM clause.
 556  *
 557  * If an RTE_FUNCTION rtable entry invokes a set-returning function that
 558  * contains just a simple SELECT, we can convert the rtable entry to an
 559  * RTE_SUBQUERY entry exposing the SELECT directly.  This is especially
 560  * useful if the subquery can then be "pulled up" for further optimization,
 561  * but we do it even if not, to reduce executor overhead.
 562  *
 563  * This has to be done before we have started to do any optimization of
 564  * subqueries, else any such steps wouldn't get applied to subqueries
 565  * obtained via inlining.  However, we do it after pull_up_sublinks
 566  * so that we can inline any functions used in SubLink subselects.
 567  *
 568  * Like most of the planner, this feels free to scribble on its input data
 569  * structure.
 570  */
 571 void
 572 inline_set_returning_functions(PlannerInfo *root)
 573 {
 574         ListCell   *rt;
 575
 576         foreach(rt, root->parse->rtable)
 577         {
 578                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
 579
 580                 if (rte->rtekind == RTE_FUNCTION)
 581                 {
 582                         Query      *funcquery;
 583
 584                         /* Check safety of expansion, and expand if possible */
 585                         funcquery = inline_set_returning_function(root, rte);
 586                         if (funcquery)
 587                         {
 588                                 /* Successful expansion, replace the rtable entry */
 589                                 rte->rtekind = RTE_SUBQUERY;
 590                                 rte->subquery = funcquery;
 591                                 rte->functions = NIL;
 592                         }
 593                 }
 594         }
 595 }
 596
 597 /*
 598  * pull_up_subqueries
 599  *              Look for subqueries in the rangetable that can be pulled up into
 600  *              the parent query.  If the subquery has no special features like
 601  *              grouping/aggregation then we can merge it into the parent's jointree.
 602  *              Also, subqueries that are simple UNION ALL structures can be
 603  *              converted into "append relations".
 604  */
 605 void
 606 pull_up_subqueries(PlannerInfo *root)
 607 {
 608         /* Top level of jointree must always be a FromExpr */
 609         Assert(IsA(root->parse->jointree, FromExpr));
 610         /* Reset flag saying we need a deletion cleanup pass */
 611         root->hasDeletedRTEs = false;
 612         /* Recursion starts with no containing join nor appendrel */
 613         root->parse->jointree = (FromExpr *)
 614                 pull_up_subqueries_recurse(root, (Node *) root->parse->jointree,
 615                                                                    NULL, NULL, NULL, false);
 616         /* Apply cleanup phase if necessary */
 617         if (root->hasDeletedRTEs)
 618                 root->parse->jointree = (FromExpr *)
 619                         pull_up_subqueries_cleanup((Node *) root->parse->jointree);
 620         Assert(IsA(root->parse->jointree, FromExpr));
 621 }
 622
 623 /*
 624  * pull_up_subqueries_recurse
 625  *              Recursive guts of pull_up_subqueries.
 626  *
 627  * This recursively processes the jointree and returns a modified jointree.
 628  * Or, if it's valid to drop the current node from the jointree completely,
 629  * it returns NULL.
 630  *
 631  * If this jointree node is within either side of an outer join, then
 632  * lowest_outer_join references the lowest such JoinExpr node; otherwise
 633  * it is NULL.  We use this to constrain the effects of LATERAL subqueries.
 634  *
 635  * If this jointree node is within the nullable side of an outer join, then
 636  * lowest_nulling_outer_join references the lowest such JoinExpr node;
 637  * otherwise it is NULL.  This forces use of the PlaceHolderVar mechanism for
 638  * references to non-nullable targetlist items, but only for references above
 639  * that join.
 640  *
 641  * If we are looking at a member subquery of an append relation,
 642  * containing_appendrel describes that relation; else it is NULL.
 643  * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
 644  * items, and puts some additional restrictions on what can be pulled up.
 645  *
 646  * deletion_ok is TRUE if the caller can cope with us returning NULL for a
 647  * deletable leaf node (for example, a VALUES RTE that could be pulled up).
 648  * If it's FALSE, we'll avoid pullup in such cases.
 649  *
 650  * A tricky aspect of this code is that if we pull up a subquery we have
 651  * to replace Vars that reference the subquery's outputs throughout the
 652  * parent query, including quals attached to jointree nodes above the one
 653  * we are currently processing!  We handle this by being careful not to
 654  * change the jointree structure while recursing: no nodes other than leaf
 655  * RangeTblRef entries and entirely-empty FromExprs will be replaced or
 656  * deleted.  Also, we can't turn pullup_replace_vars loose on the whole
 657  * jointree, because it'll return a mutated copy of the tree; we have to
 658  * invoke it just on the quals, instead.  This behavior is what makes it
 659  * reasonable to pass lowest_outer_join and lowest_nulling_outer_join as
 660  * pointers rather than some more-indirect way of identifying the lowest
 661  * OJs.  Likewise, we don't replace append_rel_list members but only their
 662  * substructure, so the containing_appendrel reference is safe to use.
 663  *
 664  * Because of the rule that no jointree nodes with substructure can be
 665  * replaced, we cannot fully handle the case of deleting nodes from the tree:
 666  * when we delete one child of a JoinExpr, we need to replace the JoinExpr
 667  * with a FromExpr, and that can't happen here.  Instead, we set the
 668  * root->hasDeletedRTEs flag, which tells pull_up_subqueries() that an
 669  * additional pass over the tree is needed to clean up.
 670  */
 671 static Node *
 672 pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,
 673                                                    JoinExpr *lowest_outer_join,
 674                                                    JoinExpr *lowest_nulling_outer_join,
 675                                                    AppendRelInfo *containing_appendrel,
 676                                                    bool deletion_ok)
 677 {
 678         Assert(jtnode != NULL);
 679         if (IsA(jtnode, RangeTblRef))
 680         {
 681                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 682                 RangeTblEntry *rte = rt_fetch(varno, root->parse->rtable);
 683
 684                 /*
 685                  * Is this a subquery RTE, and if so, is the subquery simple enough to
 686                  * pull up?
 687                  *
 688                  * If we are looking at an append-relation member, we can't pull it up
 689                  * unless is_safe_append_member says so.
 690                  */
 691                 if (rte->rtekind == RTE_SUBQUERY &&
 692                         is_simple_subquery(rte->subquery, rte,
 693                                                            lowest_outer_join, deletion_ok) &&
 694                         (containing_appendrel == NULL ||
 695                          is_safe_append_member(rte->subquery)))
 696                         return pull_up_simple_subquery(root, jtnode, rte,
 697                                                                                    lowest_outer_join,
 698                                                                                    lowest_nulling_outer_join,
 699                                                                                    containing_appendrel,
 700                                                                                    deletion_ok);
 701
 702                 /*
 703                  * Alternatively, is it a simple UNION ALL subquery?  If so, flatten
 704                  * into an "append relation".
 705                  *
 706                  * It's safe to do this regardless of whether this query is itself an
 707                  * appendrel member.  (If you're thinking we should try to flatten the
 708                  * two levels of appendrel together, you're right; but we handle that
 709                  * in set_append_rel_pathlist, not here.)
 710                  */
 711                 if (rte->rtekind == RTE_SUBQUERY &&
 712                         is_simple_union_all(rte->subquery))
 713                         return pull_up_simple_union_all(root, jtnode, rte);
 714
 715                 /*
 716                  * Or perhaps it's a simple VALUES RTE?
 717                  *
 718                  * We don't allow VALUES pullup below an outer join nor into an
 719                  * appendrel (such cases are impossible anyway at the moment).
 720                  */
 721                 if (rte->rtekind == RTE_VALUES &&
 722                         lowest_outer_join == NULL &&
 723                         containing_appendrel == NULL &&
 724                         is_simple_values(root, rte, deletion_ok))
 725                         return pull_up_simple_values(root, jtnode, rte);
 726
 727                 /* Otherwise, do nothing at this node. */
 728         }
 729         else if (IsA(jtnode, FromExpr))
 730         {
 731                 FromExpr   *f = (FromExpr *) jtnode;
 732                 bool            have_undeleted_child = false;
 733                 ListCell   *l;
 734
 735                 Assert(containing_appendrel == NULL);
 736
 737                 /*
 738                  * If the FromExpr has quals, it's not deletable even if its parent
 739                  * would allow deletion.
 740                  */
 741                 if (f->quals)
 742                         deletion_ok = false;
 743
 744                 foreach(l, f->fromlist)
 745                 {
 746                         /*
 747                          * In a non-deletable FromExpr, we can allow deletion of child
 748                          * nodes so long as at least one child remains; so it's okay
 749                          * either if any previous child survives, or if there's more to
 750                          * come.  If all children are deletable in themselves, we'll force
 751                          * the last one to remain unflattened.
 752                          *
 753                          * As a separate matter, we can allow deletion of all children of
 754                          * the top-level FromExpr in a query, since that's a special case
 755                          * anyway.
 756                          */
 757                         bool            sub_deletion_ok = (deletion_ok ||
 758                                                                                    have_undeleted_child ||
 759                                                                                    lnext(l) != NULL ||
 760                                                                                    f == root->parse->jointree);
 761
 762                         lfirst(l) = pull_up_subqueries_recurse(root, lfirst(l),
 763                                                                                                    lowest_outer_join,
 764                                                                                                    lowest_nulling_outer_join,
 765                                                                                                    NULL,
 766                                                                                                    sub_deletion_ok);
 767                         if (lfirst(l) != NULL)
 768                                 have_undeleted_child = true;
 769                 }
 770
 771                 if (deletion_ok && !have_undeleted_child)
 772                 {
 773                         /* OK to delete this FromExpr entirely */
 774                         root->hasDeletedRTEs = true;            /* probably is set already */
 775                         return NULL;
 776                 }
 777         }
 778         else if (IsA(jtnode, JoinExpr))
 779         {
 780                 JoinExpr   *j = (JoinExpr *) jtnode;
 781
 782                 Assert(containing_appendrel == NULL);
 783                 /* Recurse, being careful to tell myself when inside outer join */
 784                 switch (j->jointype)
 785                 {
 786                         case JOIN_INNER:
 787
 788                                 /*
 789                                  * INNER JOIN can allow deletion of either child node, but not
 790                                  * both.  So right child gets permission to delete only if
 791                                  * left child didn't get removed.
 792                                  */
 793                                 j->larg = pull_up_subqueries_recurse(root, j->larg,
 794                                                                                                          lowest_outer_join,
 795                                                                                                    lowest_nulling_outer_join,
 796                                                                                                          NULL,
 797                                                                                                          true);
 798                                 j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 799                                                                                                          lowest_outer_join,
 800                                                                                                    lowest_nulling_outer_join,
 801                                                                                                          NULL,
 802                                                                                                          j->larg != NULL);
 803                                 break;
 804                         case JOIN_LEFT:
 805                         case JOIN_SEMI:
 806                         case JOIN_ANTI:
 807                                 j->larg = pull_up_subqueries_recurse(root, j->larg,
 808                                                                                                          j,
 809                                                                                                    lowest_nulling_outer_join,
 810                                                                                                          NULL,
 811                                                                                                          false);
 812                                 j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 813                                                                                                          j,
 814                                                                                                          j,
 815                                                                                                          NULL,
 816                                                                                                          false);
 817                                 break;
 818                         case JOIN_FULL:
 819                                 j->larg = pull_up_subqueries_recurse(root, j->larg,
 820                                                                                                          j,
 821                                                                                                          j,
 822                                                                                                          NULL,
 823                                                                                                          false);
 824                                 j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 825                                                                                                          j,
 826                                                                                                          j,
 827                                                                                                          NULL,
 828                                                                                                          false);
 829                                 break;
 830                         case JOIN_RIGHT:
 831                                 j->larg = pull_up_subqueries_recurse(root, j->larg,
 832                                                                                                          j,
 833                                                                                                          j,
 834                                                                                                          NULL,
 835                                                                                                          false);
 836                                 j->rarg = pull_up_subqueries_recurse(root, j->rarg,
 837                                                                                                          j,
 838                                                                                                    lowest_nulling_outer_join,
 839                                                                                                          NULL,
 840                                                                                                          false);
 841                                 break;
 842                         default:
 843                                 elog(ERROR, "unrecognized join type: %d",
 844                                          (int) j->jointype);
 845                                 break;
 846                 }
 847         }
 848         else
 849                 elog(ERROR, "unrecognized node type: %d",
 850                          (int) nodeTag(jtnode));
 851         return jtnode;
 852 }
 853
 854 /*
 855  * pull_up_simple_subquery
 856  *              Attempt to pull up a single simple subquery.
 857  *
 858  * jtnode is a RangeTblRef that has been tentatively identified as a simple
 859  * subquery by pull_up_subqueries.  We return the replacement jointree node,
 860  * or NULL if the subquery can be deleted entirely, or jtnode itself if we
 861  * determine that the subquery can't be pulled up after all.
 862  *
 863  * rte is the RangeTblEntry referenced by jtnode.  Remaining parameters are
 864  * as for pull_up_subqueries_recurse.
 865  */
 866 static Node *
 867 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 868                                                 JoinExpr *lowest_outer_join,
 869                                                 JoinExpr *lowest_nulling_outer_join,
 870                                                 AppendRelInfo *containing_appendrel,
 871                                                 bool deletion_ok)
 872 {
 873         Query      *parse = root->parse;
 874         int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 875         Query      *subquery;
 876         PlannerInfo *subroot;
 877         int                     rtoffset;
 878         pullup_replace_vars_context rvcontext;
 879         ListCell   *lc;
 880
 881         /*
 882          * Need a modifiable copy of the subquery to hack on.  Even if we didn't
 883          * sometimes choose not to pull up below, we must do this to avoid
 884          * problems if the same subquery is referenced from multiple jointree
 885          * items (which can't happen normally, but might after rule rewriting).
 886          */
 887         subquery = copyObject(rte->subquery);
 888
 889         /*
 890          * Create a PlannerInfo data structure for this subquery.
 891          *
 892          * NOTE: the next few steps should match the first processing in
 893          * subquery_planner().  Can we refactor to avoid code duplication, or
 894          * would that just make things uglier?
 895          */
 896         subroot = makeNode(PlannerInfo);
 897         subroot->parse = subquery;
 898         subroot->glob = root->glob;
 899         subroot->query_level = root->query_level;
 900         subroot->parent_root = root->parent_root;
 901         subroot->plan_params = NIL;
 902         subroot->planner_cxt = CurrentMemoryContext;
 903         subroot->init_plans = NIL;
 904         subroot->cte_plan_ids = NIL;
 905         subroot->multiexpr_params = NIL;
 906         subroot->eq_classes = NIL;
 907         subroot->append_rel_list = NIL;
 908         subroot->rowMarks = NIL;
 909         subroot->hasRecursion = false;
 910         subroot->wt_param_id = -1;
 911         subroot->non_recursive_plan = NULL;
 912
 913         /* No CTEs to worry about */
 914         Assert(subquery->cteList == NIL);
 915
 916         /*
 917          * Pull up any SubLinks within the subquery's quals, so that we don't
 918          * leave unoptimized SubLinks behind.
 919          */
 920         if (subquery->hasSubLinks)
 921                 pull_up_sublinks(subroot);
 922
 923         /*
 924          * Similarly, inline any set-returning functions in its rangetable.
 925          */
 926         inline_set_returning_functions(subroot);
 927
 928         /*
 929          * Recursively pull up the subquery's subqueries, so that
 930          * pull_up_subqueries' processing is complete for its jointree and
 931          * rangetable.
 932          *
 933          * Note: it's okay that the subquery's recursion starts with NULL for
 934          * containing-join info, even if we are within an outer join in the upper
 935          * query; the lower query starts with a clean slate for outer-join
 936          * semantics.  Likewise, we needn't pass down appendrel state.
 937          */
 938         pull_up_subqueries(subroot);
 939
 940         /*
 941          * Now we must recheck whether the subquery is still simple enough to pull
 942          * up.  If not, abandon processing it.
 943          *
 944          * We don't really need to recheck all the conditions involved, but it's
 945          * easier just to keep this "if" looking the same as the one in
 946          * pull_up_subqueries_recurse.
 947          */
 948         if (is_simple_subquery(subquery, rte,
 949                                                    lowest_outer_join, deletion_ok) &&
 950                 (containing_appendrel == NULL || is_safe_append_member(subquery)))
 951         {
 952                 /* good to go */
 953         }
 954         else
 955         {
 956                 /*
 957                  * Give up, return unmodified RangeTblRef.
 958                  *
 959                  * Note: The work we just did will be redone when the subquery gets
 960                  * planned on its own.  Perhaps we could avoid that by storing the
 961                  * modified subquery back into the rangetable, but I'm not gonna risk
 962                  * it now.
 963                  */
 964                 return jtnode;
 965         }
 966
 967         /*
 968          * We must flatten any join alias Vars in the subquery's targetlist,
 969          * because pulling up the subquery's subqueries might have changed their
 970          * expansions into arbitrary expressions, which could affect
 971          * pullup_replace_vars' decisions about whether PlaceHolderVar wrappers
 972          * are needed for tlist entries.  (Likely it'd be better to do
 973          * flatten_join_alias_vars on the whole query tree at some earlier stage,
 974          * maybe even in the rewriter; but for now let's just fix this case here.)
 975          */
 976         subquery->targetList = (List *)
 977                 flatten_join_alias_vars(subroot, (Node *) subquery->targetList);
 978
 979         /*
 980          * Adjust level-0 varnos in subquery so that we can append its rangetable
 981          * to upper query's.  We have to fix the subquery's append_rel_list as
 982          * well.
 983          */
 984         rtoffset = list_length(parse->rtable);
 985         OffsetVarNodes((Node *) subquery, rtoffset, 0);
 986         OffsetVarNodes((Node *) subroot->append_rel_list, rtoffset, 0);
 987
 988         /*
 989          * Upper-level vars in subquery are now one level closer to their parent
 990          * than before.
 991          */
 992         IncrementVarSublevelsUp((Node *) subquery, -1, 1);
 993         IncrementVarSublevelsUp((Node *) subroot->append_rel_list, -1, 1);
 994
 995         /*
 996          * The subquery's targetlist items are now in the appropriate form to
 997          * insert into the top query, but if we are under an outer join then
 998          * non-nullable items and lateral references may have to be turned into
 999          * PlaceHolderVars.  If we are dealing with an appendrel member then
1000          * anything that's not a simple Var has to be turned into a
1001          * PlaceHolderVar.  Set up required context data for pullup_replace_vars.
1002          */
1003         rvcontext.root = root;
1004         rvcontext.targetlist = subquery->targetList;
1005         rvcontext.target_rte = rte;
1006         if (rte->lateral)
1007                 rvcontext.relids = get_relids_in_jointree((Node *) subquery->jointree,
1008                                                                                                   true);
1009         else    /* won't need relids */
1010                 rvcontext.relids = NULL;
1011         rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
1012         rvcontext.varno = varno;
1013         rvcontext.need_phvs = (lowest_nulling_outer_join != NULL ||
1014                                                    containing_appendrel != NULL);
1015         rvcontext.wrap_non_vars = (containing_appendrel != NULL);
1016         /* initialize cache array with indexes 0 .. length(tlist) */
1017         rvcontext.rv_cache = palloc0((list_length(subquery->targetList) + 1) *
1018                                                                  sizeof(Node *));
1019
1020         /*
1021          * Replace all of the top query's references to the subquery's outputs
1022          * with copies of the adjusted subtlist items, being careful not to
1023          * replace any of the jointree structure. (This'd be a lot cleaner if we
1024          * could use query_tree_mutator.)  We have to use PHVs in the targetList,
1025          * returningList, and havingQual, since those are certainly above any
1026          * outer join.  replace_vars_in_jointree tracks its location in the
1027          * jointree and uses PHVs or not appropriately.
1028          */
1029         parse->targetList = (List *)
1030                 pullup_replace_vars((Node *) parse->targetList, &rvcontext);
1031         parse->returningList = (List *)
1032                 pullup_replace_vars((Node *) parse->returningList, &rvcontext);
1033         if (parse->onConflict)
1034                 parse->onConflict->onConflictSet = (List *)
1035                         pullup_replace_vars((Node *) parse->onConflict->onConflictSet, &rvcontext);
1036         replace_vars_in_jointree((Node *) parse->jointree, &rvcontext,
1037                                                          lowest_nulling_outer_join);
1038         Assert(parse->setOperations == NULL);
1039         parse->havingQual = pullup_replace_vars(parse->havingQual, &rvcontext);
1040
1041         /*
1042          * Replace references in the translated_vars lists of appendrels. When
1043          * pulling up an appendrel member, we do not need PHVs in the list of the
1044          * parent appendrel --- there isn't any outer join between. Elsewhere, use
1045          * PHVs for safety.  (This analysis could be made tighter but it seems
1046          * unlikely to be worth much trouble.)
1047          */
1048         foreach(lc, root->append_rel_list)
1049         {
1050                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
1051                 bool            save_need_phvs = rvcontext.need_phvs;
1052
1053                 if (appinfo == containing_appendrel)
1054                         rvcontext.need_phvs = false;
1055                 appinfo->translated_vars = (List *)
1056                         pullup_replace_vars((Node *) appinfo->translated_vars, &rvcontext);
1057                 rvcontext.need_phvs = save_need_phvs;
1058         }
1059
1060         /*
1061          * Replace references in the joinaliasvars lists of join RTEs.
1062          *
1063          * You might think that we could avoid using PHVs for alias vars of joins
1064          * below lowest_nulling_outer_join, but that doesn't work because the
1065          * alias vars could be referenced above that join; we need the PHVs to be
1066          * present in such references after the alias vars get flattened.  (It
1067          * might be worth trying to be smarter here, someday.)
1068          */
1069         foreach(lc, parse->rtable)
1070         {
1071                 RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(lc);
1072
1073                 if (otherrte->rtekind == RTE_JOIN)
1074                         otherrte->joinaliasvars = (List *)
1075                                 pullup_replace_vars((Node *) otherrte->joinaliasvars,
1076                                                                         &rvcontext);
1077         }
1078
1079         /*
1080          * If the subquery had a LATERAL marker, propagate that to any of its
1081          * child RTEs that could possibly now contain lateral cross-references.
1082          * The children might or might not contain any actual lateral
1083          * cross-references, but we have to mark the pulled-up child RTEs so that
1084          * later planner stages will check for such.
1085          */
1086         if (rte->lateral)
1087         {
1088                 foreach(lc, subquery->rtable)
1089                 {
1090                         RangeTblEntry *child_rte = (RangeTblEntry *) lfirst(lc);
1091
1092                         switch (child_rte->rtekind)
1093                         {
1094                                 case RTE_SUBQUERY:
1095                                 case RTE_FUNCTION:
1096                                 case RTE_VALUES:
1097                                         child_rte->lateral = true;
1098                                         break;
1099                                 case RTE_RELATION:
1100                                 case RTE_JOIN:
1101                                 case RTE_CTE:
1102                                         /* these can't contain any lateral references */
1103                                         break;
1104                         }
1105                 }
1106         }
1107
1108         /*
1109          * Now append the adjusted rtable entries to upper query. (We hold off
1110          * until after fixing the upper rtable entries; no point in running that
1111          * code on the subquery ones too.)
1112          */
1113         parse->rtable = list_concat(parse->rtable, subquery->rtable);
1114
1115         /*
1116          * Pull up any FOR UPDATE/SHARE markers, too.  (OffsetVarNodes already
1117          * adjusted the marker rtindexes, so just concat the lists.)
1118          */
1119         parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);
1120
1121         /*
1122          * We also have to fix the relid sets of any PlaceHolderVar nodes in the
1123          * parent query.  (This could perhaps be done by pullup_replace_vars(),
1124          * but it seems cleaner to use two passes.)  Note in particular that any
1125          * PlaceHolderVar nodes just created by pullup_replace_vars() will be
1126          * adjusted, so having created them with the subquery's varno is correct.
1127          *
1128          * Likewise, relids appearing in AppendRelInfo nodes have to be fixed. We
1129          * already checked that this won't require introducing multiple subrelids
1130          * into the single-slot AppendRelInfo structs.
1131          */
1132         if (parse->hasSubLinks || root->glob->lastPHId != 0 ||
1133                 root->append_rel_list)
1134         {
1135                 Relids          subrelids;
1136
1137                 subrelids = get_relids_in_jointree((Node *) subquery->jointree, false);
1138                 substitute_multiple_relids((Node *) parse, varno, subrelids);
1139                 fix_append_rel_relids(root->append_rel_list, varno, subrelids);
1140         }
1141
1142         /*
1143          * And now add subquery's AppendRelInfos to our list.
1144          */
1145         root->append_rel_list = list_concat(root->append_rel_list,
1146                                                                                 subroot->append_rel_list);
1147
1148         /*
1149          * We don't have to do the equivalent bookkeeping for outer-join or
1150          * LATERAL info, because that hasn't been set up yet.  placeholder_list
1151          * likewise.
1152          */
1153         Assert(root->join_info_list == NIL);
1154         Assert(subroot->join_info_list == NIL);
1155         Assert(root->lateral_info_list == NIL);
1156         Assert(subroot->lateral_info_list == NIL);
1157         Assert(root->placeholder_list == NIL);
1158         Assert(subroot->placeholder_list == NIL);
1159
1160         /*
1161          * Miscellaneous housekeeping.
1162          *
1163          * Although replace_rte_variables() faithfully updated parse->hasSubLinks
1164          * if it copied any SubLinks out of the subquery's targetlist, we still
1165          * could have SubLinks added to the query in the expressions of FUNCTION
1166          * and VALUES RTEs copied up from the subquery.  So it's necessary to copy
1167          * subquery->hasSubLinks anyway.  Perhaps this can be improved someday.
1168          */
1169         parse->hasSubLinks |= subquery->hasSubLinks;
1170
1171         /*
1172          * subquery won't be pulled up if it hasAggs or hasWindowFuncs, so no work
1173          * needed on those flags
1174          */
1175
1176         /*
1177          * Return the adjusted subquery jointree to replace the RangeTblRef entry
1178          * in parent's jointree; or, if we're flattening a subquery with empty
1179          * FROM list, return NULL to signal deletion of the subquery from the
1180          * parent jointree (and set hasDeletedRTEs to ensure cleanup later).
1181          */
1182         if (subquery->jointree->fromlist == NIL)
1183         {
1184                 Assert(deletion_ok);
1185                 Assert(subquery->jointree->quals == NULL);
1186                 root->hasDeletedRTEs = true;
1187                 return NULL;
1188         }
1189
1190         return (Node *) subquery->jointree;
1191 }
1192
1193 /*
1194  * pull_up_simple_union_all
1195  *              Pull up a single simple UNION ALL subquery.
1196  *
1197  * jtnode is a RangeTblRef that has been identified as a simple UNION ALL
1198  * subquery by pull_up_subqueries.  We pull up the leaf subqueries and
1199  * build an "append relation" for the union set.  The result value is just
1200  * jtnode, since we don't actually need to change the query jointree.
1201  */
1202 static Node *
1203 pull_up_simple_union_all(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
1204 {
1205         int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1206         Query      *subquery = rte->subquery;
1207         int                     rtoffset = list_length(root->parse->rtable);
1208         List       *rtable;
1209
1210         /*
1211          * Make a modifiable copy of the subquery's rtable, so we can adjust
1212          * upper-level Vars in it.  There are no such Vars in the setOperations
1213          * tree proper, so fixing the rtable should be sufficient.
1214          */
1215         rtable = copyObject(subquery->rtable);
1216
1217         /*
1218          * Upper-level vars in subquery are now one level closer to their parent
1219          * than before.  We don't have to worry about offsetting varnos, though,
1220          * because the UNION leaf queries can't cross-reference each other.
1221          */
1222         IncrementVarSublevelsUp_rtable(rtable, -1, 1);
1223
1224         /*
1225          * If the UNION ALL subquery had a LATERAL marker, propagate that to all
1226          * its children.  The individual children might or might not contain any
1227          * actual lateral cross-references, but we have to mark the pulled-up
1228          * child RTEs so that later planner stages will check for such.
1229          */
1230         if (rte->lateral)
1231         {
1232                 ListCell   *rt;
1233
1234                 foreach(rt, rtable)
1235                 {
1236                         RangeTblEntry *child_rte = (RangeTblEntry *) lfirst(rt);
1237
1238                         Assert(child_rte->rtekind == RTE_SUBQUERY);
1239                         child_rte->lateral = true;
1240                 }
1241         }
1242
1243         /*
1244          * Append child RTEs to parent rtable.
1245          */
1246         root->parse->rtable = list_concat(root->parse->rtable, rtable);
1247
1248         /*
1249          * Recursively scan the subquery's setOperations tree and add
1250          * AppendRelInfo nodes for leaf subqueries to the parent's
1251          * append_rel_list.  Also apply pull_up_subqueries to the leaf subqueries.
1252          */
1253         Assert(subquery->setOperations);
1254         pull_up_union_leaf_queries(subquery->setOperations, root, varno, subquery,
1255                                                            rtoffset);
1256
1257         /*
1258          * Mark the parent as an append relation.
1259          */
1260         rte->inh = true;
1261
1262         return jtnode;
1263 }
1264
1265 /*
1266  * pull_up_union_leaf_queries -- recursive guts of pull_up_simple_union_all
1267  *
1268  * Build an AppendRelInfo for each leaf query in the setop tree, and then
1269  * apply pull_up_subqueries to the leaf query.
1270  *
1271  * Note that setOpQuery is the Query containing the setOp node, whose tlist
1272  * contains references to all the setop output columns.  When called from
1273  * pull_up_simple_union_all, this is *not* the same as root->parse, which is
1274  * the parent Query we are pulling up into.
1275  *
1276  * parentRTindex is the appendrel parent's index in root->parse->rtable.
1277  *
1278  * The child RTEs have already been copied to the parent.  childRToffset
1279  * tells us where in the parent's range table they were copied.  When called
1280  * from flatten_simple_union_all, childRToffset is 0 since the child RTEs
1281  * were already in root->parse->rtable and no RT index adjustment is needed.
1282  */
1283 static void
1284 pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
1285                                                    Query *setOpQuery, int childRToffset)
1286 {
1287         if (IsA(setOp, RangeTblRef))
1288         {
1289                 RangeTblRef *rtr = (RangeTblRef *) setOp;
1290                 int                     childRTindex;
1291                 AppendRelInfo *appinfo;
1292
1293                 /*
1294                  * Calculate the index in the parent's range table
1295                  */
1296                 childRTindex = childRToffset + rtr->rtindex;
1297
1298                 /*
1299                  * Build a suitable AppendRelInfo, and attach to parent's list.
1300                  */
1301                 appinfo = makeNode(AppendRelInfo);
1302                 appinfo->parent_relid = parentRTindex;
1303                 appinfo->child_relid = childRTindex;
1304                 appinfo->parent_reltype = InvalidOid;
1305                 appinfo->child_reltype = InvalidOid;
1306                 make_setop_translation_list(setOpQuery, childRTindex,
1307                                                                         &appinfo->translated_vars);
1308                 appinfo->parent_reloid = InvalidOid;
1309                 root->append_rel_list = lappend(root->append_rel_list, appinfo);
1310
1311                 /*
1312                  * Recursively apply pull_up_subqueries to the new child RTE.  (We
1313                  * must build the AppendRelInfo first, because this will modify it.)
1314                  * Note that we can pass NULL for containing-join info even if we're
1315                  * actually under an outer join, because the child's expressions
1316                  * aren't going to propagate up to the join.  Also, we ignore the
1317                  * possibility that pull_up_subqueries_recurse() returns a different
1318                  * jointree node than what we pass it; if it does, the important thing
1319                  * is that it replaced the child relid in the AppendRelInfo node.
1320                  */
1321                 rtr = makeNode(RangeTblRef);
1322                 rtr->rtindex = childRTindex;
1323                 (void) pull_up_subqueries_recurse(root, (Node *) rtr,
1324                                                                                   NULL, NULL, appinfo, false);
1325         }
1326         else if (IsA(setOp, SetOperationStmt))
1327         {
1328                 SetOperationStmt *op = (SetOperationStmt *) setOp;
1329
1330                 /* Recurse to reach leaf queries */
1331                 pull_up_union_leaf_queries(op->larg, root, parentRTindex, setOpQuery,
1332                                                                    childRToffset);
1333                 pull_up_union_leaf_queries(op->rarg, root, parentRTindex, setOpQuery,
1334                                                                    childRToffset);
1335         }
1336         else
1337         {
1338                 elog(ERROR, "unrecognized node type: %d",
1339                          (int) nodeTag(setOp));
1340         }
1341 }
1342
1343 /*
1344  * make_setop_translation_list
1345  *        Build the list of translations from parent Vars to child Vars for
1346  *        a UNION ALL member.  (At this point it's just a simple list of
1347  *        referencing Vars, but if we succeed in pulling up the member
1348  *        subquery, the Vars will get replaced by pulled-up expressions.)
1349  */
1350 static void
1351 make_setop_translation_list(Query *query, Index newvarno,
1352                                                         List **translated_vars)
1353 {
1354         List       *vars = NIL;
1355         ListCell   *l;
1356
1357         foreach(l, query->targetList)
1358         {
1359                 TargetEntry *tle = (TargetEntry *) lfirst(l);
1360
1361                 if (tle->resjunk)
1362                         continue;
1363
1364                 vars = lappend(vars, makeVarFromTargetEntry(newvarno, tle));
1365         }
1366
1367         *translated_vars = vars;
1368 }
1369
1370 /*
1371  * is_simple_subquery
1372  *        Check a subquery in the range table to see if it's simple enough
1373  *        to pull up into the parent query.
1374  *
1375  * rte is the RTE_SUBQUERY RangeTblEntry that contained the subquery.
1376  * (Note subquery is not necessarily equal to rte->subquery; it could be a
1377  * processed copy of that.)
1378  * lowest_outer_join is the lowest outer join above the subquery, or NULL.
1379  * deletion_ok is TRUE if it'd be okay to delete the subquery entirely.
1380  */
1381 static bool
1382 is_simple_subquery(Query *subquery, RangeTblEntry *rte,
1383                                    JoinExpr *lowest_outer_join,
1384                                    bool deletion_ok)
1385 {
1386         /*
1387          * Let's just make sure it's a valid subselect ...
1388          */
1389         if (!IsA(subquery, Query) ||
1390                 subquery->commandType != CMD_SELECT ||
1391                 subquery->utilityStmt != NULL)
1392                 elog(ERROR, "subquery is bogus");
1393
1394         /*
1395          * Can't currently pull up a query with setops (unless it's simple UNION
1396          * ALL, which is handled by a different code path). Maybe after querytree
1397          * redesign...
1398          */
1399         if (subquery->setOperations)
1400                 return false;
1401
1402         /*
1403          * Can't pull up a subquery involving grouping, aggregation, sorting,
1404          * limiting, or WITH.  (XXX WITH could possibly be allowed later)
1405          *
1406          * We also don't pull up a subquery that has explicit FOR UPDATE/SHARE
1407          * clauses, because pullup would cause the locking to occur semantically
1408          * higher than it should.  Implicit FOR UPDATE/SHARE is okay because in
1409          * that case the locking was originally declared in the upper query
1410          * anyway.
1411          */
1412         if (subquery->hasAggs ||
1413                 subquery->hasWindowFuncs ||
1414                 subquery->groupClause ||
1415                 subquery->havingQual ||
1416                 subquery->sortClause ||
1417                 subquery->distinctClause ||
1418                 subquery->limitOffset ||
1419                 subquery->limitCount ||
1420                 subquery->hasForUpdate ||
1421                 subquery->cteList)
1422                 return false;
1423
1424         /*
1425          * Don't pull up if the RTE represents a security-barrier view; we
1426          * couldn't prevent information leakage once the RTE's Vars are scattered
1427          * about in the upper query.
1428          */
1429         if (rte->security_barrier)
1430                 return false;
1431
1432         /*
1433          * Don't pull up a subquery with an empty jointree, unless it has no quals
1434          * and deletion_ok is TRUE.  query_planner() will correctly generate a
1435          * Result plan for a jointree that's totally empty, but we can't cope with
1436          * an empty FromExpr appearing lower down in a jointree: we identify join
1437          * rels via baserelid sets, so we couldn't distinguish a join containing
1438          * such a FromExpr from one without it.  This would for example break the
1439          * PlaceHolderVar mechanism, since we'd have no way to identify where to
1440          * evaluate a PHV coming out of the subquery.  We can only handle such
1441          * cases if the place where the subquery is linked is a FromExpr or inner
1442          * JOIN that would still be nonempty after removal of the subquery, so
1443          * that it's still identifiable via its contained baserelids.  Safe
1444          * contexts are signaled by deletion_ok.  But even in a safe context, we
1445          * must keep the subquery if it has any quals, because it's unclear where
1446          * to put them in the upper query.  (Note that deletion of a subquery is
1447          * also dependent on the check below that its targetlist contains no
1448          * set-returning functions.  Deletion from a FROM list or inner JOIN is
1449          * okay only if the subquery must return exactly one row.)
1450          */
1451         if (subquery->jointree->fromlist == NIL &&
1452                 (subquery->jointree->quals || !deletion_ok))
1453                 return false;
1454
1455         /*
1456          * If the subquery is LATERAL, check for pullup restrictions from that.
1457          */
1458         if (rte->lateral)
1459         {
1460                 bool            restricted;
1461                 Relids          safe_upper_varnos;
1462
1463                 /*
1464                  * The subquery's WHERE and JOIN/ON quals mustn't contain any lateral
1465                  * references to rels outside a higher outer join (including the case
1466                  * where the outer join is within the subquery itself).  In such a
1467                  * case, pulling up would result in a situation where we need to
1468                  * postpone quals from below an outer join to above it, which is
1469                  * probably completely wrong and in any case is a complication that
1470                  * doesn't seem worth addressing at the moment.
1471                  */
1472                 if (lowest_outer_join != NULL)
1473                 {
1474                         restricted = true;
1475                         safe_upper_varnos = get_relids_in_jointree((Node *) lowest_outer_join,
1476                                                                                                            true);
1477                 }
1478                 else
1479                 {
1480                         restricted = false;
1481                         safe_upper_varnos = NULL;       /* doesn't matter */
1482                 }
1483
1484                 if (jointree_contains_lateral_outer_refs((Node *) subquery->jointree,
1485                                                                                           restricted, safe_upper_varnos))
1486                         return false;
1487
1488                 /*
1489                  * If there's an outer join above the LATERAL subquery, also disallow
1490                  * pullup if the subquery's targetlist has any references to rels
1491                  * outside the outer join, since these might get pulled into quals
1492                  * above the subquery (but in or below the outer join) and then lead
1493                  * to qual-postponement issues similar to the case checked for above.
1494                  * (We wouldn't need to prevent pullup if no such references appear in
1495                  * outer-query quals, but we don't have enough info here to check
1496                  * that.  Also, maybe this restriction could be removed if we forced
1497                  * such refs to be wrapped in PlaceHolderVars, even when they're below
1498                  * the nearest outer join?      But it's a pretty hokey usage, so not
1499                  * clear this is worth sweating over.)
1500                  */
1501                 if (lowest_outer_join != NULL)
1502                 {
1503                         Relids          lvarnos = pull_varnos_of_level((Node *) subquery->targetList, 1);
1504
1505                         if (!bms_is_subset(lvarnos, safe_upper_varnos))
1506                                 return false;
1507                 }
1508         }
1509
1510         /*
1511          * Don't pull up a subquery that has any set-returning functions in its
1512          * targetlist.  Otherwise we might well wind up inserting set-returning
1513          * functions into places where they mustn't go, such as quals of higher
1514          * queries.  This also ensures deletion of an empty jointree is valid.
1515          */
1516         if (expression_returns_set((Node *) subquery->targetList))
1517                 return false;
1518
1519         /*
1520          * Don't pull up a subquery that has any volatile functions in its
1521          * targetlist.  Otherwise we might introduce multiple evaluations of these
1522          * functions, if they get copied to multiple places in the upper query,
1523          * leading to surprising results.  (Note: the PlaceHolderVar mechanism
1524          * doesn't quite guarantee single evaluation; else we could pull up anyway
1525          * and just wrap such items in PlaceHolderVars ...)
1526          */
1527         if (contain_volatile_functions((Node *) subquery->targetList))
1528                 return false;
1529
1530         return true;
1531 }
1532
1533 /*
1534  * pull_up_simple_values
1535  *              Pull up a single simple VALUES RTE.
1536  *
1537  * jtnode is a RangeTblRef that has been identified as a simple VALUES RTE
1538  * by pull_up_subqueries.  We always return NULL indicating that the RTE
1539  * can be deleted entirely (all failure cases should have been detected by
1540  * is_simple_values()).
1541  *
1542  * rte is the RangeTblEntry referenced by jtnode.  Because of the limited
1543  * possible usage of VALUES RTEs, we do not need the remaining parameters
1544  * of pull_up_subqueries_recurse.
1545  */
1546 static Node *
1547 pull_up_simple_values(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
1548 {
1549         Query      *parse = root->parse;
1550         int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1551         List       *values_list;
1552         List       *tlist;
1553         AttrNumber      attrno;
1554         pullup_replace_vars_context rvcontext;
1555         ListCell   *lc;
1556
1557         Assert(rte->rtekind == RTE_VALUES);
1558         Assert(list_length(rte->values_lists) == 1);
1559
1560         /*
1561          * Need a modifiable copy of the VALUES list to hack on, just in case it's
1562          * multiply referenced.
1563          */
1564         values_list = (List *) copyObject(linitial(rte->values_lists));
1565
1566         /*
1567          * The VALUES RTE can't contain any Vars of level zero, let alone any that
1568          * are join aliases, so no need to flatten join alias Vars.
1569          */
1570         Assert(!contain_vars_of_level((Node *) values_list, 0));
1571
1572         /*
1573          * Set up required context data for pullup_replace_vars.  In particular,
1574          * we have to make the VALUES list look like a subquery targetlist.
1575          */
1576         tlist = NIL;
1577         attrno = 1;
1578         foreach(lc, values_list)
1579         {
1580                 tlist = lappend(tlist,
1581                                                 makeTargetEntry((Expr *) lfirst(lc),
1582                                                                                 attrno,
1583                                                                                 NULL,
1584                                                                                 false));
1585                 attrno++;
1586         }
1587         rvcontext.root = root;
1588         rvcontext.targetlist = tlist;
1589         rvcontext.target_rte = rte;
1590         rvcontext.relids = NULL;
1591         rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
1592         rvcontext.varno = varno;
1593         rvcontext.need_phvs = false;
1594         rvcontext.wrap_non_vars = false;
1595         /* initialize cache array with indexes 0 .. length(tlist) */
1596         rvcontext.rv_cache = palloc0((list_length(tlist) + 1) *
1597                                                                  sizeof(Node *));
1598
1599         /*
1600          * Replace all of the top query's references to the RTE's outputs with
1601          * copies of the adjusted VALUES expressions, being careful not to replace
1602          * any of the jointree structure. (This'd be a lot cleaner if we could use
1603          * query_tree_mutator.)  Much of this should be no-ops in the dummy Query
1604          * that surrounds a VALUES RTE, but it's not enough code to be worth
1605          * removing.
1606          */
1607         parse->targetList = (List *)
1608                 pullup_replace_vars((Node *) parse->targetList, &rvcontext);
1609         parse->returningList = (List *)
1610                 pullup_replace_vars((Node *) parse->returningList, &rvcontext);
1611         if (parse->onConflict)
1612                 parse->onConflict->onConflictSet = (List *)
1613                         pullup_replace_vars((Node *) parse->onConflict->onConflictSet, &rvcontext);
1614         replace_vars_in_jointree((Node *) parse->jointree, &rvcontext, NULL);
1615         Assert(parse->setOperations == NULL);
1616         parse->havingQual = pullup_replace_vars(parse->havingQual, &rvcontext);
1617
1618         /*
1619          * There should be no appendrels to fix, nor any join alias Vars, nor any
1620          * outer joins and hence no PlaceHolderVars.
1621          */
1622         Assert(root->append_rel_list == NIL);
1623         Assert(list_length(parse->rtable) == 1);
1624         Assert(root->join_info_list == NIL);
1625         Assert(root->lateral_info_list == NIL);
1626         Assert(root->placeholder_list == NIL);
1627
1628         /*
1629          * Return NULL to signal deletion of the VALUES RTE from the parent
1630          * jointree (and set hasDeletedRTEs to ensure cleanup later).
1631          */
1632         root->hasDeletedRTEs = true;
1633         return NULL;
1634 }
1635
1636 /*
1637  * is_simple_values
1638  *        Check a VALUES RTE in the range table to see if it's simple enough
1639  *        to pull up into the parent query.
1640  *
1641  * rte is the RTE_VALUES RangeTblEntry to check.
1642  * deletion_ok is TRUE if it'd be okay to delete the VALUES RTE entirely.
1643  */
1644 static bool
1645 is_simple_values(PlannerInfo *root, RangeTblEntry *rte, bool deletion_ok)
1646 {
1647         Assert(rte->rtekind == RTE_VALUES);
1648
1649         /*
1650          * We can only pull up a VALUES RTE if deletion_ok is TRUE.  It's
1651          * basically the same case as a sub-select with empty FROM list; see
1652          * comments in is_simple_subquery().
1653          */
1654         if (!deletion_ok)
1655                 return false;
1656
1657         /*
1658          * Also, there must be exactly one VALUES list, else it's not semantically
1659          * correct to delete the VALUES RTE.
1660          */
1661         if (list_length(rte->values_lists) != 1)
1662                 return false;
1663
1664         /*
1665          * Because VALUES can't appear under an outer join (or at least, we won't
1666          * try to pull it up if it does), we need not worry about LATERAL.
1667          */
1668
1669         /*
1670          * Don't pull up a VALUES that contains any set-returning or volatile
1671          * functions.  Again, the considerations here are basically identical to
1672          * restrictions on a subquery's targetlist.
1673          */
1674         if (expression_returns_set((Node *) rte->values_lists) ||
1675                 contain_volatile_functions((Node *) rte->values_lists))
1676                 return false;
1677
1678         /*
1679          * Do not pull up a VALUES that's not the only RTE in its parent query.
1680          * This is actually the only case that the parser will generate at the
1681          * moment, and assuming this is true greatly simplifies
1682          * pull_up_simple_values().
1683          */
1684         if (list_length(root->parse->rtable) != 1 ||
1685                 rte != (RangeTblEntry *) linitial(root->parse->rtable))
1686                 return false;
1687
1688         return true;
1689 }
1690
1691 /*
1692  * is_simple_union_all
1693  *        Check a subquery to see if it's a simple UNION ALL.
1694  *
1695  * We require all the setops to be UNION ALL (no mixing) and there can't be
1696  * any datatype coercions involved, ie, all the leaf queries must emit the
1697  * same datatypes.
1698  */
1699 static bool
1700 is_simple_union_all(Query *subquery)
1701 {
1702         SetOperationStmt *topop;
1703
1704         /* Let's just make sure it's a valid subselect ... */
1705         if (!IsA(subquery, Query) ||
1706                 subquery->commandType != CMD_SELECT ||
1707                 subquery->utilityStmt != NULL)
1708                 elog(ERROR, "subquery is bogus");
1709
1710         /* Is it a set-operation query at all? */
1711         topop = (SetOperationStmt *) subquery->setOperations;
1712         if (!topop)
1713                 return false;
1714         Assert(IsA(topop, SetOperationStmt));
1715
1716         /* Can't handle ORDER BY, LIMIT/OFFSET, locking, or WITH */
1717         if (subquery->sortClause ||
1718                 subquery->limitOffset ||
1719                 subquery->limitCount ||
1720                 subquery->rowMarks ||
1721                 subquery->cteList)
1722                 return false;
1723
1724         /* Recursively check the tree of set operations */
1725         return is_simple_union_all_recurse((Node *) topop, subquery,
1726                                                                            topop->colTypes);
1727 }
1728
1729 static bool
1730 is_simple_union_all_recurse(Node *setOp, Query *setOpQuery, List *colTypes)
1731 {
1732         if (IsA(setOp, RangeTblRef))
1733         {
1734                 RangeTblRef *rtr = (RangeTblRef *) setOp;
1735                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, setOpQuery->rtable);
1736                 Query      *subquery = rte->subquery;
1737
1738                 Assert(subquery != NULL);
1739
1740                 /* Leaf nodes are OK if they match the toplevel column types */
1741                 /* We don't have to compare typmods or collations here */
1742                 return tlist_same_datatypes(subquery->targetList, colTypes, true);
1743         }
1744         else if (IsA(setOp, SetOperationStmt))
1745         {
1746                 SetOperationStmt *op = (SetOperationStmt *) setOp;
1747
1748                 /* Must be UNION ALL */
1749                 if (op->op != SETOP_UNION || !op->all)
1750                         return false;
1751
1752                 /* Recurse to check inputs */
1753                 return is_simple_union_all_recurse(op->larg, setOpQuery, colTypes) &&
1754                         is_simple_union_all_recurse(op->rarg, setOpQuery, colTypes);
1755         }
1756         else
1757         {
1758                 elog(ERROR, "unrecognized node type: %d",
1759                          (int) nodeTag(setOp));
1760                 return false;                   /* keep compiler quiet */
1761         }
1762 }
1763
1764 /*
1765  * is_safe_append_member
1766  *        Check a subquery that is a leaf of a UNION ALL appendrel to see if it's
1767  *        safe to pull up.
1768  */
1769 static bool
1770 is_safe_append_member(Query *subquery)
1771 {
1772         FromExpr   *jtnode;
1773
1774         /*
1775          * It's only safe to pull up the child if its jointree contains exactly
1776          * one RTE, else the AppendRelInfo data structure breaks. The one base RTE
1777          * could be buried in several levels of FromExpr, however.
1778          *
1779          * Also, the child can't have any WHERE quals because there's no place to
1780          * put them in an appendrel.  (This is a bit annoying...) If we didn't
1781          * need to check this, we'd just test whether get_relids_in_jointree()
1782          * yields a singleton set, to be more consistent with the coding of
1783          * fix_append_rel_relids().
1784          */
1785         jtnode = subquery->jointree;
1786         while (IsA(jtnode, FromExpr))
1787         {
1788                 if (jtnode->quals != NULL)
1789                         return false;
1790                 if (list_length(jtnode->fromlist) != 1)
1791                         return false;
1792                 jtnode = linitial(jtnode->fromlist);
1793         }
1794         if (!IsA(jtnode, RangeTblRef))
1795                 return false;
1796
1797         return true;
1798 }
1799
1800 /*
1801  * jointree_contains_lateral_outer_refs
1802  *              Check for disallowed lateral references in a jointree's quals
1803  *
1804  * If restricted is false, all level-1 Vars are allowed (but we still must
1805  * search the jointree, since it might contain outer joins below which there
1806  * will be restrictions).  If restricted is true, return TRUE when any qual
1807  * in the jointree contains level-1 Vars coming from outside the rels listed
1808  * in safe_upper_varnos.
1809  */
1810 static bool
1811 jointree_contains_lateral_outer_refs(Node *jtnode, bool restricted,
1812                                                                          Relids safe_upper_varnos)
1813 {
1814         if (jtnode == NULL)
1815                 return false;
1816         if (IsA(jtnode, RangeTblRef))
1817                 return false;
1818         else if (IsA(jtnode, FromExpr))
1819         {
1820                 FromExpr   *f = (FromExpr *) jtnode;
1821                 ListCell   *l;
1822
1823                 /* First, recurse to check child joins */
1824                 foreach(l, f->fromlist)
1825                 {
1826                         if (jointree_contains_lateral_outer_refs(lfirst(l),
1827                                                                                                          restricted,
1828                                                                                                          safe_upper_varnos))
1829                                 return true;
1830                 }
1831
1832                 /* Then check the top-level quals */
1833                 if (restricted &&
1834                         !bms_is_subset(pull_varnos_of_level(f->quals, 1),
1835                                                    safe_upper_varnos))
1836                         return true;
1837         }
1838         else if (IsA(jtnode, JoinExpr))
1839         {
1840                 JoinExpr   *j = (JoinExpr *) jtnode;
1841
1842                 /*
1843                  * If this is an outer join, we mustn't allow any upper lateral
1844                  * references in or below it.
1845                  */
1846                 if (j->jointype != JOIN_INNER)
1847                 {
1848                         restricted = true;
1849                         safe_upper_varnos = NULL;
1850                 }
1851
1852                 /* Check the child joins */
1853                 if (jointree_contains_lateral_outer_refs(j->larg,
1854                                                                                                  restricted,
1855                                                                                                  safe_upper_varnos))
1856                         return true;
1857                 if (jointree_contains_lateral_outer_refs(j->rarg,
1858                                                                                                  restricted,
1859                                                                                                  safe_upper_varnos))
1860                         return true;
1861
1862                 /* Check the JOIN's qual clauses */
1863                 if (restricted &&
1864                         !bms_is_subset(pull_varnos_of_level(j->quals, 1),
1865                                                    safe_upper_varnos))
1866                         return true;
1867         }
1868         else
1869                 elog(ERROR, "unrecognized node type: %d",
1870                          (int) nodeTag(jtnode));
1871         return false;
1872 }
1873
1874 /*
1875  * Helper routine for pull_up_subqueries: do pullup_replace_vars on every
1876  * expression in the jointree, without changing the jointree structure itself.
1877  * Ugly, but there's no other way...
1878  *
1879  * If we are at or below lowest_nulling_outer_join, we can suppress use of
1880  * PlaceHolderVars wrapped around the replacement expressions.
1881  */
1882 static void
1883 replace_vars_in_jointree(Node *jtnode,
1884                                                  pullup_replace_vars_context *context,
1885                                                  JoinExpr *lowest_nulling_outer_join)
1886 {
1887         if (jtnode == NULL)
1888                 return;
1889         if (IsA(jtnode, RangeTblRef))
1890         {
1891                 /*
1892                  * If the RangeTblRef refers to a LATERAL subquery (that isn't the
1893                  * same subquery we're pulling up), it might contain references to the
1894                  * target subquery, which we must replace.  We drive this from the
1895                  * jointree scan, rather than a scan of the rtable, for a couple of
1896                  * reasons: we can avoid processing no-longer-referenced RTEs, and we
1897                  * can use the appropriate setting of need_phvs depending on whether
1898                  * the RTE is above possibly-nulling outer joins or not.
1899                  */
1900                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1901
1902                 if (varno != context->varno)    /* ignore target subquery itself */
1903                 {
1904                         RangeTblEntry *rte = rt_fetch(varno, context->root->parse->rtable);
1905
1906                         Assert(rte != context->target_rte);
1907                         if (rte->lateral)
1908                         {
1909                                 switch (rte->rtekind)
1910                                 {
1911                                         case RTE_SUBQUERY:
1912                                                 rte->subquery =
1913                                                         pullup_replace_vars_subquery(rte->subquery,
1914                                                                                                                  context);
1915                                                 break;
1916                                         case RTE_FUNCTION:
1917                                                 rte->functions = (List *)
1918                                                         pullup_replace_vars((Node *) rte->functions,
1919                                                                                                 context);
1920                                                 break;
1921                                         case RTE_VALUES:
1922                                                 rte->values_lists = (List *)
1923                                                         pullup_replace_vars((Node *) rte->values_lists,
1924                                                                                                 context);
1925                                                 break;
1926                                         case RTE_RELATION:
1927                                         case RTE_JOIN:
1928                                         case RTE_CTE:
1929                                                 /* these shouldn't be marked LATERAL */
1930                                                 Assert(false);
1931                                                 break;
1932                                 }
1933                         }
1934                 }
1935         }
1936         else if (IsA(jtnode, FromExpr))
1937         {
1938                 FromExpr   *f = (FromExpr *) jtnode;
1939                 ListCell   *l;
1940
1941                 foreach(l, f->fromlist)
1942                         replace_vars_in_jointree(lfirst(l), context,
1943                                                                          lowest_nulling_outer_join);
1944                 f->quals = pullup_replace_vars(f->quals, context);
1945         }
1946         else if (IsA(jtnode, JoinExpr))
1947         {
1948                 JoinExpr   *j = (JoinExpr *) jtnode;
1949                 bool            save_need_phvs = context->need_phvs;
1950
1951                 if (j == lowest_nulling_outer_join)
1952                 {
1953                         /* no more PHVs in or below this join */
1954                         context->need_phvs = false;
1955                         lowest_nulling_outer_join = NULL;
1956                 }
1957                 replace_vars_in_jointree(j->larg, context, lowest_nulling_outer_join);
1958                 replace_vars_in_jointree(j->rarg, context, lowest_nulling_outer_join);
1959                 j->quals = pullup_replace_vars(j->quals, context);
1960
1961                 /*
1962                  * We don't bother to update the colvars list, since it won't be used
1963                  * again ...
1964                  */
1965                 context->need_phvs = save_need_phvs;
1966         }
1967         else
1968                 elog(ERROR, "unrecognized node type: %d",
1969                          (int) nodeTag(jtnode));
1970 }
1971
1972 /*
1973  * Apply pullup variable replacement throughout an expression tree
1974  *
1975  * Returns a modified copy of the tree, so this can't be used where we
1976  * need to do in-place replacement.
1977  */
1978 static Node *
1979 pullup_replace_vars(Node *expr, pullup_replace_vars_context *context)
1980 {
1981         return replace_rte_variables(expr,
1982                                                                  context->varno, 0,
1983                                                                  pullup_replace_vars_callback,
1984                                                                  (void *) context,
1985                                                                  context->outer_hasSubLinks);
1986 }
1987
1988 static Node *
1989 pullup_replace_vars_callback(Var *var,
1990                                                          replace_rte_variables_context *context)
1991 {
1992         pullup_replace_vars_context *rcon = (pullup_replace_vars_context *) context->callback_arg;
1993         int                     varattno = var->varattno;
1994         Node       *newnode;
1995
1996         /*
1997          * If PlaceHolderVars are needed, we cache the modified expressions in
1998          * rcon->rv_cache[].  This is not in hopes of any material speed gain
1999          * within this function, but to avoid generating identical PHVs with
2000          * different IDs.  That would result in duplicate evaluations at runtime,
2001          * and possibly prevent optimizations that rely on recognizing different
2002          * references to the same subquery output as being equal().  So it's worth
2003          * a bit of extra effort to avoid it.
2004          */
2005         if (rcon->need_phvs &&
2006                 varattno >= InvalidAttrNumber &&
2007                 varattno <= list_length(rcon->targetlist) &&
2008                 rcon->rv_cache[varattno] != NULL)
2009         {
2010                 /* Just copy the entry and fall through to adjust its varlevelsup */
2011                 newnode = copyObject(rcon->rv_cache[varattno]);
2012         }
2013         else if (varattno == InvalidAttrNumber)
2014         {
2015                 /* Must expand whole-tuple reference into RowExpr */
2016                 RowExpr    *rowexpr;
2017                 List       *colnames;
2018                 List       *fields;
2019                 bool            save_need_phvs = rcon->need_phvs;
2020                 int                     save_sublevelsup = context->sublevels_up;
2021
2022                 /*
2023                  * If generating an expansion for a var of a named rowtype (ie, this
2024                  * is a plain relation RTE), then we must include dummy items for
2025                  * dropped columns.  If the var is RECORD (ie, this is a JOIN), then
2026                  * omit dropped columns. Either way, attach column names to the
2027                  * RowExpr for use of ruleutils.c.
2028                  *
2029                  * In order to be able to cache the results, we always generate the
2030                  * expansion with varlevelsup = 0, and then adjust if needed.
2031                  */
2032                 expandRTE(rcon->target_rte,
2033                                   var->varno, 0 /* not varlevelsup */ , var->location,
2034                                   (var->vartype != RECORDOID),
2035                                   &colnames, &fields);
2036                 /* Adjust the generated per-field Vars, but don't insert PHVs */
2037                 rcon->need_phvs = false;
2038                 context->sublevels_up = 0;              /* to match the expandRTE output */
2039                 fields = (List *) replace_rte_variables_mutator((Node *) fields,
2040                                                                                                                 context);
2041                 rcon->need_phvs = save_need_phvs;
2042                 context->sublevels_up = save_sublevelsup;
2043
2044                 rowexpr = makeNode(RowExpr);
2045                 rowexpr->args = fields;
2046                 rowexpr->row_typeid = var->vartype;
2047                 rowexpr->row_format = COERCE_IMPLICIT_CAST;
2048                 rowexpr->colnames = colnames;
2049                 rowexpr->location = var->location;
2050                 newnode = (Node *) rowexpr;
2051
2052                 /*
2053                  * Insert PlaceHolderVar if needed.  Notice that we are wrapping one
2054                  * PlaceHolderVar around the whole RowExpr, rather than putting one
2055                  * around each element of the row.  This is because we need the
2056                  * expression to yield NULL, not ROW(NULL,NULL,...) when it is forced
2057                  * to null by an outer join.
2058                  */
2059                 if (rcon->need_phvs)
2060                 {
2061                         /* RowExpr is certainly not strict, so always need PHV */
2062                         newnode = (Node *)
2063                                 make_placeholder_expr(rcon->root,
2064                                                                           (Expr *) newnode,
2065                                                                           bms_make_singleton(rcon->varno));
2066                         /* cache it with the PHV, and with varlevelsup still zero */
2067                         rcon->rv_cache[InvalidAttrNumber] = copyObject(newnode);
2068                 }
2069         }
2070         else
2071         {
2072                 /* Normal case referencing one targetlist element */
2073                 TargetEntry *tle = get_tle_by_resno(rcon->targetlist, varattno);
2074
2075                 if (tle == NULL)                /* shouldn't happen */
2076                         elog(ERROR, "could not find attribute %d in subquery targetlist",
2077                                  varattno);
2078
2079                 /* Make a copy of the tlist item to return */
2080                 newnode = copyObject(tle->expr);
2081
2082                 /* Insert PlaceHolderVar if needed */
2083                 if (rcon->need_phvs)
2084                 {
2085                         bool            wrap;
2086
2087                         if (newnode && IsA(newnode, Var) &&
2088                                 ((Var *) newnode)->varlevelsup == 0)
2089                         {
2090                                 /*
2091                                  * Simple Vars always escape being wrapped, unless they are
2092                                  * lateral references to something outside the subquery being
2093                                  * pulled up.  (Even then, we could omit the PlaceHolderVar if
2094                                  * the referenced rel is under the same lowest outer join, but
2095                                  * it doesn't seem worth the trouble to check that.)
2096                                  */
2097                                 if (rcon->target_rte->lateral &&
2098                                         !bms_is_member(((Var *) newnode)->varno, rcon->relids))
2099                                         wrap = true;
2100                                 else
2101                                         wrap = false;
2102                         }
2103                         else if (newnode && IsA(newnode, PlaceHolderVar) &&
2104                                          ((PlaceHolderVar *) newnode)->phlevelsup == 0)
2105                         {
2106                                 /* No need to wrap a PlaceHolderVar with another one, either */
2107                                 wrap = false;
2108                         }
2109                         else if (rcon->wrap_non_vars)
2110                         {
2111                                 /* Wrap all non-Vars in a PlaceHolderVar */
2112                                 wrap = true;
2113                         }
2114                         else
2115                         {
2116                                 /*
2117                                  * If it contains a Var of the subquery being pulled up, and
2118                                  * does not contain any non-strict constructs, then it's
2119                                  * certainly nullable so we don't need to insert a
2120                                  * PlaceHolderVar.
2121                                  *
2122                                  * This analysis could be tighter: in particular, a non-strict
2123                                  * construct hidden within a lower-level PlaceHolderVar is not
2124                                  * reason to add another PHV.  But for now it doesn't seem
2125                                  * worth the code to be more exact.
2126                                  *
2127                                  * Note: in future maybe we should insert a PlaceHolderVar
2128                                  * anyway, if the tlist item is expensive to evaluate?
2129                                  *
2130                                  * For a LATERAL subquery, we have to check the actual var
2131                                  * membership of the node, but if it's non-lateral then any
2132                                  * level-zero var must belong to the subquery.
2133                                  */
2134                                 if ((rcon->target_rte->lateral ?
2135                                    bms_overlap(pull_varnos((Node *) newnode), rcon->relids) :
2136                                          contain_vars_of_level((Node *) newnode, 0)) &&
2137                                         !contain_nonstrict_functions((Node *) newnode))
2138                                 {
2139                                         /* No wrap needed */
2140                                         wrap = false;
2141                                 }
2142                                 else
2143                                 {
2144                                         /* Else wrap it in a PlaceHolderVar */
2145                                         wrap = true;
2146                                 }
2147                         }
2148
2149                         if (wrap)
2150                                 newnode = (Node *)
2151                                         make_placeholder_expr(rcon->root,
2152                                                                                   (Expr *) newnode,
2153                                                                                   bms_make_singleton(rcon->varno));
2154
2155                         /*
2156                          * Cache it if possible (ie, if the attno is in range, which it
2157                          * probably always should be).  We can cache the value even if we
2158                          * decided we didn't need a PHV, since this result will be
2159                          * suitable for any request that has need_phvs.
2160                          */
2161                         if (varattno > InvalidAttrNumber &&
2162                                 varattno <= list_length(rcon->targetlist))
2163                                 rcon->rv_cache[varattno] = copyObject(newnode);
2164                 }
2165         }
2166
2167         /* Must adjust varlevelsup if tlist item is from higher query */
2168         if (var->varlevelsup > 0)
2169                 IncrementVarSublevelsUp(newnode, var->varlevelsup, 0);
2170
2171         return newnode;
2172 }
2173
2174 /*
2175  * Apply pullup variable replacement to a subquery
2176  *
2177  * This needs to be different from pullup_replace_vars() because
2178  * replace_rte_variables will think that it shouldn't increment sublevels_up
2179  * before entering the Query; so we need to call it with sublevels_up == 1.
2180  */
2181 static Query *
2182 pullup_replace_vars_subquery(Query *query,
2183                                                          pullup_replace_vars_context *context)
2184 {
2185         Assert(IsA(query, Query));
2186         return (Query *) replace_rte_variables((Node *) query,
2187                                                                                    context->varno, 1,
2188                                                                                    pullup_replace_vars_callback,
2189                                                                                    (void *) context,
2190                                                                                    NULL);
2191 }
2192
2193 /*
2194  * pull_up_subqueries_cleanup
2195  *              Recursively fix up jointree after deletion of some subqueries.
2196  *
2197  * The jointree now contains some NULL subtrees, which we need to get rid of.
2198  * In a FromExpr, just rebuild the child-node list with null entries deleted.
2199  * In an inner JOIN, replace the JoinExpr node with a one-child FromExpr.
2200  */
2201 static Node *
2202 pull_up_subqueries_cleanup(Node *jtnode)
2203 {
2204         Assert(jtnode != NULL);
2205         if (IsA(jtnode, RangeTblRef))
2206         {
2207                 /* Nothing to do at leaf nodes. */
2208         }
2209         else if (IsA(jtnode, FromExpr))
2210         {
2211                 FromExpr   *f = (FromExpr *) jtnode;
2212                 List       *newfrom = NIL;
2213                 ListCell   *l;
2214
2215                 foreach(l, f->fromlist)
2216                 {
2217                         Node       *child = (Node *) lfirst(l);
2218
2219                         if (child == NULL)
2220                                 continue;
2221                         child = pull_up_subqueries_cleanup(child);
2222                         newfrom = lappend(newfrom, child);
2223                 }
2224                 f->fromlist = newfrom;
2225         }
2226         else if (IsA(jtnode, JoinExpr))
2227         {
2228                 JoinExpr   *j = (JoinExpr *) jtnode;
2229
2230                 if (j->larg)
2231                         j->larg = pull_up_subqueries_cleanup(j->larg);
2232                 if (j->rarg)
2233                         j->rarg = pull_up_subqueries_cleanup(j->rarg);
2234                 if (j->larg == NULL)
2235                 {
2236                         Assert(j->jointype == JOIN_INNER);
2237                         Assert(j->rarg != NULL);
2238                         return (Node *) makeFromExpr(list_make1(j->rarg), j->quals);
2239                 }
2240                 else if (j->rarg == NULL)
2241                 {
2242                         Assert(j->jointype == JOIN_INNER);
2243                         return (Node *) makeFromExpr(list_make1(j->larg), j->quals);
2244                 }
2245         }
2246         else
2247                 elog(ERROR, "unrecognized node type: %d",
2248                          (int) nodeTag(jtnode));
2249         return jtnode;
2250 }
2251
2252
2253 /*
2254  * flatten_simple_union_all
2255  *              Try to optimize top-level UNION ALL structure into an appendrel
2256  *
2257  * If a query's setOperations tree consists entirely of simple UNION ALL
2258  * operations, flatten it into an append relation, which we can process more
2259  * intelligently than the general setops case.  Otherwise, do nothing.
2260  *
2261  * In most cases, this can succeed only for a top-level query, because for a
2262  * subquery in FROM, the parent query's invocation of pull_up_subqueries would
2263  * already have flattened the UNION via pull_up_simple_union_all.  But there
2264  * are a few cases we can support here but not in that code path, for example
2265  * when the subquery also contains ORDER BY.
2266  */
2267 void
2268 flatten_simple_union_all(PlannerInfo *root)
2269 {
2270         Query      *parse = root->parse;
2271         SetOperationStmt *topop;
2272         Node       *leftmostjtnode;
2273         int                     leftmostRTI;
2274         RangeTblEntry *leftmostRTE;
2275         int                     childRTI;
2276         RangeTblEntry *childRTE;
2277         RangeTblRef *rtr;
2278
2279         /* Shouldn't be called unless query has setops */
2280         topop = (SetOperationStmt *) parse->setOperations;
2281         Assert(topop && IsA(topop, SetOperationStmt));
2282
2283         /* Can't optimize away a recursive UNION */
2284         if (root->hasRecursion)
2285                 return;
2286
2287         /*
2288          * Recursively check the tree of set operations.  If not all UNION ALL
2289          * with identical column types, punt.
2290          */
2291         if (!is_simple_union_all_recurse((Node *) topop, parse, topop->colTypes))
2292                 return;
2293
2294         /*
2295          * Locate the leftmost leaf query in the setops tree.  The upper query's
2296          * Vars all refer to this RTE (see transformSetOperationStmt).
2297          */
2298         leftmostjtnode = topop->larg;
2299         while (leftmostjtnode && IsA(leftmostjtnode, SetOperationStmt))
2300                 leftmostjtnode = ((SetOperationStmt *) leftmostjtnode)->larg;
2301         Assert(leftmostjtnode && IsA(leftmostjtnode, RangeTblRef));
2302         leftmostRTI = ((RangeTblRef *) leftmostjtnode)->rtindex;
2303         leftmostRTE = rt_fetch(leftmostRTI, parse->rtable);
2304         Assert(leftmostRTE->rtekind == RTE_SUBQUERY);
2305
2306         /*
2307          * Make a copy of the leftmost RTE and add it to the rtable.  This copy
2308          * will represent the leftmost leaf query in its capacity as a member of
2309          * the appendrel.  The original will represent the appendrel as a whole.
2310          * (We must do things this way because the upper query's Vars have to be
2311          * seen as referring to the whole appendrel.)
2312          */
2313         childRTE = copyObject(leftmostRTE);
2314         parse->rtable = lappend(parse->rtable, childRTE);
2315         childRTI = list_length(parse->rtable);
2316
2317         /* Modify the setops tree to reference the child copy */
2318         ((RangeTblRef *) leftmostjtnode)->rtindex = childRTI;
2319
2320         /* Modify the formerly-leftmost RTE to mark it as an appendrel parent */
2321         leftmostRTE->inh = true;
2322
2323         /*
2324          * Form a RangeTblRef for the appendrel, and insert it into FROM.  The top
2325          * Query of a setops tree should have had an empty FromClause initially.
2326          */
2327         rtr = makeNode(RangeTblRef);
2328         rtr->rtindex = leftmostRTI;
2329         Assert(parse->jointree->fromlist == NIL);
2330         parse->jointree->fromlist = list_make1(rtr);
2331
2332         /*
2333          * Now pretend the query has no setops.  We must do this before trying to
2334          * do subquery pullup, because of Assert in pull_up_simple_subquery.
2335          */
2336         parse->setOperations = NULL;
2337
2338         /*
2339          * Build AppendRelInfo information, and apply pull_up_subqueries to the
2340          * leaf queries of the UNION ALL.  (We must do that now because they
2341          * weren't previously referenced by the jointree, and so were missed by
2342          * the main invocation of pull_up_subqueries.)
2343          */
2344         pull_up_union_leaf_queries((Node *) topop, root, leftmostRTI, parse, 0);
2345 }
2346
2347
2348 /*
2349  * reduce_outer_joins
2350  *              Attempt to reduce outer joins to plain inner joins.
2351  *
2352  * The idea here is that given a query like
2353  *              SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
2354  * we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
2355  * is strict.  The strict operator will always return NULL, causing the outer
2356  * WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
2357  * columns.  Therefore, there's no need for the join to produce null-extended
2358  * rows in the first place --- which makes it a plain join not an outer join.
2359  * (This scenario may not be very likely in a query written out by hand, but
2360  * it's reasonably likely when pushing quals down into complex views.)
2361  *
2362  * More generally, an outer join can be reduced in strength if there is a
2363  * strict qual above it in the qual tree that constrains a Var from the
2364  * nullable side of the join to be non-null.  (For FULL joins this applies
2365  * to each side separately.)
2366  *
2367  * Another transformation we apply here is to recognize cases like
2368  *              SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.y IS NULL;
2369  * If the join clause is strict for b.y, then only null-extended rows could
2370  * pass the upper WHERE, and we can conclude that what the query is really
2371  * specifying is an anti-semijoin.  We change the join type from JOIN_LEFT
2372  * to JOIN_ANTI.  The IS NULL clause then becomes redundant, and must be
2373  * removed to prevent bogus selectivity calculations, but we leave it to
2374  * distribute_qual_to_rels to get rid of such clauses.
2375  *
2376  * Also, we get rid of JOIN_RIGHT cases by flipping them around to become
2377  * JOIN_LEFT.  This saves some code here and in some later planner routines,
2378  * but the main reason to do it is to not need to invent a JOIN_REVERSE_ANTI
2379  * join type.
2380  *
2381  * To ease recognition of strict qual clauses, we require this routine to be
2382  * run after expression preprocessing (i.e., qual canonicalization and JOIN
2383  * alias-var expansion).
2384  */
2385 void
2386 reduce_outer_joins(PlannerInfo *root)
2387 {
2388         reduce_outer_joins_state *state;
2389
2390         /*
2391          * To avoid doing strictness checks on more quals than necessary, we want
2392          * to stop descending the jointree as soon as there are no outer joins
2393          * below our current point.  This consideration forces a two-pass process.
2394          * The first pass gathers information about which base rels appear below
2395          * each side of each join clause, and about whether there are outer
2396          * join(s) below each side of each join clause. The second pass examines
2397          * qual clauses and changes join types as it descends the tree.
2398          */
2399         state = reduce_outer_joins_pass1((Node *) root->parse->jointree);
2400
2401         /* planner.c shouldn't have called me if no outer joins */
2402         if (state == NULL || !state->contains_outer)
2403                 elog(ERROR, "so where are the outer joins?");
2404
2405         reduce_outer_joins_pass2((Node *) root->parse->jointree,
2406                                                          state, root, NULL, NIL, NIL);
2407 }
2408
2409 /*
2410  * reduce_outer_joins_pass1 - phase 1 data collection
2411  *
2412  * Returns a state node describing the given jointree node.
2413  */
2414 static reduce_outer_joins_state *
2415 reduce_outer_joins_pass1(Node *jtnode)
2416 {
2417         reduce_outer_joins_state *result;
2418
2419         result = (reduce_outer_joins_state *)
2420                 palloc(sizeof(reduce_outer_joins_state));
2421         result->relids = NULL;
2422         result->contains_outer = false;
2423         result->sub_states = NIL;
2424
2425         if (jtnode == NULL)
2426                 return result;
2427         if (IsA(jtnode, RangeTblRef))
2428         {
2429                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
2430
2431                 result->relids = bms_make_singleton(varno);
2432         }
2433         else if (IsA(jtnode, FromExpr))
2434         {
2435                 FromExpr   *f = (FromExpr *) jtnode;
2436                 ListCell   *l;
2437
2438                 foreach(l, f->fromlist)
2439                 {
2440                         reduce_outer_joins_state *sub_state;
2441
2442                         sub_state = reduce_outer_joins_pass1(lfirst(l));
2443                         result->relids = bms_add_members(result->relids,
2444                                                                                          sub_state->relids);
2445                         result->contains_outer |= sub_state->contains_outer;
2446                         result->sub_states = lappend(result->sub_states, sub_state);
2447                 }
2448         }
2449         else if (IsA(jtnode, JoinExpr))
2450         {
2451                 JoinExpr   *j = (JoinExpr *) jtnode;
2452                 reduce_outer_joins_state *sub_state;
2453
2454                 /* join's own RT index is not wanted in result->relids */
2455                 if (IS_OUTER_JOIN(j->jointype))
2456                         result->contains_outer = true;
2457
2458                 sub_state = reduce_outer_joins_pass1(j->larg);
2459                 result->relids = bms_add_members(result->relids,
2460                                                                                  sub_state->relids);
2461                 result->contains_outer |= sub_state->contains_outer;
2462                 result->sub_states = lappend(result->sub_states, sub_state);
2463
2464                 sub_state = reduce_outer_joins_pass1(j->rarg);
2465                 result->relids = bms_add_members(result->relids,
2466                                                                                  sub_state->relids);
2467                 result->contains_outer |= sub_state->contains_outer;
2468                 result->sub_states = lappend(result->sub_states, sub_state);
2469         }
2470         else
2471                 elog(ERROR, "unrecognized node type: %d",
2472                          (int) nodeTag(jtnode));
2473         return result;
2474 }
2475
2476 /*
2477  * reduce_outer_joins_pass2 - phase 2 processing
2478  *
2479  *      jtnode: current jointree node
2480  *      state: state data collected by phase 1 for this node
2481  *      root: toplevel planner state
2482  *      nonnullable_rels: set of base relids forced non-null by upper quals
2483  *      nonnullable_vars: list of Vars forced non-null by upper quals
2484  *      forced_null_vars: list of Vars forced null by upper quals
2485  */
2486 static void
2487 reduce_outer_joins_pass2(Node *jtnode,
2488                                                  reduce_outer_joins_state *state,
2489                                                  PlannerInfo *root,
2490                                                  Relids nonnullable_rels,
2491                                                  List *nonnullable_vars,
2492                                                  List *forced_null_vars)
2493 {
2494         /*
2495          * pass 2 should never descend as far as an empty subnode or base rel,
2496          * because it's only called on subtrees marked as contains_outer.
2497          */
2498         if (jtnode == NULL)
2499                 elog(ERROR, "reached empty jointree");
2500         if (IsA(jtnode, RangeTblRef))
2501                 elog(ERROR, "reached base rel");
2502         else if (IsA(jtnode, FromExpr))
2503         {
2504                 FromExpr   *f = (FromExpr *) jtnode;
2505                 ListCell   *l;
2506                 ListCell   *s;
2507                 Relids          pass_nonnullable_rels;
2508                 List       *pass_nonnullable_vars;
2509                 List       *pass_forced_null_vars;
2510
2511                 /* Scan quals to see if we can add any constraints */
2512                 pass_nonnullable_rels = find_nonnullable_rels(f->quals);
2513                 pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels,
2514                                                                                                 nonnullable_rels);
2515                 /* NB: we rely on list_concat to not damage its second argument */
2516                 pass_nonnullable_vars = find_nonnullable_vars(f->quals);
2517                 pass_nonnullable_vars = list_concat(pass_nonnullable_vars,
2518                                                                                         nonnullable_vars);
2519                 pass_forced_null_vars = find_forced_null_vars(f->quals);
2520                 pass_forced_null_vars = list_concat(pass_forced_null_vars,
2521                                                                                         forced_null_vars);
2522                 /* And recurse --- but only into interesting subtrees */
2523                 Assert(list_length(f->fromlist) == list_length(state->sub_states));
2524                 forboth(l, f->fromlist, s, state->sub_states)
2525                 {
2526                         reduce_outer_joins_state *sub_state = lfirst(s);
2527
2528                         if (sub_state->contains_outer)
2529                                 reduce_outer_joins_pass2(lfirst(l), sub_state, root,
2530                                                                                  pass_nonnullable_rels,
2531                                                                                  pass_nonnullable_vars,
2532                                                                                  pass_forced_null_vars);
2533                 }
2534                 bms_free(pass_nonnullable_rels);
2535                 /* can't so easily clean up var lists, unfortunately */
2536         }
2537         else if (IsA(jtnode, JoinExpr))
2538         {
2539                 JoinExpr   *j = (JoinExpr *) jtnode;
2540                 int                     rtindex = j->rtindex;
2541                 JoinType        jointype = j->jointype;
2542                 reduce_outer_joins_state *left_state = linitial(state->sub_states);
2543                 reduce_outer_joins_state *right_state = lsecond(state->sub_states);
2544                 List       *local_nonnullable_vars = NIL;
2545                 bool            computed_local_nonnullable_vars = false;
2546
2547                 /* Can we simplify this join? */
2548                 switch (jointype)
2549                 {
2550                         case JOIN_INNER:
2551                                 break;
2552                         case JOIN_LEFT:
2553                                 if (bms_overlap(nonnullable_rels, right_state->relids))
2554                                         jointype = JOIN_INNER;
2555                                 break;
2556                         case JOIN_RIGHT:
2557                                 if (bms_overlap(nonnullable_rels, left_state->relids))
2558                                         jointype = JOIN_INNER;
2559                                 break;
2560                         case JOIN_FULL:
2561                                 if (bms_overlap(nonnullable_rels, left_state->relids))
2562                                 {
2563                                         if (bms_overlap(nonnullable_rels, right_state->relids))
2564                                                 jointype = JOIN_INNER;
2565                                         else
2566                                                 jointype = JOIN_LEFT;
2567                                 }
2568                                 else
2569                                 {
2570                                         if (bms_overlap(nonnullable_rels, right_state->relids))
2571                                                 jointype = JOIN_RIGHT;
2572                                 }
2573                                 break;
2574                         case JOIN_SEMI:
2575                         case JOIN_ANTI:
2576
2577                                 /*
2578                                  * These could only have been introduced by pull_up_sublinks,
2579                                  * so there's no way that upper quals could refer to their
2580                                  * righthand sides, and no point in checking.
2581                                  */
2582                                 break;
2583                         default:
2584                                 elog(ERROR, "unrecognized join type: %d",
2585                                          (int) jointype);
2586                                 break;
2587                 }
2588
2589                 /*
2590                  * Convert JOIN_RIGHT to JOIN_LEFT.  Note that in the case where we
2591                  * reduced JOIN_FULL to JOIN_RIGHT, this will mean the JoinExpr no
2592                  * longer matches the internal ordering of any CoalesceExpr's built to
2593                  * represent merged join variables.  We don't care about that at
2594                  * present, but be wary of it ...
2595                  */
2596                 if (jointype == JOIN_RIGHT)
2597                 {
2598                         Node       *tmparg;
2599
2600                         tmparg = j->larg;
2601                         j->larg = j->rarg;
2602                         j->rarg = tmparg;
2603                         jointype = JOIN_LEFT;
2604                         right_state = linitial(state->sub_states);
2605                         left_state = lsecond(state->sub_states);
2606                 }
2607
2608                 /*
2609                  * See if we can reduce JOIN_LEFT to JOIN_ANTI.  This is the case if
2610                  * the join's own quals are strict for any var that was forced null by
2611                  * higher qual levels.  NOTE: there are other ways that we could
2612                  * detect an anti-join, in particular if we were to check whether Vars
2613                  * coming from the RHS must be non-null because of table constraints.
2614                  * That seems complicated and expensive though (in particular, one
2615                  * would have to be wary of lower outer joins). For the moment this
2616                  * seems sufficient.
2617                  */
2618                 if (jointype == JOIN_LEFT)
2619                 {
2620                         List       *overlap;
2621
2622                         local_nonnullable_vars = find_nonnullable_vars(j->quals);
2623                         computed_local_nonnullable_vars = true;
2624
2625                         /*
2626                          * It's not sufficient to check whether local_nonnullable_vars and
2627                          * forced_null_vars overlap: we need to know if the overlap
2628                          * includes any RHS variables.
2629                          */
2630                         overlap = list_intersection(local_nonnullable_vars,
2631                                                                                 forced_null_vars);
2632                         if (overlap != NIL &&
2633                                 bms_overlap(pull_varnos((Node *) overlap),
2634                                                         right_state->relids))
2635                                 jointype = JOIN_ANTI;
2636                 }
2637
2638                 /* Apply the jointype change, if any, to both jointree node and RTE */
2639                 if (rtindex && jointype != j->jointype)
2640                 {
2641                         RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable);
2642
2643                         Assert(rte->rtekind == RTE_JOIN);
2644                         Assert(rte->jointype == j->jointype);
2645                         rte->jointype = jointype;
2646                 }
2647                 j->jointype = jointype;
2648
2649                 /* Only recurse if there's more to do below here */
2650                 if (left_state->contains_outer || right_state->contains_outer)
2651                 {
2652                         Relids          local_nonnullable_rels;
2653                         List       *local_forced_null_vars;
2654                         Relids          pass_nonnullable_rels;
2655                         List       *pass_nonnullable_vars;
2656                         List       *pass_forced_null_vars;
2657
2658                         /*
2659                          * If this join is (now) inner, we can add any constraints its
2660                          * quals provide to those we got from above.  But if it is outer,
2661                          * we can pass down the local constraints only into the nullable
2662                          * side, because an outer join never eliminates any rows from its
2663                          * non-nullable side.  Also, there is no point in passing upper
2664                          * constraints into the nullable side, since if there were any
2665                          * we'd have been able to reduce the join.  (In the case of upper
2666                          * forced-null constraints, we *must not* pass them into the
2667                          * nullable side --- they either applied here, or not.) The upshot
2668                          * is that we pass either the local or the upper constraints,
2669                          * never both, to the children of an outer join.
2670                          *
2671                          * Note that a SEMI join works like an inner join here: it's okay
2672                          * to pass down both local and upper constraints.  (There can't be
2673                          * any upper constraints affecting its inner side, but it's not
2674                          * worth having a separate code path to avoid passing them.)
2675                          *
2676                          * At a FULL join we just punt and pass nothing down --- is it
2677                          * possible to be smarter?
2678                          */
2679                         if (jointype != JOIN_FULL)
2680                         {
2681                                 local_nonnullable_rels = find_nonnullable_rels(j->quals);
2682                                 if (!computed_local_nonnullable_vars)
2683                                         local_nonnullable_vars = find_nonnullable_vars(j->quals);
2684                                 local_forced_null_vars = find_forced_null_vars(j->quals);
2685                                 if (jointype == JOIN_INNER || jointype == JOIN_SEMI)
2686                                 {
2687                                         /* OK to merge upper and local constraints */
2688                                         local_nonnullable_rels = bms_add_members(local_nonnullable_rels,
2689                                                                                                                    nonnullable_rels);
2690                                         local_nonnullable_vars = list_concat(local_nonnullable_vars,
2691                                                                                                                  nonnullable_vars);
2692                                         local_forced_null_vars = list_concat(local_forced_null_vars,
2693                                                                                                                  forced_null_vars);
2694                                 }
2695                         }
2696                         else
2697                         {
2698                                 /* no use in calculating these */
2699                                 local_nonnullable_rels = NULL;
2700                                 local_forced_null_vars = NIL;
2701                         }
2702
2703                         if (left_state->contains_outer)
2704                         {
2705                                 if (jointype == JOIN_INNER || jointype == JOIN_SEMI)
2706                                 {
2707                                         /* pass union of local and upper constraints */
2708                                         pass_nonnullable_rels = local_nonnullable_rels;
2709                                         pass_nonnullable_vars = local_nonnullable_vars;
2710                                         pass_forced_null_vars = local_forced_null_vars;
2711                                 }
2712                                 else if (jointype != JOIN_FULL) /* ie, LEFT or ANTI */
2713                                 {
2714                                         /* can't pass local constraints to non-nullable side */
2715                                         pass_nonnullable_rels = nonnullable_rels;
2716                                         pass_nonnullable_vars = nonnullable_vars;
2717                                         pass_forced_null_vars = forced_null_vars;
2718                                 }
2719                                 else
2720                                 {
2721                                         /* no constraints pass through JOIN_FULL */
2722                                         pass_nonnullable_rels = NULL;
2723                                         pass_nonnullable_vars = NIL;
2724                                         pass_forced_null_vars = NIL;
2725                                 }
2726                                 reduce_outer_joins_pass2(j->larg, left_state, root,
2727                                                                                  pass_nonnullable_rels,
2728                                                                                  pass_nonnullable_vars,
2729                                                                                  pass_forced_null_vars);
2730                         }
2731
2732                         if (right_state->contains_outer)
2733                         {
2734                                 if (jointype != JOIN_FULL)              /* ie, INNER/LEFT/SEMI/ANTI */
2735                                 {
2736                                         /* pass appropriate constraints, per comment above */
2737                                         pass_nonnullable_rels = local_nonnullable_rels;
2738                                         pass_nonnullable_vars = local_nonnullable_vars;
2739                                         pass_forced_null_vars = local_forced_null_vars;
2740                                 }
2741                                 else
2742                                 {
2743                                         /* no constraints pass through JOIN_FULL */
2744                                         pass_nonnullable_rels = NULL;
2745                                         pass_nonnullable_vars = NIL;
2746                                         pass_forced_null_vars = NIL;
2747                                 }
2748                                 reduce_outer_joins_pass2(j->rarg, right_state, root,
2749                                                                                  pass_nonnullable_rels,
2750                                                                                  pass_nonnullable_vars,
2751                                                                                  pass_forced_null_vars);
2752                         }
2753                         bms_free(local_nonnullable_rels);
2754                 }
2755         }
2756         else
2757                 elog(ERROR, "unrecognized node type: %d",
2758                          (int) nodeTag(jtnode));
2759 }
2760
2761 /*
2762  * substitute_multiple_relids - adjust node relid sets after pulling up
2763  * a subquery
2764  *
2765  * Find any PlaceHolderVar nodes in the given tree that reference the
2766  * pulled-up relid, and change them to reference the replacement relid(s).
2767  *
2768  * NOTE: although this has the form of a walker, we cheat and modify the
2769  * nodes in-place.  This should be OK since the tree was copied by
2770  * pullup_replace_vars earlier.  Avoid scribbling on the original values of
2771  * the bitmapsets, though, because expression_tree_mutator doesn't copy those.
2772  */
2773
2774 typedef struct
2775 {
2776         int                     varno;
2777         int                     sublevels_up;
2778         Relids          subrelids;
2779 } substitute_multiple_relids_context;
2780
2781 static bool
2782 substitute_multiple_relids_walker(Node *node,
2783                                                                   substitute_multiple_relids_context *context)
2784 {
2785         if (node == NULL)
2786                 return false;
2787         if (IsA(node, PlaceHolderVar))
2788         {
2789                 PlaceHolderVar *phv = (PlaceHolderVar *) node;
2790
2791                 if (phv->phlevelsup == context->sublevels_up &&
2792                         bms_is_member(context->varno, phv->phrels))
2793                 {
2794                         phv->phrels = bms_union(phv->phrels,
2795                                                                         context->subrelids);
2796                         phv->phrels = bms_del_member(phv->phrels,
2797                                                                                  context->varno);
2798                 }
2799                 /* fall through to examine children */
2800         }
2801         if (IsA(node, Query))
2802         {
2803                 /* Recurse into subselects */
2804                 bool            result;
2805
2806                 context->sublevels_up++;
2807                 result = query_tree_walker((Query *) node,
2808                                                                    substitute_multiple_relids_walker,
2809                                                                    (void *) context, 0);
2810                 context->sublevels_up--;
2811                 return result;
2812         }
2813         /* Shouldn't need to handle planner auxiliary nodes here */
2814         Assert(!IsA(node, SpecialJoinInfo));
2815         Assert(!IsA(node, LateralJoinInfo));
2816         Assert(!IsA(node, AppendRelInfo));
2817         Assert(!IsA(node, PlaceHolderInfo));
2818         Assert(!IsA(node, MinMaxAggInfo));
2819
2820         return expression_tree_walker(node, substitute_multiple_relids_walker,
2821                                                                   (void *) context);
2822 }
2823
2824 static void
2825 substitute_multiple_relids(Node *node, int varno, Relids subrelids)
2826 {
2827         substitute_multiple_relids_context context;
2828
2829         context.varno = varno;
2830         context.sublevels_up = 0;
2831         context.subrelids = subrelids;
2832
2833         /*
2834          * Must be prepared to start with a Query or a bare expression tree.
2835          */
2836         query_or_expression_tree_walker(node,
2837                                                                         substitute_multiple_relids_walker,
2838                                                                         (void *) &context,
2839                                                                         0);
2840 }
2841
2842 /*
2843  * fix_append_rel_relids: update RT-index fields of AppendRelInfo nodes
2844  *
2845  * When we pull up a subquery, any AppendRelInfo references to the subquery's
2846  * RT index have to be replaced by the substituted relid (and there had better
2847  * be only one).  We also need to apply substitute_multiple_relids to their
2848  * translated_vars lists, since those might contain PlaceHolderVars.
2849  *
2850  * We assume we may modify the AppendRelInfo nodes in-place.
2851  */
2852 static void
2853 fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
2854 {
2855         ListCell   *l;
2856         int                     subvarno = -1;
2857
2858         /*
2859          * We only want to extract the member relid once, but we mustn't fail
2860          * immediately if there are multiple members; it could be that none of the
2861          * AppendRelInfo nodes refer to it.  So compute it on first use. Note that
2862          * bms_singleton_member will complain if set is not singleton.
2863          */
2864         foreach(l, append_rel_list)
2865         {
2866                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
2867
2868                 /* The parent_relid shouldn't ever be a pullup target */
2869                 Assert(appinfo->parent_relid != varno);
2870
2871                 if (appinfo->child_relid == varno)
2872                 {
2873                         if (subvarno < 0)
2874                                 subvarno = bms_singleton_member(subrelids);
2875                         appinfo->child_relid = subvarno;
2876                 }
2877
2878                 /* Also finish fixups for its translated vars */
2879                 substitute_multiple_relids((Node *) appinfo->translated_vars,
2880                                                                    varno, subrelids);
2881         }
2882 }
2883
2884 /*
2885  * get_relids_in_jointree: get set of RT indexes present in a jointree
2886  *
2887  * If include_joins is true, join RT indexes are included; if false,
2888  * only base rels are included.
2889  */
2890 Relids
2891 get_relids_in_jointree(Node *jtnode, bool include_joins)
2892 {
2893         Relids          result = NULL;
2894
2895         if (jtnode == NULL)
2896                 return result;
2897         if (IsA(jtnode, RangeTblRef))
2898         {
2899                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
2900
2901                 result = bms_make_singleton(varno);
2902         }
2903         else if (IsA(jtnode, FromExpr))
2904         {
2905                 FromExpr   *f = (FromExpr *) jtnode;
2906                 ListCell   *l;
2907
2908                 foreach(l, f->fromlist)
2909                 {
2910                         result = bms_join(result,
2911                                                           get_relids_in_jointree(lfirst(l),
2912                                                                                                          include_joins));
2913                 }
2914         }
2915         else if (IsA(jtnode, JoinExpr))
2916         {
2917                 JoinExpr   *j = (JoinExpr *) jtnode;
2918
2919                 result = get_relids_in_jointree(j->larg, include_joins);
2920                 result = bms_join(result,
2921                                                   get_relids_in_jointree(j->rarg, include_joins));
2922                 if (include_joins && j->rtindex)
2923                         result = bms_add_member(result, j->rtindex);
2924         }
2925         else
2926                 elog(ERROR, "unrecognized node type: %d",
2927                          (int) nodeTag(jtnode));
2928         return result;
2929 }
2930
2931 /*
2932  * get_relids_for_join: get set of base RT indexes making up a join
2933  */
2934 Relids
2935 get_relids_for_join(PlannerInfo *root, int joinrelid)
2936 {
2937         Node       *jtnode;
2938
2939         jtnode = find_jointree_node_for_rel((Node *) root->parse->jointree,
2940                                                                                 joinrelid);
2941         if (!jtnode)
2942                 elog(ERROR, "could not find join node %d", joinrelid);
2943         return get_relids_in_jointree(jtnode, false);
2944 }
2945
2946 /*
2947  * find_jointree_node_for_rel: locate jointree node for a base or join RT index
2948  *
2949  * Returns NULL if not found
2950  */
2951 static Node *
2952 find_jointree_node_for_rel(Node *jtnode, int relid)
2953 {
2954         if (jtnode == NULL)
2955                 return NULL;
2956         if (IsA(jtnode, RangeTblRef))
2957         {
2958                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
2959
2960                 if (relid == varno)
2961                         return jtnode;
2962         }
2963         else if (IsA(jtnode, FromExpr))
2964         {
2965                 FromExpr   *f = (FromExpr *) jtnode;
2966                 ListCell   *l;
2967
2968                 foreach(l, f->fromlist)
2969                 {
2970                         jtnode = find_jointree_node_for_rel(lfirst(l), relid);
2971                         if (jtnode)
2972                                 return jtnode;
2973                 }
2974         }
2975         else if (IsA(jtnode, JoinExpr))
2976         {
2977                 JoinExpr   *j = (JoinExpr *) jtnode;
2978
2979                 if (relid == j->rtindex)
2980                         return jtnode;
2981                 jtnode = find_jointree_node_for_rel(j->larg, relid);
2982                 if (jtnode)
2983                         return jtnode;
2984                 jtnode = find_jointree_node_for_rel(j->rarg, relid);
2985                 if (jtnode)
2986                         return jtnode;
2987         }
2988         else
2989                 elog(ERROR, "unrecognized node type: %d",
2990                          (int) nodeTag(jtnode));
2991         return NULL;
2992 }