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