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  *              do expression preprocessing (including flattening JOIN alias vars)
  11  *              reduce_outer_joins
  12  *
  13  *
  14  * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
  15  * Portions Copyright (c) 1994, Regents of the University of California
  16  *
  17  *
  18  * IDENTIFICATION
  19  *        $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.70 2010/01/02 16:57:47 momjian Exp $
  20  *
  21  *-------------------------------------------------------------------------
  22  */
  23 #include "postgres.h"
  24
  25 #include "catalog/pg_type.h"
  26 #include "nodes/makefuncs.h"
  27 #include "nodes/nodeFuncs.h"
  28 #include "optimizer/clauses.h"
  29 #include "optimizer/placeholder.h"
  30 #include "optimizer/prep.h"
  31 #include "optimizer/subselect.h"
  32 #include "optimizer/tlist.h"
  33 #include "optimizer/var.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         bool       *outer_hasSubLinks;  /* -> outer query's hasSubLinks */
  45         int                     varno;                          /* varno of subquery */
  46         bool            need_phvs;                      /* do we need PlaceHolderVars? */
  47         bool            wrap_non_vars;          /* do we need 'em on *all* non-Vars? */
  48         Node      **rv_cache;                   /* cache for results with PHVs */
  49 } pullup_replace_vars_context;
  50
  51 typedef struct reduce_outer_joins_state
  52 {
  53         Relids          relids;                 /* base relids within this subtree */
  54         bool            contains_outer; /* does subtree contain outer join(s)? */
  55         List       *sub_states;         /* List of states for subtree components */
  56 } reduce_outer_joins_state;
  57
  58 static Node *pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
  59                                                                   Relids *relids);
  60 static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
  61                                                           Relids available_rels, Node **jtlink);
  62 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
  63                                                 RangeTblEntry *rte,
  64                                                 JoinExpr *lowest_outer_join,
  65                                                 AppendRelInfo *containing_appendrel);
  66 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
  67                                                  RangeTblEntry *rte);
  68 static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,
  69                                                    int parentRTindex, Query *setOpQuery,
  70                                                    int childRToffset);
  71 static void make_setop_translation_list(Query *query, Index newvarno,
  72                                                         List **translated_vars);
  73 static bool is_simple_subquery(Query *subquery);
  74 static bool is_simple_union_all(Query *subquery);
  75 static bool is_simple_union_all_recurse(Node *setOp, Query *setOpQuery,
  76                                                         List *colTypes);
  77 static bool is_safe_append_member(Query *subquery);
  78 static void replace_vars_in_jointree(Node *jtnode,
  79                                                  pullup_replace_vars_context *context,
  80                                                  JoinExpr *lowest_outer_join);
  81 static Node *pullup_replace_vars(Node *expr,
  82                                                                  pullup_replace_vars_context *context);
  83 static Node *pullup_replace_vars_callback(Var *var,
  84                                                          replace_rte_variables_context *context);
  85 static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
  86 static void reduce_outer_joins_pass2(Node *jtnode,
  87                                                  reduce_outer_joins_state *state,
  88                                                  PlannerInfo *root,
  89                                                  Relids nonnullable_rels,
  90                                                  List *nonnullable_vars,
  91                                                  List *forced_null_vars);
  92 static void substitute_multiple_relids(Node *node,
  93                                                    int varno, Relids subrelids);
  94 static void fix_append_rel_relids(List *append_rel_list, int varno,
  95                                           Relids subrelids);
  96 static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
  97
  98
  99 /*
 100  * pull_up_sublinks
 101  *              Attempt to pull up ANY and EXISTS SubLinks to be treated as
 102  *              semijoins or anti-semijoins.
 103  *
 104  * A clause "foo op ANY (sub-SELECT)" can be processed by pulling the
 105  * sub-SELECT up to become a rangetable entry and treating the implied
 106  * comparisons as quals of a semijoin.  However, this optimization *only*
 107  * works at the top level of WHERE or a JOIN/ON clause, because we cannot
 108  * distinguish whether the ANY ought to return FALSE or NULL in cases
 109  * involving NULL inputs.  Also, in an outer join's ON clause we can only
 110  * do this if the sublink is degenerate (ie, references only the nullable
 111  * side of the join).  In that case it is legal to push the semijoin
 112  * down into the nullable side of the join.  If the sublink references any
 113  * nonnullable-side variables then it would have to be evaluated as part
 114  * of the outer join, which makes things way too complicated.
 115  *
 116  * Under similar conditions, EXISTS and NOT EXISTS clauses can be handled
 117  * by pulling up the sub-SELECT and creating a semijoin or anti-semijoin.
 118  *
 119  * This routine searches for such clauses and does the necessary parsetree
 120  * transformations if any are found.
 121  *
 122  * This routine has to run before preprocess_expression(), so the quals
 123  * clauses are not yet reduced to implicit-AND format.  That means we need
 124  * to recursively search through explicit AND clauses, which are
 125  * probably only binary ANDs.  We stop as soon as we hit a non-AND item.
 126  */
 127 void
 128 pull_up_sublinks(PlannerInfo *root)
 129 {
 130         Node       *jtnode;
 131         Relids          relids;
 132
 133         /* Begin recursion through the jointree */
 134         jtnode = pull_up_sublinks_jointree_recurse(root,
 135                                                                                            (Node *) root->parse->jointree,
 136                                                                                            &relids);
 137
 138         /*
 139          * root->parse->jointree must always be a FromExpr, so insert a dummy one
 140          * if we got a bare RangeTblRef or JoinExpr out of the recursion.
 141          */
 142         if (IsA(jtnode, FromExpr))
 143                 root->parse->jointree = (FromExpr *) jtnode;
 144         else
 145                 root->parse->jointree = makeFromExpr(list_make1(jtnode), NULL);
 146 }
 147
 148 /*
 149  * Recurse through jointree nodes for pull_up_sublinks()
 150  *
 151  * In addition to returning the possibly-modified jointree node, we return
 152  * a relids set of the contained rels into *relids.
 153  */
 154 static Node *
 155 pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
 156                                                                   Relids *relids)
 157 {
 158         if (jtnode == NULL)
 159         {
 160                 *relids = NULL;
 161         }
 162         else if (IsA(jtnode, RangeTblRef))
 163         {
 164                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 165
 166                 *relids = bms_make_singleton(varno);
 167                 /* jtnode is returned unmodified */
 168         }
 169         else if (IsA(jtnode, FromExpr))
 170         {
 171                 FromExpr   *f = (FromExpr *) jtnode;
 172                 List       *newfromlist = NIL;
 173                 Relids          frelids = NULL;
 174                 FromExpr   *newf;
 175                 Node       *jtlink;
 176                 ListCell   *l;
 177
 178                 /* First, recurse to process children and collect their relids */
 179                 foreach(l, f->fromlist)
 180                 {
 181                         Node       *newchild;
 182                         Relids          childrelids;
 183
 184                         newchild = pull_up_sublinks_jointree_recurse(root,
 185                                                                                                                  lfirst(l),
 186                                                                                                                  &childrelids);
 187                         newfromlist = lappend(newfromlist, newchild);
 188                         frelids = bms_join(frelids, childrelids);
 189                 }
 190                 /* Build the replacement FromExpr; no quals yet */
 191                 newf = makeFromExpr(newfromlist, NULL);
 192                 /* Set up a link representing the rebuilt jointree */
 193                 jtlink = (Node *) newf;
 194                 /* Now process qual --- all children are available for use */
 195                 newf->quals = pull_up_sublinks_qual_recurse(root, f->quals, frelids,
 196                                                                                                         &jtlink);
 197
 198                 /*
 199                  * Note that the result will be either newf, or a stack of JoinExprs
 200                  * with newf at the base.  We rely on subsequent optimization steps to
 201                  * flatten this and rearrange the joins as needed.
 202                  *
 203                  * Although we could include the pulled-up subqueries in the returned
 204                  * relids, there's no need since upper quals couldn't refer to their
 205                  * outputs anyway.
 206                  */
 207                 *relids = frelids;
 208                 jtnode = jtlink;
 209         }
 210         else if (IsA(jtnode, JoinExpr))
 211         {
 212                 JoinExpr   *j;
 213                 Relids          leftrelids;
 214                 Relids          rightrelids;
 215                 Node       *jtlink;
 216
 217                 /*
 218                  * Make a modifiable copy of join node, but don't bother copying its
 219                  * subnodes (yet).
 220                  */
 221                 j = (JoinExpr *) palloc(sizeof(JoinExpr));
 222                 memcpy(j, jtnode, sizeof(JoinExpr));
 223                 jtlink = (Node *) j;
 224
 225                 /* Recurse to process children and collect their relids */
 226                 j->larg = pull_up_sublinks_jointree_recurse(root, j->larg,
 227                                                                                                         &leftrelids);
 228                 j->rarg = pull_up_sublinks_jointree_recurse(root, j->rarg,
 229                                                                                                         &rightrelids);
 230
 231                 /*
 232                  * Now process qual, showing appropriate child relids as available,
 233                  * and attach any pulled-up jointree items at the right place. In the
 234                  * inner-join case we put new JoinExprs above the existing one (much
 235                  * as for a FromExpr-style join).  In outer-join cases the new
 236                  * JoinExprs must go into the nullable side of the outer join. The
 237                  * point of the available_rels machinations is to ensure that we only
 238                  * pull up quals for which that's okay.
 239                  *
 240                  * XXX for the moment, we refrain from pulling up IN/EXISTS clauses
 241                  * appearing in LEFT or RIGHT join conditions.  Although it is
 242                  * semantically valid to do so under the above conditions, we end up
 243                  * with a query in which the semijoin or antijoin must be evaluated
 244                  * below the outer join, which could perform far worse than leaving it
 245                  * as a sublink that is executed only for row pairs that meet the
 246                  * other join conditions.  Fixing this seems to require considerable
 247                  * restructuring of the executor, but maybe someday it can happen.
 248                  *
 249                  * We don't expect to see any pre-existing JOIN_SEMI or JOIN_ANTI
 250                  * nodes here.
 251                  */
 252                 switch (j->jointype)
 253                 {
 254                         case JOIN_INNER:
 255                                 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
 256                                                                                                                  bms_union(leftrelids,
 257                                                                                                                                 rightrelids),
 258                                                                                                                  &jtlink);
 259                                 break;
 260                         case JOIN_LEFT:
 261 #ifdef NOT_USED                                 /* see XXX comment above */
 262                                 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
 263                                                                                                                  rightrelids,
 264                                                                                                                  &j->rarg);
 265 #endif
 266                                 break;
 267                         case JOIN_FULL:
 268                                 /* can't do anything with full-join quals */
 269                                 break;
 270                         case JOIN_RIGHT:
 271 #ifdef NOT_USED                                 /* see XXX comment above */
 272                                 j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
 273                                                                                                                  leftrelids,
 274                                                                                                                  &j->larg);
 275 #endif
 276                                 break;
 277                         default:
 278                                 elog(ERROR, "unrecognized join type: %d",
 279                                          (int) j->jointype);
 280                                 break;
 281                 }
 282
 283                 /*
 284                  * Although we could include the pulled-up subqueries in the returned
 285                  * relids, there's no need since upper quals couldn't refer to their
 286                  * outputs anyway.      But we *do* need to include the join's own rtindex
 287                  * because we haven't yet collapsed join alias variables, so upper
 288                  * levels would mistakenly think they couldn't use references to this
 289                  * join.
 290                  */
 291                 *relids = bms_join(leftrelids, rightrelids);
 292                 if (j->rtindex)
 293                         *relids = bms_add_member(*relids, j->rtindex);
 294                 jtnode = jtlink;
 295         }
 296         else
 297                 elog(ERROR, "unrecognized node type: %d",
 298                          (int) nodeTag(jtnode));
 299         return jtnode;
 300 }
 301
 302 /*
 303  * Recurse through top-level qual nodes for pull_up_sublinks()
 304  *
 305  * jtlink points to the link in the jointree where any new JoinExprs should be
 306  * inserted.  If we find multiple pull-up-able SubLinks, they'll get stacked
 307  * there in the order we encounter them.  We rely on subsequent optimization
 308  * to rearrange the stack if appropriate.
 309  */
 310 static Node *
 311 pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,
 312                                                           Relids available_rels, Node **jtlink)
 313 {
 314         if (node == NULL)
 315                 return NULL;
 316         if (IsA(node, SubLink))
 317         {
 318                 SubLink    *sublink = (SubLink *) node;
 319                 JoinExpr   *j;
 320
 321                 /* Is it a convertible ANY or EXISTS clause? */
 322                 if (sublink->subLinkType == ANY_SUBLINK)
 323                 {
 324                         j = convert_ANY_sublink_to_join(root, sublink,
 325                                                                                         available_rels);
 326                         if (j)
 327                         {
 328                                 /* Yes, insert the new join node into the join tree */
 329                                 j->larg = *jtlink;
 330                                 *jtlink = (Node *) j;
 331                                 /* and return NULL representing constant TRUE */
 332                                 return NULL;
 333                         }
 334                 }
 335                 else if (sublink->subLinkType == EXISTS_SUBLINK)
 336                 {
 337                         j = convert_EXISTS_sublink_to_join(root, sublink, false,
 338                                                                                            available_rels);
 339                         if (j)
 340                         {
 341                                 /* Yes, insert the new join node into the join tree */
 342                                 j->larg = *jtlink;
 343                                 *jtlink = (Node *) j;
 344                                 /* and return NULL representing constant TRUE */
 345                                 return NULL;
 346                         }
 347                 }
 348                 /* Else return it unmodified */
 349                 return node;
 350         }
 351         if (not_clause(node))
 352         {
 353                 /* If the immediate argument of NOT is EXISTS, try to convert */
 354                 SubLink    *sublink = (SubLink *) get_notclausearg((Expr *) node);
 355                 JoinExpr   *j;
 356
 357                 if (sublink && IsA(sublink, SubLink))
 358                 {
 359                         if (sublink->subLinkType == EXISTS_SUBLINK)
 360                         {
 361                                 j = convert_EXISTS_sublink_to_join(root, sublink, true,
 362                                                                                                    available_rels);
 363                                 if (j)
 364                                 {
 365                                         /* Yes, insert the new join node into the join tree */
 366                                         j->larg = *jtlink;
 367                                         *jtlink = (Node *) j;
 368                                         /* and return NULL representing constant TRUE */
 369                                         return NULL;
 370                                 }
 371                         }
 372                 }
 373                 /* Else return it unmodified */
 374                 return node;
 375         }
 376         if (and_clause(node))
 377         {
 378                 /* Recurse into AND clause */
 379                 List       *newclauses = NIL;
 380                 ListCell   *l;
 381
 382                 foreach(l, ((BoolExpr *) node)->args)
 383                 {
 384                         Node       *oldclause = (Node *) lfirst(l);
 385                         Node       *newclause;
 386
 387                         newclause = pull_up_sublinks_qual_recurse(root,
 388                                                                                                           oldclause,
 389                                                                                                           available_rels,
 390                                                                                                           jtlink);
 391                         if (newclause)
 392                                 newclauses = lappend(newclauses, newclause);
 393                 }
 394                 /* We might have got back fewer clauses than we started with */
 395                 if (newclauses == NIL)
 396                         return NULL;
 397                 else if (list_length(newclauses) == 1)
 398                         return (Node *) linitial(newclauses);
 399                 else
 400                         return (Node *) make_andclause(newclauses);
 401         }
 402         /* Stop if not an AND */
 403         return node;
 404 }
 405
 406 /*
 407  * inline_set_returning_functions
 408  *              Attempt to "inline" set-returning functions in the FROM clause.
 409  *
 410  * If an RTE_FUNCTION rtable entry invokes a set-returning function that
 411  * contains just a simple SELECT, we can convert the rtable entry to an
 412  * RTE_SUBQUERY entry exposing the SELECT directly.  This is especially
 413  * useful if the subquery can then be "pulled up" for further optimization,
 414  * but we do it even if not, to reduce executor overhead.
 415  *
 416  * This has to be done before we have started to do any optimization of
 417  * subqueries, else any such steps wouldn't get applied to subqueries
 418  * obtained via inlining.  However, we do it after pull_up_sublinks
 419  * so that we can inline any functions used in SubLink subselects.
 420  *
 421  * Like most of the planner, this feels free to scribble on its input data
 422  * structure.
 423  */
 424 void
 425 inline_set_returning_functions(PlannerInfo *root)
 426 {
 427         ListCell   *rt;
 428
 429         foreach(rt, root->parse->rtable)
 430         {
 431                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(rt);
 432
 433                 if (rte->rtekind == RTE_FUNCTION)
 434                 {
 435                         Query      *funcquery;
 436
 437                         /* Check safety of expansion, and expand if possible */
 438                         funcquery = inline_set_returning_function(root, rte);
 439                         if (funcquery)
 440                         {
 441                                 /* Successful expansion, replace the rtable entry */
 442                                 rte->rtekind = RTE_SUBQUERY;
 443                                 rte->subquery = funcquery;
 444                                 rte->funcexpr = NULL;
 445                                 rte->funccoltypes = NIL;
 446                                 rte->funccoltypmods = NIL;
 447                         }
 448                 }
 449         }
 450 }
 451
 452 /*
 453  * pull_up_subqueries
 454  *              Look for subqueries in the rangetable that can be pulled up into
 455  *              the parent query.  If the subquery has no special features like
 456  *              grouping/aggregation then we can merge it into the parent's jointree.
 457  *              Also, subqueries that are simple UNION ALL structures can be
 458  *              converted into "append relations".
 459  *
 460  * If this jointree node is within the nullable side of an outer join, then
 461  * lowest_outer_join references the lowest such JoinExpr node; otherwise it
 462  * is NULL.  This forces use of the PlaceHolderVar mechanism for references
 463  * to non-nullable targetlist items, but only for references above that join.
 464  *
 465  * If we are looking at a member subquery of an append relation,
 466  * containing_appendrel describes that relation; else it is NULL.
 467  * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist
 468  * items, and puts some additional restrictions on what can be pulled up.
 469  *
 470  * A tricky aspect of this code is that if we pull up a subquery we have
 471  * to replace Vars that reference the subquery's outputs throughout the
 472  * parent query, including quals attached to jointree nodes above the one
 473  * we are currently processing!  We handle this by being careful not to
 474  * change the jointree structure while recursing: no nodes other than
 475  * subquery RangeTblRef entries will be replaced.  Also, we can't turn
 476  * pullup_replace_vars loose on the whole jointree, because it'll return a
 477  * mutated copy of the tree; we have to invoke it just on the quals, instead.
 478  * This behavior is what makes it reasonable to pass lowest_outer_join as a
 479  * pointer rather than some more-indirect way of identifying the lowest OJ.
 480  * Likewise, we don't replace append_rel_list members but only their
 481  * substructure, so the containing_appendrel reference is safe to use.
 482  */
 483 Node *
 484 pull_up_subqueries(PlannerInfo *root, Node *jtnode,
 485                                    JoinExpr *lowest_outer_join,
 486                                    AppendRelInfo *containing_appendrel)
 487 {
 488         if (jtnode == NULL)
 489                 return NULL;
 490         if (IsA(jtnode, RangeTblRef))
 491         {
 492                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 493                 RangeTblEntry *rte = rt_fetch(varno, root->parse->rtable);
 494
 495                 /*
 496                  * Is this a subquery RTE, and if so, is the subquery simple enough to
 497                  * pull up?
 498                  *
 499                  * If we are looking at an append-relation member, we can't pull it up
 500                  * unless is_safe_append_member says so.
 501                  */
 502                 if (rte->rtekind == RTE_SUBQUERY &&
 503                         is_simple_subquery(rte->subquery) &&
 504                         (containing_appendrel == NULL ||
 505                          is_safe_append_member(rte->subquery)))
 506                         return pull_up_simple_subquery(root, jtnode, rte,
 507                                                                                    lowest_outer_join,
 508                                                                                    containing_appendrel);
 509
 510                 /*
 511                  * Alternatively, is it a simple UNION ALL subquery?  If so, flatten
 512                  * into an "append relation".
 513                  *
 514                  * It's safe to do this regardless of whether this query is itself an
 515                  * appendrel member.  (If you're thinking we should try to flatten the
 516                  * two levels of appendrel together, you're right; but we handle that
 517                  * in set_append_rel_pathlist, not here.)
 518                  */
 519                 if (rte->rtekind == RTE_SUBQUERY &&
 520                         is_simple_union_all(rte->subquery))
 521                         return pull_up_simple_union_all(root, jtnode, rte);
 522
 523                 /* Otherwise, do nothing at this node. */
 524         }
 525         else if (IsA(jtnode, FromExpr))
 526         {
 527                 FromExpr   *f = (FromExpr *) jtnode;
 528                 ListCell   *l;
 529
 530                 Assert(containing_appendrel == NULL);
 531                 foreach(l, f->fromlist)
 532                         lfirst(l) = pull_up_subqueries(root, lfirst(l),
 533                                                                                    lowest_outer_join, NULL);
 534         }
 535         else if (IsA(jtnode, JoinExpr))
 536         {
 537                 JoinExpr   *j = (JoinExpr *) jtnode;
 538
 539                 Assert(containing_appendrel == NULL);
 540                 /* Recurse, being careful to tell myself when inside outer join */
 541                 switch (j->jointype)
 542                 {
 543                         case JOIN_INNER:
 544                                 j->larg = pull_up_subqueries(root, j->larg,
 545                                                                                          lowest_outer_join, NULL);
 546                                 j->rarg = pull_up_subqueries(root, j->rarg,
 547                                                                                          lowest_outer_join, NULL);
 548                                 break;
 549                         case JOIN_LEFT:
 550                         case JOIN_SEMI:
 551                         case JOIN_ANTI:
 552                                 j->larg = pull_up_subqueries(root, j->larg,
 553                                                                                          lowest_outer_join, NULL);
 554                                 j->rarg = pull_up_subqueries(root, j->rarg,
 555                                                                                          j, NULL);
 556                                 break;
 557                         case JOIN_FULL:
 558                                 j->larg = pull_up_subqueries(root, j->larg,
 559                                                                                          j, NULL);
 560                                 j->rarg = pull_up_subqueries(root, j->rarg,
 561                                                                                          j, NULL);
 562                                 break;
 563                         case JOIN_RIGHT:
 564                                 j->larg = pull_up_subqueries(root, j->larg,
 565                                                                                          j, NULL);
 566                                 j->rarg = pull_up_subqueries(root, j->rarg,
 567                                                                                          lowest_outer_join, NULL);
 568                                 break;
 569                         default:
 570                                 elog(ERROR, "unrecognized join type: %d",
 571                                          (int) j->jointype);
 572                                 break;
 573                 }
 574         }
 575         else
 576                 elog(ERROR, "unrecognized node type: %d",
 577                          (int) nodeTag(jtnode));
 578         return jtnode;
 579 }
 580
 581 /*
 582  * pull_up_simple_subquery
 583  *              Attempt to pull up a single simple subquery.
 584  *
 585  * jtnode is a RangeTblRef that has been tentatively identified as a simple
 586  * subquery by pull_up_subqueries.      We return the replacement jointree node,
 587  * or jtnode itself if we determine that the subquery can't be pulled up after
 588  * all.
 589  *
 590  * rte is the RangeTblEntry referenced by jtnode.  Remaining parameters are
 591  * as for pull_up_subqueries.
 592  */
 593 static Node *
 594 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 595                                                 JoinExpr *lowest_outer_join,
 596                                                 AppendRelInfo *containing_appendrel)
 597 {
 598         Query      *parse = root->parse;
 599         int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 600         Query      *subquery;
 601         PlannerInfo *subroot;
 602         int                     rtoffset;
 603         pullup_replace_vars_context rvcontext;
 604         ListCell   *lc;
 605
 606         /*
 607          * Need a modifiable copy of the subquery to hack on.  Even if we didn't
 608          * sometimes choose not to pull up below, we must do this to avoid
 609          * problems if the same subquery is referenced from multiple jointree
 610          * items (which can't happen normally, but might after rule rewriting).
 611          */
 612         subquery = copyObject(rte->subquery);
 613
 614         /*
 615          * Create a PlannerInfo data structure for this subquery.
 616          *
 617          * NOTE: the next few steps should match the first processing in
 618          * subquery_planner().  Can we refactor to avoid code duplication, or
 619          * would that just make things uglier?
 620          */
 621         subroot = makeNode(PlannerInfo);
 622         subroot->parse = subquery;
 623         subroot->glob = root->glob;
 624         subroot->query_level = root->query_level;
 625         subroot->parent_root = root->parent_root;
 626         subroot->planner_cxt = CurrentMemoryContext;
 627         subroot->init_plans = NIL;
 628         subroot->cte_plan_ids = NIL;
 629         subroot->eq_classes = NIL;
 630         subroot->append_rel_list = NIL;
 631         subroot->rowMarks = NIL;
 632         subroot->hasRecursion = false;
 633         subroot->wt_param_id = -1;
 634         subroot->non_recursive_plan = NULL;
 635
 636         /* No CTEs to worry about */
 637         Assert(subquery->cteList == NIL);
 638
 639         /*
 640          * Pull up any SubLinks within the subquery's quals, so that we don't
 641          * leave unoptimized SubLinks behind.
 642          */
 643         if (subquery->hasSubLinks)
 644                 pull_up_sublinks(subroot);
 645
 646         /*
 647          * Similarly, inline any set-returning functions in its rangetable.
 648          */
 649         inline_set_returning_functions(subroot);
 650
 651         /*
 652          * Recursively pull up the subquery's subqueries, so that
 653          * pull_up_subqueries' processing is complete for its jointree and
 654          * rangetable.
 655          *
 656          * Note: we should pass NULL for containing-join info even if we are
 657          * within an outer join in the upper query; the lower query starts with a
 658          * clean slate for outer-join semantics.  Likewise, we say we aren't
 659          * handling an appendrel member.
 660          */
 661         subquery->jointree = (FromExpr *)
 662                 pull_up_subqueries(subroot, (Node *) subquery->jointree, NULL, NULL);
 663
 664         /*
 665          * Now we must recheck whether the subquery is still simple enough to pull
 666          * up.  If not, abandon processing it.
 667          *
 668          * We don't really need to recheck all the conditions involved, but it's
 669          * easier just to keep this "if" looking the same as the one in
 670          * pull_up_subqueries.
 671          */
 672         if (is_simple_subquery(subquery) &&
 673                 (containing_appendrel == NULL || is_safe_append_member(subquery)))
 674         {
 675                 /* good to go */
 676         }
 677         else
 678         {
 679                 /*
 680                  * Give up, return unmodified RangeTblRef.
 681                  *
 682                  * Note: The work we just did will be redone when the subquery gets
 683                  * planned on its own.  Perhaps we could avoid that by storing the
 684                  * modified subquery back into the rangetable, but I'm not gonna risk
 685                  * it now.
 686                  */
 687                 return jtnode;
 688         }
 689
 690         /*
 691          * Adjust level-0 varnos in subquery so that we can append its rangetable
 692          * to upper query's.  We have to fix the subquery's append_rel_list as
 693          * well.
 694          */
 695         rtoffset = list_length(parse->rtable);
 696         OffsetVarNodes((Node *) subquery, rtoffset, 0);
 697         OffsetVarNodes((Node *) subroot->append_rel_list, rtoffset, 0);
 698
 699         /*
 700          * Upper-level vars in subquery are now one level closer to their parent
 701          * than before.
 702          */
 703         IncrementVarSublevelsUp((Node *) subquery, -1, 1);
 704         IncrementVarSublevelsUp((Node *) subroot->append_rel_list, -1, 1);
 705
 706         /*
 707          * The subquery's targetlist items are now in the appropriate form to
 708          * insert into the top query, but if we are under an outer join then
 709          * non-nullable items may have to be turned into PlaceHolderVars.  If we
 710          * are dealing with an appendrel member then anything that's not a simple
 711          * Var has to be turned into a PlaceHolderVar.  Set up appropriate context
 712          * data for pullup_replace_vars.
 713          */
 714         rvcontext.root = root;
 715         rvcontext.targetlist = subquery->targetList;
 716         rvcontext.target_rte = rte;
 717         rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
 718         rvcontext.varno = varno;
 719         rvcontext.need_phvs = (lowest_outer_join != NULL ||
 720                                                    containing_appendrel != NULL);
 721         rvcontext.wrap_non_vars = (containing_appendrel != NULL);
 722         /* initialize cache array with indexes 0 .. length(tlist) */
 723         rvcontext.rv_cache = palloc0((list_length(subquery->targetList) + 1) *
 724                                                                  sizeof(Node *));
 725
 726         /*
 727          * Replace all of the top query's references to the subquery's outputs
 728          * with copies of the adjusted subtlist items, being careful not to
 729          * replace any of the jointree structure. (This'd be a lot cleaner if we
 730          * could use query_tree_mutator.)  We have to use PHVs in the targetList,
 731          * returningList, and havingQual, since those are certainly above any
 732          * outer join.  replace_vars_in_jointree tracks its location in the
 733          * jointree and uses PHVs or not appropriately.
 734          */
 735         parse->targetList = (List *)
 736                 pullup_replace_vars((Node *) parse->targetList, &rvcontext);
 737         parse->returningList = (List *)
 738                 pullup_replace_vars((Node *) parse->returningList, &rvcontext);
 739         replace_vars_in_jointree((Node *) parse->jointree, &rvcontext,
 740                                                          lowest_outer_join);
 741         Assert(parse->setOperations == NULL);
 742         parse->havingQual = pullup_replace_vars(parse->havingQual, &rvcontext);
 743
 744         /*
 745          * Replace references in the translated_vars lists of appendrels. When
 746          * pulling up an appendrel member, we do not need PHVs in the list of the
 747          * parent appendrel --- there isn't any outer join between. Elsewhere, use
 748          * PHVs for safety.  (This analysis could be made tighter but it seems
 749          * unlikely to be worth much trouble.)
 750          */
 751         foreach(lc, root->append_rel_list)
 752         {
 753                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
 754                 bool    save_need_phvs = rvcontext.need_phvs;
 755
 756                 if (appinfo == containing_appendrel)
 757                         rvcontext.need_phvs = false;
 758                 appinfo->translated_vars = (List *)
 759                         pullup_replace_vars((Node *) appinfo->translated_vars, &rvcontext);
 760                 rvcontext.need_phvs = save_need_phvs;
 761         }
 762
 763         /*
 764          * Replace references in the joinaliasvars lists of join RTEs.
 765          *
 766          * You might think that we could avoid using PHVs for alias vars of joins
 767          * below lowest_outer_join, but that doesn't work because the alias vars
 768          * could be referenced above that join; we need the PHVs to be present in
 769          * such references after the alias vars get flattened.  (It might be worth
 770          * trying to be smarter here, someday.)
 771          */
 772         foreach(lc, parse->rtable)
 773         {
 774                 RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(lc);
 775
 776                 if (otherrte->rtekind == RTE_JOIN)
 777                         otherrte->joinaliasvars = (List *)
 778                                 pullup_replace_vars((Node *) otherrte->joinaliasvars,
 779                                                                         &rvcontext);
 780         }
 781
 782         /*
 783          * Now append the adjusted rtable entries to upper query. (We hold off
 784          * until after fixing the upper rtable entries; no point in running that
 785          * code on the subquery ones too.)
 786          */
 787         parse->rtable = list_concat(parse->rtable, subquery->rtable);
 788
 789         /*
 790          * Pull up any FOR UPDATE/SHARE markers, too.  (OffsetVarNodes already
 791          * adjusted the marker rtindexes, so just concat the lists.)
 792          */
 793         parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);
 794
 795         /*
 796          * We also have to fix the relid sets of any PlaceHolderVar nodes in the
 797          * parent query.  (This could perhaps be done by pullup_replace_vars(),
 798          * but it seems cleaner to use two passes.)  Note in particular that any
 799          * PlaceHolderVar nodes just created by pullup_replace_vars()
 800          * will be adjusted, so having created them with the subquery's varno is
 801          * correct.
 802          *
 803          * Likewise, relids appearing in AppendRelInfo nodes have to be fixed. We
 804          * already checked that this won't require introducing multiple subrelids
 805          * into the single-slot AppendRelInfo structs.
 806          */
 807         if (parse->hasSubLinks || root->glob->lastPHId != 0 ||
 808                 root->append_rel_list)
 809         {
 810                 Relids          subrelids;
 811
 812                 subrelids = get_relids_in_jointree((Node *) subquery->jointree, false);
 813                 substitute_multiple_relids((Node *) parse, varno, subrelids);
 814                 fix_append_rel_relids(root->append_rel_list, varno, subrelids);
 815         }
 816
 817         /*
 818          * And now add subquery's AppendRelInfos to our list.
 819          */
 820         root->append_rel_list = list_concat(root->append_rel_list,
 821                                                                                 subroot->append_rel_list);
 822
 823         /*
 824          * We don't have to do the equivalent bookkeeping for outer-join info,
 825          * because that hasn't been set up yet.  placeholder_list likewise.
 826          */
 827         Assert(root->join_info_list == NIL);
 828         Assert(subroot->join_info_list == NIL);
 829         Assert(root->placeholder_list == NIL);
 830         Assert(subroot->placeholder_list == NIL);
 831
 832         /*
 833          * Miscellaneous housekeeping.
 834          *
 835          * Although replace_rte_variables() faithfully updated parse->hasSubLinks
 836          * if it copied any SubLinks out of the subquery's targetlist, we still
 837          * could have SubLinks added to the query in the expressions of FUNCTION
 838          * and VALUES RTEs copied up from the subquery.  So it's necessary to copy
 839          * subquery->hasSubLinks anyway.  Perhaps this can be improved someday.
 840          */
 841         parse->hasSubLinks |= subquery->hasSubLinks;
 842
 843         /*
 844          * subquery won't be pulled up if it hasAggs or hasWindowFuncs, so no work
 845          * needed on those flags
 846          */
 847
 848         /*
 849          * Return the adjusted subquery jointree to replace the RangeTblRef entry
 850          * in parent's jointree.
 851          */
 852         return (Node *) subquery->jointree;
 853 }
 854
 855 /*
 856  * pull_up_simple_union_all
 857  *              Pull up a single simple UNION ALL subquery.
 858  *
 859  * jtnode is a RangeTblRef that has been identified as a simple UNION ALL
 860  * subquery by pull_up_subqueries.      We pull up the leaf subqueries and
 861  * build an "append relation" for the union set.  The result value is just
 862  * jtnode, since we don't actually need to change the query jointree.
 863  */
 864 static Node *
 865 pull_up_simple_union_all(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
 866 {
 867         int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 868         Query      *subquery = rte->subquery;
 869         int                     rtoffset;
 870         List       *rtable;
 871
 872         /*
 873          * Append the subquery rtable entries to upper query.
 874          */
 875         rtoffset = list_length(root->parse->rtable);
 876
 877         /*
 878          * Append child RTEs to parent rtable.
 879          *
 880          * Upper-level vars in subquery are now one level closer to their parent
 881          * than before.  We don't have to worry about offsetting varnos, though,
 882          * because any such vars must refer to stuff above the level of the query
 883          * we are pulling into.
 884          */
 885         rtable = copyObject(subquery->rtable);
 886         IncrementVarSublevelsUp_rtable(rtable, -1, 1);
 887         root->parse->rtable = list_concat(root->parse->rtable, rtable);
 888
 889         /*
 890          * Recursively scan the subquery's setOperations tree and add
 891          * AppendRelInfo nodes for leaf subqueries to the parent's
 892          * append_rel_list.
 893          */
 894         Assert(subquery->setOperations);
 895         pull_up_union_leaf_queries(subquery->setOperations, root, varno, subquery,
 896                                                            rtoffset);
 897
 898         /*
 899          * Mark the parent as an append relation.
 900          */
 901         rte->inh = true;
 902
 903         return jtnode;
 904 }
 905
 906 /*
 907  * pull_up_union_leaf_queries -- recursive guts of pull_up_simple_union_all
 908  *
 909  * Note that setOpQuery is the Query containing the setOp node, whose rtable
 910  * is where to look up the RTE if setOp is a RangeTblRef.  This is *not* the
 911  * same as root->parse, which is the top-level Query we are pulling up into.
 912  *
 913  * parentRTindex is the appendrel parent's index in root->parse->rtable.
 914  *
 915  * The child RTEs have already been copied to the parent. childRToffset
 916  * tells us where in the parent's range table they were copied.
 917  */
 918 static void
 919 pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
 920                                                    Query *setOpQuery, int childRToffset)
 921 {
 922         if (IsA(setOp, RangeTblRef))
 923         {
 924                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 925                 int                     childRTindex;
 926                 AppendRelInfo *appinfo;
 927
 928                 /*
 929                  * Calculate the index in the parent's range table
 930                  */
 931                 childRTindex = childRToffset + rtr->rtindex;
 932
 933                 /*
 934                  * Build a suitable AppendRelInfo, and attach to parent's list.
 935                  */
 936                 appinfo = makeNode(AppendRelInfo);
 937                 appinfo->parent_relid = parentRTindex;
 938                 appinfo->child_relid = childRTindex;
 939                 appinfo->parent_reltype = InvalidOid;
 940                 appinfo->child_reltype = InvalidOid;
 941                 make_setop_translation_list(setOpQuery, childRTindex,
 942                                                                         &appinfo->translated_vars);
 943                 appinfo->parent_reloid = InvalidOid;
 944                 root->append_rel_list = lappend(root->append_rel_list, appinfo);
 945
 946                 /*
 947                  * Recursively apply pull_up_subqueries to the new child RTE.  (We
 948                  * must build the AppendRelInfo first, because this will modify it.)
 949                  * Note that we can pass NULL for containing-join info even if we're
 950                  * actually under an outer join, because the child's expressions
 951                  * aren't going to propagate up above the join.
 952                  */
 953                 rtr = makeNode(RangeTblRef);
 954                 rtr->rtindex = childRTindex;
 955                 (void) pull_up_subqueries(root, (Node *) rtr, NULL, appinfo);
 956         }
 957         else if (IsA(setOp, SetOperationStmt))
 958         {
 959                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 960
 961                 /* Recurse to reach leaf queries */
 962                 pull_up_union_leaf_queries(op->larg, root, parentRTindex, setOpQuery,
 963                                                                    childRToffset);
 964                 pull_up_union_leaf_queries(op->rarg, root, parentRTindex, setOpQuery,
 965                                                                    childRToffset);
 966         }
 967         else
 968         {
 969                 elog(ERROR, "unrecognized node type: %d",
 970                          (int) nodeTag(setOp));
 971         }
 972 }
 973
 974 /*
 975  * make_setop_translation_list
 976  *        Build the list of translations from parent Vars to child Vars for
 977  *        a UNION ALL member.  (At this point it's just a simple list of
 978  *        referencing Vars, but if we succeed in pulling up the member
 979  *        subquery, the Vars will get replaced by pulled-up expressions.)
 980  */
 981 static void
 982 make_setop_translation_list(Query *query, Index newvarno,
 983                                                         List **translated_vars)
 984 {
 985         List       *vars = NIL;
 986         ListCell   *l;
 987
 988         foreach(l, query->targetList)
 989         {
 990                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 991
 992                 if (tle->resjunk)
 993                         continue;
 994
 995                 vars = lappend(vars, makeVar(newvarno,
 996                                                                          tle->resno,
 997                                                                          exprType((Node *) tle->expr),
 998                                                                          exprTypmod((Node *) tle->expr),
 999                                                                          0));
1000         }
1001
1002         *translated_vars = vars;
1003 }
1004
1005 /*
1006  * is_simple_subquery
1007  *        Check a subquery in the range table to see if it's simple enough
1008  *        to pull up into the parent query.
1009  */
1010 static bool
1011 is_simple_subquery(Query *subquery)
1012 {
1013         /*
1014          * Let's just make sure it's a valid subselect ...
1015          */
1016         if (!IsA(subquery, Query) ||
1017                 subquery->commandType != CMD_SELECT ||
1018                 subquery->utilityStmt != NULL ||
1019                 subquery->intoClause != NULL)
1020                 elog(ERROR, "subquery is bogus");
1021
1022         /*
1023          * Can't currently pull up a query with setops (unless it's simple UNION
1024          * ALL, which is handled by a different code path). Maybe after querytree
1025          * redesign...
1026          */
1027         if (subquery->setOperations)
1028                 return false;
1029
1030         /*
1031          * Can't pull up a subquery involving grouping, aggregation, sorting,
1032          * limiting, or WITH.  (XXX WITH could possibly be allowed later)
1033          *
1034          * We also don't pull up a subquery that has explicit FOR UPDATE/SHARE
1035          * clauses, because pullup would cause the locking to occur semantically
1036          * higher than it should.  Implicit FOR UPDATE/SHARE is okay because
1037          * in that case the locking was originally declared in the upper query
1038          * anyway.
1039          */
1040         if (subquery->hasAggs ||
1041                 subquery->hasWindowFuncs ||
1042                 subquery->groupClause ||
1043                 subquery->havingQual ||
1044                 subquery->sortClause ||
1045                 subquery->distinctClause ||
1046                 subquery->limitOffset ||
1047                 subquery->limitCount ||
1048                 subquery->hasForUpdate ||
1049                 subquery->cteList)
1050                 return false;
1051
1052         /*
1053          * Don't pull up a subquery that has any set-returning functions in its
1054          * targetlist.  Otherwise we might well wind up inserting set-returning
1055          * functions into places where they mustn't go, such as quals of higher
1056          * queries.
1057          */
1058         if (expression_returns_set((Node *) subquery->targetList))
1059                 return false;
1060
1061         /*
1062          * Don't pull up a subquery that has any volatile functions in its
1063          * targetlist.  Otherwise we might introduce multiple evaluations of these
1064          * functions, if they get copied to multiple places in the upper query,
1065          * leading to surprising results.  (Note: the PlaceHolderVar mechanism
1066          * doesn't quite guarantee single evaluation; else we could pull up anyway
1067          * and just wrap such items in PlaceHolderVars ...)
1068          */
1069         if (contain_volatile_functions((Node *) subquery->targetList))
1070                 return false;
1071
1072         /*
1073          * Hack: don't try to pull up a subquery with an empty jointree.
1074          * query_planner() will correctly generate a Result plan for a jointree
1075          * that's totally empty, but I don't think the right things happen if an
1076          * empty FromExpr appears lower down in a jointree.  It would pose a
1077          * problem for the PlaceHolderVar mechanism too, since we'd have no way to
1078          * identify where to evaluate a PHV coming out of the subquery. Not worth
1079          * working hard on this, just to collapse SubqueryScan/Result into Result;
1080          * especially since the SubqueryScan can often be optimized away by
1081          * setrefs.c anyway.
1082          */
1083         if (subquery->jointree->fromlist == NIL)
1084                 return false;
1085
1086         return true;
1087 }
1088
1089 /*
1090  * is_simple_union_all
1091  *        Check a subquery to see if it's a simple UNION ALL.
1092  *
1093  * We require all the setops to be UNION ALL (no mixing) and there can't be
1094  * any datatype coercions involved, ie, all the leaf queries must emit the
1095  * same datatypes.
1096  */
1097 static bool
1098 is_simple_union_all(Query *subquery)
1099 {
1100         SetOperationStmt *topop;
1101
1102         /* Let's just make sure it's a valid subselect ... */
1103         if (!IsA(subquery, Query) ||
1104                 subquery->commandType != CMD_SELECT ||
1105                 subquery->utilityStmt != NULL ||
1106                 subquery->intoClause != NULL)
1107                 elog(ERROR, "subquery is bogus");
1108
1109         /* Is it a set-operation query at all? */
1110         topop = (SetOperationStmt *) subquery->setOperations;
1111         if (!topop)
1112                 return false;
1113         Assert(IsA(topop, SetOperationStmt));
1114
1115         /* Can't handle ORDER BY, LIMIT/OFFSET, locking, or WITH */
1116         if (subquery->sortClause ||
1117                 subquery->limitOffset ||
1118                 subquery->limitCount ||
1119                 subquery->rowMarks ||
1120                 subquery->cteList)
1121                 return false;
1122
1123         /* Recursively check the tree of set operations */
1124         return is_simple_union_all_recurse((Node *) topop, subquery,
1125                                                                            topop->colTypes);
1126 }
1127
1128 static bool
1129 is_simple_union_all_recurse(Node *setOp, Query *setOpQuery, List *colTypes)
1130 {
1131         if (IsA(setOp, RangeTblRef))
1132         {
1133                 RangeTblRef *rtr = (RangeTblRef *) setOp;
1134                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, setOpQuery->rtable);
1135                 Query      *subquery = rte->subquery;
1136
1137                 Assert(subquery != NULL);
1138
1139                 /* Leaf nodes are OK if they match the toplevel column types */
1140                 /* We don't have to compare typmods here */
1141                 return tlist_same_datatypes(subquery->targetList, colTypes, true);
1142         }
1143         else if (IsA(setOp, SetOperationStmt))
1144         {
1145                 SetOperationStmt *op = (SetOperationStmt *) setOp;
1146
1147                 /* Must be UNION ALL */
1148                 if (op->op != SETOP_UNION || !op->all)
1149                         return false;
1150
1151                 /* Recurse to check inputs */
1152                 return is_simple_union_all_recurse(op->larg, setOpQuery, colTypes) &&
1153                         is_simple_union_all_recurse(op->rarg, setOpQuery, colTypes);
1154         }
1155         else
1156         {
1157                 elog(ERROR, "unrecognized node type: %d",
1158                          (int) nodeTag(setOp));
1159                 return false;                   /* keep compiler quiet */
1160         }
1161 }
1162
1163 /*
1164  * is_safe_append_member
1165  *        Check a subquery that is a leaf of a UNION ALL appendrel to see if it's
1166  *        safe to pull up.
1167  */
1168 static bool
1169 is_safe_append_member(Query *subquery)
1170 {
1171         FromExpr   *jtnode;
1172
1173         /*
1174          * It's only safe to pull up the child if its jointree contains exactly
1175          * one RTE, else the AppendRelInfo data structure breaks. The one base RTE
1176          * could be buried in several levels of FromExpr, however.
1177          *
1178          * Also, the child can't have any WHERE quals because there's no place to
1179          * put them in an appendrel.  (This is a bit annoying...) If we didn't
1180          * need to check this, we'd just test whether get_relids_in_jointree()
1181          * yields a singleton set, to be more consistent with the coding of
1182          * fix_append_rel_relids().
1183          */
1184         jtnode = subquery->jointree;
1185         while (IsA(jtnode, FromExpr))
1186         {
1187                 if (jtnode->quals != NULL)
1188                         return false;
1189                 if (list_length(jtnode->fromlist) != 1)
1190                         return false;
1191                 jtnode = linitial(jtnode->fromlist);
1192         }
1193         if (!IsA(jtnode, RangeTblRef))
1194                 return false;
1195
1196         return true;
1197 }
1198
1199 /*
1200  * Helper routine for pull_up_subqueries: do pullup_replace_vars on every
1201  * expression in the jointree, without changing the jointree structure itself.
1202  * Ugly, but there's no other way...
1203  *
1204  * If we are at or below lowest_outer_join, we can suppress use of
1205  * PlaceHolderVars wrapped around the replacement expressions.
1206  */
1207 static void
1208 replace_vars_in_jointree(Node *jtnode,
1209                                                  pullup_replace_vars_context *context,
1210                                                  JoinExpr *lowest_outer_join)
1211 {
1212         if (jtnode == NULL)
1213                 return;
1214         if (IsA(jtnode, RangeTblRef))
1215         {
1216                 /* nothing to do here */
1217         }
1218         else if (IsA(jtnode, FromExpr))
1219         {
1220                 FromExpr   *f = (FromExpr *) jtnode;
1221                 ListCell   *l;
1222
1223                 foreach(l, f->fromlist)
1224                         replace_vars_in_jointree(lfirst(l), context, lowest_outer_join);
1225                 f->quals = pullup_replace_vars(f->quals, context);
1226         }
1227         else if (IsA(jtnode, JoinExpr))
1228         {
1229                 JoinExpr   *j = (JoinExpr *) jtnode;
1230                 bool    save_need_phvs = context->need_phvs;
1231
1232                 if (j == lowest_outer_join)
1233                 {
1234                         /* no more PHVs in or below this join */
1235                         context->need_phvs = false;
1236                         lowest_outer_join = NULL;
1237                 }
1238                 replace_vars_in_jointree(j->larg, context, lowest_outer_join);
1239                 replace_vars_in_jointree(j->rarg, context, lowest_outer_join);
1240                 j->quals = pullup_replace_vars(j->quals, context);
1241
1242                 /*
1243                  * We don't bother to update the colvars list, since it won't be used
1244                  * again ...
1245                  */
1246                 context->need_phvs = save_need_phvs;
1247         }
1248         else
1249                 elog(ERROR, "unrecognized node type: %d",
1250                          (int) nodeTag(jtnode));
1251 }
1252
1253 /*
1254  * Apply pullup variable replacement throughout an expression tree
1255  *
1256  * Returns a modified copy of the tree, so this can't be used where we
1257  * need to do in-place replacement.
1258  */
1259 static Node *
1260 pullup_replace_vars(Node *expr, pullup_replace_vars_context *context)
1261 {
1262         return replace_rte_variables(expr,
1263                                                                  context->varno, 0,
1264                                                                  pullup_replace_vars_callback,
1265                                                                  (void *) context,
1266                                                                  context->outer_hasSubLinks);
1267 }
1268
1269 static Node *
1270 pullup_replace_vars_callback(Var *var,
1271                                                          replace_rte_variables_context *context)
1272 {
1273         pullup_replace_vars_context *rcon = (pullup_replace_vars_context *) context->callback_arg;
1274         int                     varattno = var->varattno;
1275         Node       *newnode;
1276
1277         /*
1278          * If PlaceHolderVars are needed, we cache the modified expressions in
1279          * rcon->rv_cache[].  This is not in hopes of any material speed gain
1280          * within this function, but to avoid generating identical PHVs with
1281          * different IDs.  That would result in duplicate evaluations at runtime,
1282          * and possibly prevent optimizations that rely on recognizing different
1283          * references to the same subquery output as being equal().  So it's worth
1284          * a bit of extra effort to avoid it.
1285          */
1286         if (rcon->need_phvs &&
1287                 varattno >= InvalidAttrNumber &&
1288                 varattno <= list_length(rcon->targetlist) &&
1289                 rcon->rv_cache[varattno] != NULL)
1290         {
1291                 /* Just copy the entry and fall through to adjust its varlevelsup */
1292                 newnode = copyObject(rcon->rv_cache[varattno]);
1293         }
1294         else if (varattno == InvalidAttrNumber)
1295         {
1296                 /* Must expand whole-tuple reference into RowExpr */
1297                 RowExpr    *rowexpr;
1298                 List       *colnames;
1299                 List       *fields;
1300                 bool            save_need_phvs = rcon->need_phvs;
1301
1302                 /*
1303                  * If generating an expansion for a var of a named rowtype (ie, this
1304                  * is a plain relation RTE), then we must include dummy items for
1305                  * dropped columns.  If the var is RECORD (ie, this is a JOIN), then
1306                  * omit dropped columns. Either way, attach column names to the
1307                  * RowExpr for use of ruleutils.c.
1308                  *
1309                  * In order to be able to cache the results, we always generate the
1310                  * expansion with varlevelsup = 0, and then adjust if needed.
1311                  */
1312                 expandRTE(rcon->target_rte,
1313                                   var->varno, 0 /* not varlevelsup */, var->location,
1314                                   (var->vartype != RECORDOID),
1315                                   &colnames, &fields);
1316                 /* Adjust the generated per-field Vars, but don't insert PHVs */
1317                 rcon->need_phvs = false;
1318                 fields = (List *) replace_rte_variables_mutator((Node *) fields,
1319                                                                                                                 context);
1320                 rcon->need_phvs = save_need_phvs;
1321                 rowexpr = makeNode(RowExpr);
1322                 rowexpr->args = fields;
1323                 rowexpr->row_typeid = var->vartype;
1324                 rowexpr->row_format = COERCE_IMPLICIT_CAST;
1325                 rowexpr->colnames = colnames;
1326                 rowexpr->location = var->location;
1327                 newnode = (Node *) rowexpr;
1328
1329                 /*
1330                  * Insert PlaceHolderVar if needed.  Notice that we are wrapping
1331                  * one PlaceHolderVar around the whole RowExpr, rather than putting
1332                  * one around each element of the row.  This is because we need
1333                  * the expression to yield NULL, not ROW(NULL,NULL,...) when it
1334                  * is forced to null by an outer join.
1335                  */
1336                 if (rcon->need_phvs)
1337                 {
1338                         /* RowExpr is certainly not strict, so always need PHV */
1339                         newnode = (Node *)
1340                                 make_placeholder_expr(rcon->root,
1341                                                                           (Expr *) newnode,
1342                                                                           bms_make_singleton(rcon->varno));
1343                         /* cache it with the PHV, and with varlevelsup still zero */
1344                         rcon->rv_cache[InvalidAttrNumber] = copyObject(newnode);
1345                 }
1346         }
1347         else
1348         {
1349                 /* Normal case referencing one targetlist element */
1350                 TargetEntry *tle = get_tle_by_resno(rcon->targetlist, varattno);
1351
1352                 if (tle == NULL)                /* shouldn't happen */
1353                         elog(ERROR, "could not find attribute %d in subquery targetlist",
1354                                  varattno);
1355
1356                 /* Make a copy of the tlist item to return */
1357                 newnode = copyObject(tle->expr);
1358
1359                 /* Insert PlaceHolderVar if needed */
1360                 if (rcon->need_phvs)
1361                 {
1362                         bool    wrap;
1363
1364                         if (newnode && IsA(newnode, Var) &&
1365                                 ((Var *) newnode)->varlevelsup == 0)
1366                         {
1367                                 /* Simple Vars always escape being wrapped */
1368                                 wrap = false;
1369                         }
1370                         else if (rcon->wrap_non_vars)
1371                         {
1372                                 /* Wrap all non-Vars in a PlaceHolderVar */
1373                                 wrap = true;
1374                         }
1375                         else
1376                         {
1377                                 /*
1378                                  * If it contains a Var of current level, and does not contain
1379                                  * any non-strict constructs, then it's certainly nullable and
1380                                  * we don't need to insert a PlaceHolderVar.  (Note: in future
1381                                  * maybe we should insert PlaceHolderVars anyway, when a tlist
1382                                  * item is expensive to evaluate?
1383                                  */
1384                                 if (contain_vars_of_level((Node *) newnode, 0) &&
1385                                         !contain_nonstrict_functions((Node *) newnode))
1386                                 {
1387                                         /* No wrap needed */
1388                                         wrap = false;
1389                                 }
1390                                 else
1391                                 {
1392                                         /* Else wrap it in a PlaceHolderVar */
1393                                         wrap = true;
1394                                 }
1395                         }
1396
1397                         if (wrap)
1398                                 newnode = (Node *)
1399                                         make_placeholder_expr(rcon->root,
1400                                                                                   (Expr *) newnode,
1401                                                                                   bms_make_singleton(rcon->varno));
1402
1403                         /*
1404                          * Cache it if possible (ie, if the attno is in range, which it
1405                          * probably always should be).  We can cache the value even if
1406                          * we decided we didn't need a PHV, since this result will be
1407                          * suitable for any request that has need_phvs.
1408                          */
1409                         if (varattno > InvalidAttrNumber &&
1410                                 varattno <= list_length(rcon->targetlist))
1411                                 rcon->rv_cache[varattno] = copyObject(newnode);
1412                 }
1413         }
1414
1415         /* Must adjust varlevelsup if tlist item is from higher query */
1416         if (var->varlevelsup > 0)
1417                 IncrementVarSublevelsUp(newnode, var->varlevelsup, 0);
1418
1419         return newnode;
1420 }
1421
1422 /*
1423  * reduce_outer_joins
1424  *              Attempt to reduce outer joins to plain inner joins.
1425  *
1426  * The idea here is that given a query like
1427  *              SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
1428  * we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
1429  * is strict.  The strict operator will always return NULL, causing the outer
1430  * WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
1431  * columns.  Therefore, there's no need for the join to produce null-extended
1432  * rows in the first place --- which makes it a plain join not an outer join.
1433  * (This scenario may not be very likely in a query written out by hand, but
1434  * it's reasonably likely when pushing quals down into complex views.)
1435  *
1436  * More generally, an outer join can be reduced in strength if there is a
1437  * strict qual above it in the qual tree that constrains a Var from the
1438  * nullable side of the join to be non-null.  (For FULL joins this applies
1439  * to each side separately.)
1440  *
1441  * Another transformation we apply here is to recognize cases like
1442  *              SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.y IS NULL;
1443  * If the join clause is strict for b.y, then only null-extended rows could
1444  * pass the upper WHERE, and we can conclude that what the query is really
1445  * specifying is an anti-semijoin.      We change the join type from JOIN_LEFT
1446  * to JOIN_ANTI.  The IS NULL clause then becomes redundant, and must be
1447  * removed to prevent bogus selectivity calculations, but we leave it to
1448  * distribute_qual_to_rels to get rid of such clauses.
1449  *
1450  * Also, we get rid of JOIN_RIGHT cases by flipping them around to become
1451  * JOIN_LEFT.  This saves some code here and in some later planner routines,
1452  * but the main reason to do it is to not need to invent a JOIN_REVERSE_ANTI
1453  * join type.
1454  *
1455  * To ease recognition of strict qual clauses, we require this routine to be
1456  * run after expression preprocessing (i.e., qual canonicalization and JOIN
1457  * alias-var expansion).
1458  */
1459 void
1460 reduce_outer_joins(PlannerInfo *root)
1461 {
1462         reduce_outer_joins_state *state;
1463
1464         /*
1465          * To avoid doing strictness checks on more quals than necessary, we want
1466          * to stop descending the jointree as soon as there are no outer joins
1467          * below our current point.  This consideration forces a two-pass process.
1468          * The first pass gathers information about which base rels appear below
1469          * each side of each join clause, and about whether there are outer
1470          * join(s) below each side of each join clause. The second pass examines
1471          * qual clauses and changes join types as it descends the tree.
1472          */
1473         state = reduce_outer_joins_pass1((Node *) root->parse->jointree);
1474
1475         /* planner.c shouldn't have called me if no outer joins */
1476         if (state == NULL || !state->contains_outer)
1477                 elog(ERROR, "so where are the outer joins?");
1478
1479         reduce_outer_joins_pass2((Node *) root->parse->jointree,
1480                                                          state, root, NULL, NIL, NIL);
1481 }
1482
1483 /*
1484  * reduce_outer_joins_pass1 - phase 1 data collection
1485  *
1486  * Returns a state node describing the given jointree node.
1487  */
1488 static reduce_outer_joins_state *
1489 reduce_outer_joins_pass1(Node *jtnode)
1490 {
1491         reduce_outer_joins_state *result;
1492
1493         result = (reduce_outer_joins_state *)
1494                 palloc(sizeof(reduce_outer_joins_state));
1495         result->relids = NULL;
1496         result->contains_outer = false;
1497         result->sub_states = NIL;
1498
1499         if (jtnode == NULL)
1500                 return result;
1501         if (IsA(jtnode, RangeTblRef))
1502         {
1503                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1504
1505                 result->relids = bms_make_singleton(varno);
1506         }
1507         else if (IsA(jtnode, FromExpr))
1508         {
1509                 FromExpr   *f = (FromExpr *) jtnode;
1510                 ListCell   *l;
1511
1512                 foreach(l, f->fromlist)
1513                 {
1514                         reduce_outer_joins_state *sub_state;
1515
1516                         sub_state = reduce_outer_joins_pass1(lfirst(l));
1517                         result->relids = bms_add_members(result->relids,
1518                                                                                          sub_state->relids);
1519                         result->contains_outer |= sub_state->contains_outer;
1520                         result->sub_states = lappend(result->sub_states, sub_state);
1521                 }
1522         }
1523         else if (IsA(jtnode, JoinExpr))
1524         {
1525                 JoinExpr   *j = (JoinExpr *) jtnode;
1526                 reduce_outer_joins_state *sub_state;
1527
1528                 /* join's own RT index is not wanted in result->relids */
1529                 if (IS_OUTER_JOIN(j->jointype))
1530                         result->contains_outer = true;
1531
1532                 sub_state = reduce_outer_joins_pass1(j->larg);
1533                 result->relids = bms_add_members(result->relids,
1534                                                                                  sub_state->relids);
1535                 result->contains_outer |= sub_state->contains_outer;
1536                 result->sub_states = lappend(result->sub_states, sub_state);
1537
1538                 sub_state = reduce_outer_joins_pass1(j->rarg);
1539                 result->relids = bms_add_members(result->relids,
1540                                                                                  sub_state->relids);
1541                 result->contains_outer |= sub_state->contains_outer;
1542                 result->sub_states = lappend(result->sub_states, sub_state);
1543         }
1544         else
1545                 elog(ERROR, "unrecognized node type: %d",
1546                          (int) nodeTag(jtnode));
1547         return result;
1548 }
1549
1550 /*
1551  * reduce_outer_joins_pass2 - phase 2 processing
1552  *
1553  *      jtnode: current jointree node
1554  *      state: state data collected by phase 1 for this node
1555  *      root: toplevel planner state
1556  *      nonnullable_rels: set of base relids forced non-null by upper quals
1557  *      nonnullable_vars: list of Vars forced non-null by upper quals
1558  *      forced_null_vars: list of Vars forced null by upper quals
1559  */
1560 static void
1561 reduce_outer_joins_pass2(Node *jtnode,
1562                                                  reduce_outer_joins_state *state,
1563                                                  PlannerInfo *root,
1564                                                  Relids nonnullable_rels,
1565                                                  List *nonnullable_vars,
1566                                                  List *forced_null_vars)
1567 {
1568         /*
1569          * pass 2 should never descend as far as an empty subnode or base rel,
1570          * because it's only called on subtrees marked as contains_outer.
1571          */
1572         if (jtnode == NULL)
1573                 elog(ERROR, "reached empty jointree");
1574         if (IsA(jtnode, RangeTblRef))
1575                 elog(ERROR, "reached base rel");
1576         else if (IsA(jtnode, FromExpr))
1577         {
1578                 FromExpr   *f = (FromExpr *) jtnode;
1579                 ListCell   *l;
1580                 ListCell   *s;
1581                 Relids          pass_nonnullable_rels;
1582                 List       *pass_nonnullable_vars;
1583                 List       *pass_forced_null_vars;
1584
1585                 /* Scan quals to see if we can add any constraints */
1586                 pass_nonnullable_rels = find_nonnullable_rels(f->quals);
1587                 pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels,
1588                                                                                                 nonnullable_rels);
1589                 /* NB: we rely on list_concat to not damage its second argument */
1590                 pass_nonnullable_vars = find_nonnullable_vars(f->quals);
1591                 pass_nonnullable_vars = list_concat(pass_nonnullable_vars,
1592                                                                                         nonnullable_vars);
1593                 pass_forced_null_vars = find_forced_null_vars(f->quals);
1594                 pass_forced_null_vars = list_concat(pass_forced_null_vars,
1595                                                                                         forced_null_vars);
1596                 /* And recurse --- but only into interesting subtrees */
1597                 Assert(list_length(f->fromlist) == list_length(state->sub_states));
1598                 forboth(l, f->fromlist, s, state->sub_states)
1599                 {
1600                         reduce_outer_joins_state *sub_state = lfirst(s);
1601
1602                         if (sub_state->contains_outer)
1603                                 reduce_outer_joins_pass2(lfirst(l), sub_state, root,
1604                                                                                  pass_nonnullable_rels,
1605                                                                                  pass_nonnullable_vars,
1606                                                                                  pass_forced_null_vars);
1607                 }
1608                 bms_free(pass_nonnullable_rels);
1609                 /* can't so easily clean up var lists, unfortunately */
1610         }
1611         else if (IsA(jtnode, JoinExpr))
1612         {
1613                 JoinExpr   *j = (JoinExpr *) jtnode;
1614                 int                     rtindex = j->rtindex;
1615                 JoinType        jointype = j->jointype;
1616                 reduce_outer_joins_state *left_state = linitial(state->sub_states);
1617                 reduce_outer_joins_state *right_state = lsecond(state->sub_states);
1618                 List       *local_nonnullable_vars = NIL;
1619                 bool            computed_local_nonnullable_vars = false;
1620
1621                 /* Can we simplify this join? */
1622                 switch (jointype)
1623                 {
1624                         case JOIN_INNER:
1625                                 break;
1626                         case JOIN_LEFT:
1627                                 if (bms_overlap(nonnullable_rels, right_state->relids))
1628                                         jointype = JOIN_INNER;
1629                                 break;
1630                         case JOIN_RIGHT:
1631                                 if (bms_overlap(nonnullable_rels, left_state->relids))
1632                                         jointype = JOIN_INNER;
1633                                 break;
1634                         case JOIN_FULL:
1635                                 if (bms_overlap(nonnullable_rels, left_state->relids))
1636                                 {
1637                                         if (bms_overlap(nonnullable_rels, right_state->relids))
1638                                                 jointype = JOIN_INNER;
1639                                         else
1640                                                 jointype = JOIN_LEFT;
1641                                 }
1642                                 else
1643                                 {
1644                                         if (bms_overlap(nonnullable_rels, right_state->relids))
1645                                                 jointype = JOIN_RIGHT;
1646                                 }
1647                                 break;
1648                         case JOIN_SEMI:
1649                         case JOIN_ANTI:
1650
1651                                 /*
1652                                  * These could only have been introduced by pull_up_sublinks,
1653                                  * so there's no way that upper quals could refer to their
1654                                  * righthand sides, and no point in checking.
1655                                  */
1656                                 break;
1657                         default:
1658                                 elog(ERROR, "unrecognized join type: %d",
1659                                          (int) jointype);
1660                                 break;
1661                 }
1662
1663                 /*
1664                  * Convert JOIN_RIGHT to JOIN_LEFT.  Note that in the case where we
1665                  * reduced JOIN_FULL to JOIN_RIGHT, this will mean the JoinExpr no
1666                  * longer matches the internal ordering of any CoalesceExpr's built to
1667                  * represent merged join variables.  We don't care about that at
1668                  * present, but be wary of it ...
1669                  */
1670                 if (jointype == JOIN_RIGHT)
1671                 {
1672                         Node       *tmparg;
1673
1674                         tmparg = j->larg;
1675                         j->larg = j->rarg;
1676                         j->rarg = tmparg;
1677                         jointype = JOIN_LEFT;
1678                         right_state = linitial(state->sub_states);
1679                         left_state = lsecond(state->sub_states);
1680                 }
1681
1682                 /*
1683                  * See if we can reduce JOIN_LEFT to JOIN_ANTI.  This is the case if
1684                  * the join's own quals are strict for any var that was forced null by
1685                  * higher qual levels.  NOTE: there are other ways that we could
1686                  * detect an anti-join, in particular if we were to check whether Vars
1687                  * coming from the RHS must be non-null because of table constraints.
1688                  * That seems complicated and expensive though (in particular, one
1689                  * would have to be wary of lower outer joins). For the moment this
1690                  * seems sufficient.
1691                  */
1692                 if (jointype == JOIN_LEFT)
1693                 {
1694                         List       *overlap;
1695
1696                         local_nonnullable_vars = find_nonnullable_vars(j->quals);
1697                         computed_local_nonnullable_vars = true;
1698
1699                         /*
1700                          * It's not sufficient to check whether local_nonnullable_vars and
1701                          * forced_null_vars overlap: we need to know if the overlap
1702                          * includes any RHS variables.
1703                          */
1704                         overlap = list_intersection(local_nonnullable_vars,
1705                                                                                 forced_null_vars);
1706                         if (overlap != NIL &&
1707                                 bms_overlap(pull_varnos((Node *) overlap),
1708                                                         right_state->relids))
1709                                 jointype = JOIN_ANTI;
1710                 }
1711
1712                 /* Apply the jointype change, if any, to both jointree node and RTE */
1713                 if (rtindex && jointype != j->jointype)
1714                 {
1715                         RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable);
1716
1717                         Assert(rte->rtekind == RTE_JOIN);
1718                         Assert(rte->jointype == j->jointype);
1719                         rte->jointype = jointype;
1720                 }
1721                 j->jointype = jointype;
1722
1723                 /* Only recurse if there's more to do below here */
1724                 if (left_state->contains_outer || right_state->contains_outer)
1725                 {
1726                         Relids          local_nonnullable_rels;
1727                         List       *local_forced_null_vars;
1728                         Relids          pass_nonnullable_rels;
1729                         List       *pass_nonnullable_vars;
1730                         List       *pass_forced_null_vars;
1731
1732                         /*
1733                          * If this join is (now) inner, we can add any constraints its
1734                          * quals provide to those we got from above.  But if it is outer,
1735                          * we can pass down the local constraints only into the nullable
1736                          * side, because an outer join never eliminates any rows from its
1737                          * non-nullable side.  Also, there is no point in passing upper
1738                          * constraints into the nullable side, since if there were any
1739                          * we'd have been able to reduce the join.  (In the case of upper
1740                          * forced-null constraints, we *must not* pass them into the
1741                          * nullable side --- they either applied here, or not.) The upshot
1742                          * is that we pass either the local or the upper constraints,
1743                          * never both, to the children of an outer join.
1744                          *
1745                          * At a FULL join we just punt and pass nothing down --- is it
1746                          * possible to be smarter?
1747                          */
1748                         if (jointype != JOIN_FULL)
1749                         {
1750                                 local_nonnullable_rels = find_nonnullable_rels(j->quals);
1751                                 if (!computed_local_nonnullable_vars)
1752                                         local_nonnullable_vars = find_nonnullable_vars(j->quals);
1753                                 local_forced_null_vars = find_forced_null_vars(j->quals);
1754                                 if (jointype == JOIN_INNER)
1755                                 {
1756                                         /* OK to merge upper and local constraints */
1757                                         local_nonnullable_rels = bms_add_members(local_nonnullable_rels,
1758                                                                                                                    nonnullable_rels);
1759                                         local_nonnullable_vars = list_concat(local_nonnullable_vars,
1760                                                                                                                  nonnullable_vars);
1761                                         local_forced_null_vars = list_concat(local_forced_null_vars,
1762                                                                                                                  forced_null_vars);
1763                                 }
1764                         }
1765                         else
1766                         {
1767                                 /* no use in calculating these */
1768                                 local_nonnullable_rels = NULL;
1769                                 local_forced_null_vars = NIL;
1770                         }
1771
1772                         if (left_state->contains_outer)
1773                         {
1774                                 if (jointype == JOIN_INNER)
1775                                 {
1776                                         /* pass union of local and upper constraints */
1777                                         pass_nonnullable_rels = local_nonnullable_rels;
1778                                         pass_nonnullable_vars = local_nonnullable_vars;
1779                                         pass_forced_null_vars = local_forced_null_vars;
1780                                 }
1781                                 else if (jointype != JOIN_FULL) /* ie, LEFT/SEMI/ANTI */
1782                                 {
1783                                         /* can't pass local constraints to non-nullable side */
1784                                         pass_nonnullable_rels = nonnullable_rels;
1785                                         pass_nonnullable_vars = nonnullable_vars;
1786                                         pass_forced_null_vars = forced_null_vars;
1787                                 }
1788                                 else
1789                                 {
1790                                         /* no constraints pass through JOIN_FULL */
1791                                         pass_nonnullable_rels = NULL;
1792                                         pass_nonnullable_vars = NIL;
1793                                         pass_forced_null_vars = NIL;
1794                                 }
1795                                 reduce_outer_joins_pass2(j->larg, left_state, root,
1796                                                                                  pass_nonnullable_rels,
1797                                                                                  pass_nonnullable_vars,
1798                                                                                  pass_forced_null_vars);
1799                         }
1800
1801                         if (right_state->contains_outer)
1802                         {
1803                                 if (jointype != JOIN_FULL)              /* ie, INNER/LEFT/SEMI/ANTI */
1804                                 {
1805                                         /* pass appropriate constraints, per comment above */
1806                                         pass_nonnullable_rels = local_nonnullable_rels;
1807                                         pass_nonnullable_vars = local_nonnullable_vars;
1808                                         pass_forced_null_vars = local_forced_null_vars;
1809                                 }
1810                                 else
1811                                 {
1812                                         /* no constraints pass through JOIN_FULL */
1813                                         pass_nonnullable_rels = NULL;
1814                                         pass_nonnullable_vars = NIL;
1815                                         pass_forced_null_vars = NIL;
1816                                 }
1817                                 reduce_outer_joins_pass2(j->rarg, right_state, root,
1818                                                                                  pass_nonnullable_rels,
1819                                                                                  pass_nonnullable_vars,
1820                                                                                  pass_forced_null_vars);
1821                         }
1822                         bms_free(local_nonnullable_rels);
1823                 }
1824         }
1825         else
1826                 elog(ERROR, "unrecognized node type: %d",
1827                          (int) nodeTag(jtnode));
1828 }
1829
1830 /*
1831  * substitute_multiple_relids - adjust node relid sets after pulling up
1832  * a subquery
1833  *
1834  * Find any PlaceHolderVar nodes in the given tree that reference the
1835  * pulled-up relid, and change them to reference the replacement relid(s).
1836  * We do not need to recurse into subqueries, since no subquery of the current
1837  * top query could (yet) contain such a reference.
1838  *
1839  * NOTE: although this has the form of a walker, we cheat and modify the
1840  * nodes in-place.  This should be OK since the tree was copied by
1841  * pullup_replace_vars earlier.  Avoid scribbling on the original values of
1842  * the bitmapsets, though, because expression_tree_mutator doesn't copy those.
1843  */
1844
1845 typedef struct
1846 {
1847         int                     varno;
1848         Relids          subrelids;
1849 } substitute_multiple_relids_context;
1850
1851 static bool
1852 substitute_multiple_relids_walker(Node *node,
1853                                                                   substitute_multiple_relids_context *context)
1854 {
1855         if (node == NULL)
1856                 return false;
1857         if (IsA(node, PlaceHolderVar))
1858         {
1859                 PlaceHolderVar *phv = (PlaceHolderVar *) node;
1860
1861                 if (bms_is_member(context->varno, phv->phrels))
1862                 {
1863                         phv->phrels = bms_union(phv->phrels,
1864                                                                         context->subrelids);
1865                         phv->phrels = bms_del_member(phv->phrels,
1866                                                                                  context->varno);
1867                 }
1868                 /* fall through to examine children */
1869         }
1870         /* Shouldn't need to handle planner auxiliary nodes here */
1871         Assert(!IsA(node, SpecialJoinInfo));
1872         Assert(!IsA(node, AppendRelInfo));
1873         Assert(!IsA(node, PlaceHolderInfo));
1874
1875         return expression_tree_walker(node, substitute_multiple_relids_walker,
1876                                                                   (void *) context);
1877 }
1878
1879 static void
1880 substitute_multiple_relids(Node *node, int varno, Relids subrelids)
1881 {
1882         substitute_multiple_relids_context context;
1883
1884         context.varno = varno;
1885         context.subrelids = subrelids;
1886
1887         /*
1888          * Must be prepared to start with a Query or a bare expression tree.
1889          */
1890         query_or_expression_tree_walker(node,
1891                                                                         substitute_multiple_relids_walker,
1892                                                                         (void *) &context,
1893                                                                         0);
1894 }
1895
1896 /*
1897  * fix_append_rel_relids: update RT-index fields of AppendRelInfo nodes
1898  *
1899  * When we pull up a subquery, any AppendRelInfo references to the subquery's
1900  * RT index have to be replaced by the substituted relid (and there had better
1901  * be only one).  We also need to apply substitute_multiple_relids to their
1902  * translated_vars lists, since those might contain PlaceHolderVars.
1903  *
1904  * We assume we may modify the AppendRelInfo nodes in-place.
1905  */
1906 static void
1907 fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
1908 {
1909         ListCell   *l;
1910         int                     subvarno = -1;
1911
1912         /*
1913          * We only want to extract the member relid once, but we mustn't fail
1914          * immediately if there are multiple members; it could be that none of the
1915          * AppendRelInfo nodes refer to it.  So compute it on first use. Note that
1916          * bms_singleton_member will complain if set is not singleton.
1917          */
1918         foreach(l, append_rel_list)
1919         {
1920                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
1921
1922                 /* The parent_relid shouldn't ever be a pullup target */
1923                 Assert(appinfo->parent_relid != varno);
1924
1925                 if (appinfo->child_relid == varno)
1926                 {
1927                         if (subvarno < 0)
1928                                 subvarno = bms_singleton_member(subrelids);
1929                         appinfo->child_relid = subvarno;
1930                 }
1931
1932                 /* Also finish fixups for its translated vars */
1933                 substitute_multiple_relids((Node *) appinfo->translated_vars,
1934                                                                    varno, subrelids);
1935         }
1936 }
1937
1938 /*
1939  * get_relids_in_jointree: get set of RT indexes present in a jointree
1940  *
1941  * If include_joins is true, join RT indexes are included; if false,
1942  * only base rels are included.
1943  */
1944 Relids
1945 get_relids_in_jointree(Node *jtnode, bool include_joins)
1946 {
1947         Relids          result = NULL;
1948
1949         if (jtnode == NULL)
1950                 return result;
1951         if (IsA(jtnode, RangeTblRef))
1952         {
1953                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1954
1955                 result = bms_make_singleton(varno);
1956         }
1957         else if (IsA(jtnode, FromExpr))
1958         {
1959                 FromExpr   *f = (FromExpr *) jtnode;
1960                 ListCell   *l;
1961
1962                 foreach(l, f->fromlist)
1963                 {
1964                         result = bms_join(result,
1965                                                           get_relids_in_jointree(lfirst(l),
1966                                                                                                          include_joins));
1967                 }
1968         }
1969         else if (IsA(jtnode, JoinExpr))
1970         {
1971                 JoinExpr   *j = (JoinExpr *) jtnode;
1972
1973                 result = get_relids_in_jointree(j->larg, include_joins);
1974                 result = bms_join(result,
1975                                                   get_relids_in_jointree(j->rarg, include_joins));
1976                 if (include_joins && j->rtindex)
1977                         result = bms_add_member(result, j->rtindex);
1978         }
1979         else
1980                 elog(ERROR, "unrecognized node type: %d",
1981                          (int) nodeTag(jtnode));
1982         return result;
1983 }
1984
1985 /*
1986  * get_relids_for_join: get set of base RT indexes making up a join
1987  */
1988 Relids
1989 get_relids_for_join(PlannerInfo *root, int joinrelid)
1990 {
1991         Node       *jtnode;
1992
1993         jtnode = find_jointree_node_for_rel((Node *) root->parse->jointree,
1994                                                                                 joinrelid);
1995         if (!jtnode)
1996                 elog(ERROR, "could not find join node %d", joinrelid);
1997         return get_relids_in_jointree(jtnode, false);
1998 }
1999
2000 /*
2001  * find_jointree_node_for_rel: locate jointree node for a base or join RT index
2002  *
2003  * Returns NULL if not found
2004  */
2005 static Node *
2006 find_jointree_node_for_rel(Node *jtnode, int relid)
2007 {
2008         if (jtnode == NULL)
2009                 return NULL;
2010         if (IsA(jtnode, RangeTblRef))
2011         {
2012                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
2013
2014                 if (relid == varno)
2015                         return jtnode;
2016         }
2017         else if (IsA(jtnode, FromExpr))
2018         {
2019                 FromExpr   *f = (FromExpr *) jtnode;
2020                 ListCell   *l;
2021
2022                 foreach(l, f->fromlist)
2023                 {
2024                         jtnode = find_jointree_node_for_rel(lfirst(l), relid);
2025                         if (jtnode)
2026                                 return jtnode;
2027                 }
2028         }
2029         else if (IsA(jtnode, JoinExpr))
2030         {
2031                 JoinExpr   *j = (JoinExpr *) jtnode;
2032
2033                 if (relid == j->rtindex)
2034                         return jtnode;
2035                 jtnode = find_jointree_node_for_rel(j->larg, relid);
2036                 if (jtnode)
2037                         return jtnode;
2038                 jtnode = find_jointree_node_for_rel(j->rarg, relid);
2039                 if (jtnode)
2040                         return jtnode;
2041         }
2042         else
2043                 elog(ERROR, "unrecognized node type: %d",
2044                          (int) nodeTag(jtnode));
2045         return NULL;
2046 }