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_IN_clauses
   8  *              pull_up_subqueries
   9  *              do expression preprocessing (including flattening JOIN alias vars)
  10  *              reduce_outer_joins
  11  *
  12  *
  13  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
  14  * Portions Copyright (c) 1994, Regents of the University of California
  15  *
  16  *
  17  * IDENTIFICATION
  18  *        $PostgreSQL: pgsql/src/backend/optimizer/prep/prepjointree.c,v 1.45 2007/01/05 22:19:32 momjian Exp $
  19  *
  20  *-------------------------------------------------------------------------
  21  */
  22 #include "postgres.h"
  23
  24 #include "nodes/makefuncs.h"
  25 #include "optimizer/clauses.h"
  26 #include "optimizer/prep.h"
  27 #include "optimizer/subselect.h"
  28 #include "optimizer/tlist.h"
  29 #include "optimizer/var.h"
  30 #include "parser/parse_expr.h"
  31 #include "parser/parsetree.h"
  32 #include "rewrite/rewriteManip.h"
  33
  34
  35 typedef struct reduce_outer_joins_state
  36 {
  37         Relids          relids;                 /* base relids within this subtree */
  38         bool            contains_outer; /* does subtree contain outer join(s)? */
  39         List       *sub_states;         /* List of states for subtree components */
  40 } reduce_outer_joins_state;
  41
  42 static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,
  43                                                 RangeTblEntry *rte,
  44                                                 bool below_outer_join,
  45                                                 bool append_rel_member);
  46 static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,
  47                                                  RangeTblEntry *rte);
  48 static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,
  49                                                    int parentRTindex, Query *setOpQuery);
  50 static void make_setop_translation_lists(Query *query,
  51                                                          Index newvarno,
  52                                                          List **col_mappings, List **translated_vars);
  53 static bool is_simple_subquery(Query *subquery);
  54 static bool is_simple_union_all(Query *subquery);
  55 static bool is_simple_union_all_recurse(Node *setOp, Query *setOpQuery,
  56                                                         List *colTypes);
  57 static bool has_nullable_targetlist(Query *subquery);
  58 static bool is_safe_append_member(Query *subquery);
  59 static void resolvenew_in_jointree(Node *jtnode, int varno,
  60                                            RangeTblEntry *rte, List *subtlist);
  61 static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode);
  62 static void reduce_outer_joins_pass2(Node *jtnode,
  63                                                  reduce_outer_joins_state *state,
  64                                                  PlannerInfo *root,
  65                                                  Relids nonnullable_rels);
  66 static void fix_in_clause_relids(List *in_info_list, int varno,
  67                                          Relids subrelids);
  68 static void fix_append_rel_relids(List *append_rel_list, int varno,
  69                                           Relids subrelids);
  70 static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
  71
  72
  73 /*
  74  * pull_up_IN_clauses
  75  *              Attempt to pull up top-level IN clauses to be treated like joins.
  76  *
  77  * A clause "foo IN (sub-SELECT)" appearing at the top level of WHERE can
  78  * be processed by pulling the sub-SELECT up to become a rangetable entry
  79  * and handling the implied equality comparisons as join operators (with
  80  * special join rules).
  81  * This optimization *only* works at the top level of WHERE, because
  82  * it cannot distinguish whether the IN ought to return FALSE or NULL in
  83  * cases involving NULL inputs.  This routine searches for such clauses
  84  * and does the necessary parsetree transformations if any are found.
  85  *
  86  * This routine has to run before preprocess_expression(), so the WHERE
  87  * clause is not yet reduced to implicit-AND format.  That means we need
  88  * to recursively search through explicit AND clauses, which are
  89  * probably only binary ANDs.  We stop as soon as we hit a non-AND item.
  90  *
  91  * Returns the possibly-modified version of the given qual-tree node.
  92  */
  93 Node *
  94 pull_up_IN_clauses(PlannerInfo *root, Node *node)
  95 {
  96         if (node == NULL)
  97                 return NULL;
  98         if (IsA(node, SubLink))
  99         {
 100                 SubLink    *sublink = (SubLink *) node;
 101                 Node       *subst;
 102
 103                 /* Is it a convertible IN clause?  If not, return it as-is */
 104                 subst = convert_IN_to_join(root, sublink);
 105                 if (subst == NULL)
 106                         return node;
 107                 return subst;
 108         }
 109         if (and_clause(node))
 110         {
 111                 List       *newclauses = NIL;
 112                 ListCell   *l;
 113
 114                 foreach(l, ((BoolExpr *) node)->args)
 115                 {
 116                         Node       *oldclause = (Node *) lfirst(l);
 117
 118                         newclauses = lappend(newclauses,
 119                                                                  pull_up_IN_clauses(root, oldclause));
 120                 }
 121                 return (Node *) make_andclause(newclauses);
 122         }
 123         /* Stop if not an AND */
 124         return node;
 125 }
 126
 127 /*
 128  * pull_up_subqueries
 129  *              Look for subqueries in the rangetable that can be pulled up into
 130  *              the parent query.  If the subquery has no special features like
 131  *              grouping/aggregation then we can merge it into the parent's jointree.
 132  *              Also, subqueries that are simple UNION ALL structures can be
 133  *              converted into "append relations".
 134  *
 135  * below_outer_join is true if this jointree node is within the nullable
 136  * side of an outer join.  This restricts what we can do.
 137  *
 138  * append_rel_member is true if we are looking at a member subquery of
 139  * an append relation.  This puts some different restrictions on what
 140  * we can do.
 141  *
 142  * A tricky aspect of this code is that if we pull up a subquery we have
 143  * to replace Vars that reference the subquery's outputs throughout the
 144  * parent query, including quals attached to jointree nodes above the one
 145  * we are currently processing!  We handle this by being careful not to
 146  * change the jointree structure while recursing: no nodes other than
 147  * subquery RangeTblRef entries will be replaced.  Also, we can't turn
 148  * ResolveNew loose on the whole jointree, because it'll return a mutated
 149  * copy of the tree; we have to invoke it just on the quals, instead.
 150  */
 151 Node *
 152 pull_up_subqueries(PlannerInfo *root, Node *jtnode,
 153                                    bool below_outer_join, bool append_rel_member)
 154 {
 155         if (jtnode == NULL)
 156                 return NULL;
 157         if (IsA(jtnode, RangeTblRef))
 158         {
 159                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 160                 RangeTblEntry *rte = rt_fetch(varno, root->parse->rtable);
 161
 162                 /*
 163                  * Is this a subquery RTE, and if so, is the subquery simple enough to
 164                  * pull up?  (If not, do nothing at this node.)
 165                  *
 166                  * If we are inside an outer join, only pull up subqueries whose
 167                  * targetlists are nullable --- otherwise substituting their tlist
 168                  * entries for upper Var references would do the wrong thing (the
 169                  * results wouldn't become NULL when they're supposed to).
 170                  *
 171                  * XXX This could be improved by generating pseudo-variables for such
 172                  * expressions; we'd have to figure out how to get the pseudo-
 173                  * variables evaluated at the right place in the modified plan tree.
 174                  * Fix it someday.
 175                  *
 176                  * If we are looking at an append-relation member, we can't pull it up
 177                  * unless is_safe_append_member says so.
 178                  */
 179                 if (rte->rtekind == RTE_SUBQUERY &&
 180                         is_simple_subquery(rte->subquery) &&
 181                         (!below_outer_join || has_nullable_targetlist(rte->subquery)) &&
 182                         (!append_rel_member || is_safe_append_member(rte->subquery)))
 183                         return pull_up_simple_subquery(root, jtnode, rte,
 184                                                                                    below_outer_join,
 185                                                                                    append_rel_member);
 186
 187                 /*
 188                  * Alternatively, is it a simple UNION ALL subquery?  If so, flatten
 189                  * into an "append relation".  We can do this regardless of
 190                  * nullability considerations since this transformation does not
 191                  * result in propagating non-Var expressions into upper levels of the
 192                  * query.
 193                  *
 194                  * It's also safe to do this regardless of whether this query is
 195                  * itself an appendrel member.  (If you're thinking we should try to
 196                  * flatten the two levels of appendrel together, you're right; but we
 197                  * handle that in set_append_rel_pathlist, not here.)
 198                  */
 199                 if (rte->rtekind == RTE_SUBQUERY &&
 200                         is_simple_union_all(rte->subquery))
 201                         return pull_up_simple_union_all(root, jtnode, rte);
 202         }
 203         else if (IsA(jtnode, FromExpr))
 204         {
 205                 FromExpr   *f = (FromExpr *) jtnode;
 206                 ListCell   *l;
 207
 208                 Assert(!append_rel_member);
 209                 foreach(l, f->fromlist)
 210                         lfirst(l) = pull_up_subqueries(root, lfirst(l),
 211                                                                                    below_outer_join, false);
 212         }
 213         else if (IsA(jtnode, JoinExpr))
 214         {
 215                 JoinExpr   *j = (JoinExpr *) jtnode;
 216
 217                 Assert(!append_rel_member);
 218                 /* Recurse, being careful to tell myself when inside outer join */
 219                 switch (j->jointype)
 220                 {
 221                         case JOIN_INNER:
 222                                 j->larg = pull_up_subqueries(root, j->larg,
 223                                                                                          below_outer_join, false);
 224                                 j->rarg = pull_up_subqueries(root, j->rarg,
 225                                                                                          below_outer_join, false);
 226                                 break;
 227                         case JOIN_LEFT:
 228                                 j->larg = pull_up_subqueries(root, j->larg,
 229                                                                                          below_outer_join, false);
 230                                 j->rarg = pull_up_subqueries(root, j->rarg,
 231                                                                                          true, false);
 232                                 break;
 233                         case JOIN_FULL:
 234                                 j->larg = pull_up_subqueries(root, j->larg,
 235                                                                                          true, false);
 236                                 j->rarg = pull_up_subqueries(root, j->rarg,
 237                                                                                          true, false);
 238                                 break;
 239                         case JOIN_RIGHT:
 240                                 j->larg = pull_up_subqueries(root, j->larg,
 241                                                                                          true, false);
 242                                 j->rarg = pull_up_subqueries(root, j->rarg,
 243                                                                                          below_outer_join, false);
 244                                 break;
 245                         default:
 246                                 elog(ERROR, "unrecognized join type: %d",
 247                                          (int) j->jointype);
 248                                 break;
 249                 }
 250         }
 251         else
 252                 elog(ERROR, "unrecognized node type: %d",
 253                          (int) nodeTag(jtnode));
 254         return jtnode;
 255 }
 256
 257 /*
 258  * pull_up_simple_subquery
 259  *              Attempt to pull up a single simple subquery.
 260  *
 261  * jtnode is a RangeTblRef that has been tentatively identified as a simple
 262  * subquery by pull_up_subqueries.      We return the replacement jointree node,
 263  * or jtnode itself if we determine that the subquery can't be pulled up after
 264  * all.
 265  */
 266 static Node *
 267 pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 268                                                 bool below_outer_join, bool append_rel_member)
 269 {
 270         Query      *parse = root->parse;
 271         int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 272         Query      *subquery;
 273         PlannerInfo *subroot;
 274         int                     rtoffset;
 275         List       *subtlist;
 276         ListCell   *rt;
 277
 278         /*
 279          * Need a modifiable copy of the subquery to hack on.  Even if we didn't
 280          * sometimes choose not to pull up below, we must do this to avoid
 281          * problems if the same subquery is referenced from multiple jointree
 282          * items (which can't happen normally, but might after rule rewriting).
 283          */
 284         subquery = copyObject(rte->subquery);
 285
 286         /*
 287          * Create a PlannerInfo data structure for this subquery.
 288          *
 289          * NOTE: the next few steps should match the first processing in
 290          * subquery_planner().  Can we refactor to avoid code duplication, or
 291          * would that just make things uglier?
 292          */
 293         subroot = makeNode(PlannerInfo);
 294         subroot->parse = subquery;
 295         subroot->in_info_list = NIL;
 296         subroot->append_rel_list = NIL;
 297
 298         /*
 299          * Pull up any IN clauses within the subquery's WHERE, so that we don't
 300          * leave unoptimized INs behind.
 301          */
 302         if (subquery->hasSubLinks)
 303                 subquery->jointree->quals = pull_up_IN_clauses(subroot,
 304                                                                                                   subquery->jointree->quals);
 305
 306         /*
 307          * Recursively pull up the subquery's subqueries, so that
 308          * pull_up_subqueries' processing is complete for its jointree and
 309          * rangetable.
 310          *
 311          * Note: below_outer_join = false is correct here even if we are within an
 312          * outer join in the upper query; the lower query starts with a clean
 313          * slate for outer-join semantics.      Likewise, we say we aren't handling an
 314          * appendrel member.
 315          */
 316         subquery->jointree = (FromExpr *)
 317                 pull_up_subqueries(subroot, (Node *) subquery->jointree, false, false);
 318
 319         /*
 320          * Now we must recheck whether the subquery is still simple enough to pull
 321          * up.  If not, abandon processing it.
 322          *
 323          * We don't really need to recheck all the conditions involved, but it's
 324          * easier just to keep this "if" looking the same as the one in
 325          * pull_up_subqueries.
 326          */
 327         if (is_simple_subquery(subquery) &&
 328                 (!below_outer_join || has_nullable_targetlist(subquery)) &&
 329                 (!append_rel_member || is_safe_append_member(subquery)))
 330         {
 331                 /* good to go */
 332         }
 333         else
 334         {
 335                 /*
 336                  * Give up, return unmodified RangeTblRef.
 337                  *
 338                  * Note: The work we just did will be redone when the subquery gets
 339                  * planned on its own.  Perhaps we could avoid that by storing the
 340                  * modified subquery back into the rangetable, but I'm not gonna risk
 341                  * it now.
 342                  */
 343                 return jtnode;
 344         }
 345
 346         /*
 347          * Adjust level-0 varnos in subquery so that we can append its rangetable
 348          * to upper query's.  We have to fix the subquery's in_info_list and
 349          * append_rel_list, as well.
 350          */
 351         rtoffset = list_length(parse->rtable);
 352         OffsetVarNodes((Node *) subquery, rtoffset, 0);
 353         OffsetVarNodes((Node *) subroot->in_info_list, rtoffset, 0);
 354         OffsetVarNodes((Node *) subroot->append_rel_list, rtoffset, 0);
 355
 356         /*
 357          * Upper-level vars in subquery are now one level closer to their parent
 358          * than before.
 359          */
 360         IncrementVarSublevelsUp((Node *) subquery, -1, 1);
 361         IncrementVarSublevelsUp((Node *) subroot->in_info_list, -1, 1);
 362         IncrementVarSublevelsUp((Node *) subroot->append_rel_list, -1, 1);
 363
 364         /*
 365          * Replace all of the top query's references to the subquery's outputs
 366          * with copies of the adjusted subtlist items, being careful not to
 367          * replace any of the jointree structure. (This'd be a lot cleaner if we
 368          * could use query_tree_mutator.)
 369          */
 370         subtlist = subquery->targetList;
 371         parse->targetList = (List *)
 372                 ResolveNew((Node *) parse->targetList,
 373                                    varno, 0, rte,
 374                                    subtlist, CMD_SELECT, 0);
 375         parse->returningList = (List *)
 376                 ResolveNew((Node *) parse->returningList,
 377                                    varno, 0, rte,
 378                                    subtlist, CMD_SELECT, 0);
 379         resolvenew_in_jointree((Node *) parse->jointree, varno,
 380                                                    rte, subtlist);
 381         Assert(parse->setOperations == NULL);
 382         parse->havingQual =
 383                 ResolveNew(parse->havingQual,
 384                                    varno, 0, rte,
 385                                    subtlist, CMD_SELECT, 0);
 386         root->in_info_list = (List *)
 387                 ResolveNew((Node *) root->in_info_list,
 388                                    varno, 0, rte,
 389                                    subtlist, CMD_SELECT, 0);
 390         root->append_rel_list = (List *)
 391                 ResolveNew((Node *) root->append_rel_list,
 392                                    varno, 0, rte,
 393                                    subtlist, CMD_SELECT, 0);
 394
 395         foreach(rt, parse->rtable)
 396         {
 397                 RangeTblEntry *otherrte = (RangeTblEntry *) lfirst(rt);
 398
 399                 if (otherrte->rtekind == RTE_JOIN)
 400                         otherrte->joinaliasvars = (List *)
 401                                 ResolveNew((Node *) otherrte->joinaliasvars,
 402                                                    varno, 0, rte,
 403                                                    subtlist, CMD_SELECT, 0);
 404         }
 405
 406         /*
 407          * Now append the adjusted rtable entries to upper query. (We hold off
 408          * until after fixing the upper rtable entries; no point in running that
 409          * code on the subquery ones too.)
 410          */
 411         parse->rtable = list_concat(parse->rtable, subquery->rtable);
 412
 413         /*
 414          * Pull up any FOR UPDATE/SHARE markers, too.  (OffsetVarNodes already
 415          * adjusted the marker rtindexes, so just concat the lists.)
 416          */
 417         parse->rowMarks = list_concat(parse->rowMarks, subquery->rowMarks);
 418
 419         /*
 420          * We also have to fix the relid sets of any parent InClauseInfo nodes.
 421          * (This could perhaps be done by ResolveNew, but it would clutter that
 422          * routine's API unreasonably.)
 423          *
 424          * Likewise, relids appearing in AppendRelInfo nodes have to be fixed (but
 425          * we took care of their translated_vars lists above).  We already checked
 426          * that this won't require introducing multiple subrelids into the
 427          * single-slot AppendRelInfo structs.
 428          */
 429         if (root->in_info_list || root->append_rel_list)
 430         {
 431                 Relids          subrelids;
 432
 433                 subrelids = get_relids_in_jointree((Node *) subquery->jointree);
 434                 fix_in_clause_relids(root->in_info_list, varno, subrelids);
 435                 fix_append_rel_relids(root->append_rel_list, varno, subrelids);
 436         }
 437
 438         /*
 439          * And now add any subquery InClauseInfos and AppendRelInfos to our lists.
 440          */
 441         root->in_info_list = list_concat(root->in_info_list,
 442                                                                          subroot->in_info_list);
 443         root->append_rel_list = list_concat(root->append_rel_list,
 444                                                                                 subroot->append_rel_list);
 445
 446         /*
 447          * We don't have to do the equivalent bookkeeping for outer-join info,
 448          * because that hasn't been set up yet.
 449          */
 450         Assert(root->oj_info_list == NIL);
 451         Assert(subroot->oj_info_list == NIL);
 452
 453         /*
 454          * Miscellaneous housekeeping.
 455          */
 456         parse->hasSubLinks |= subquery->hasSubLinks;
 457         /* subquery won't be pulled up if it hasAggs, so no work there */
 458
 459         /*
 460          * Return the adjusted subquery jointree to replace the RangeTblRef entry
 461          * in parent's jointree.
 462          */
 463         return (Node *) subquery->jointree;
 464 }
 465
 466 /*
 467  * pull_up_simple_union_all
 468  *              Pull up a single simple UNION ALL subquery.
 469  *
 470  * jtnode is a RangeTblRef that has been identified as a simple UNION ALL
 471  * subquery by pull_up_subqueries.      We pull up the leaf subqueries and
 472  * build an "append relation" for the union set.  The result value is just
 473  * jtnode, since we don't actually need to change the query jointree.
 474  */
 475 static Node *
 476 pull_up_simple_union_all(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
 477 {
 478         int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 479         Query      *subquery = rte->subquery;
 480
 481         /*
 482          * Recursively scan the subquery's setOperations tree and copy the leaf
 483          * subqueries into the parent rangetable.  Add AppendRelInfo nodes for
 484          * them to the parent's append_rel_list, too.
 485          */
 486         Assert(subquery->setOperations);
 487         pull_up_union_leaf_queries(subquery->setOperations, root, varno, subquery);
 488
 489         /*
 490          * Mark the parent as an append relation.
 491          */
 492         rte->inh = true;
 493
 494         return jtnode;
 495 }
 496
 497 /*
 498  * pull_up_union_leaf_queries -- recursive guts of pull_up_simple_union_all
 499  *
 500  * Note that setOpQuery is the Query containing the setOp node, whose rtable
 501  * is where to look up the RTE if setOp is a RangeTblRef.  This is *not* the
 502  * same as root->parse, which is the top-level Query we are pulling up into.
 503  * parentRTindex is the appendrel parent's index in root->parse->rtable.
 504  */
 505 static void
 506 pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex,
 507                                                    Query *setOpQuery)
 508 {
 509         if (IsA(setOp, RangeTblRef))
 510         {
 511                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 512                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, setOpQuery->rtable);
 513                 Query      *subquery;
 514                 int                     childRTindex;
 515                 AppendRelInfo *appinfo;
 516                 Query      *parse = root->parse;
 517
 518                 /*
 519                  * Make a modifiable copy of the child RTE and contained query.
 520                  */
 521                 rte = copyObject(rte);
 522                 subquery = rte->subquery;
 523                 Assert(subquery != NULL);
 524
 525                 /*
 526                  * Upper-level vars in subquery are now one level closer to their
 527                  * parent than before.  We don't have to worry about offsetting
 528                  * varnos, though, because any such vars must refer to stuff above the
 529                  * level of the query we are pulling into.
 530                  */
 531                 IncrementVarSublevelsUp((Node *) subquery, -1, 1);
 532
 533                 /*
 534                  * Attach child RTE to parent rtable.
 535                  */
 536                 parse->rtable = lappend(parse->rtable, rte);
 537                 childRTindex = list_length(parse->rtable);
 538
 539                 /*
 540                  * Build a suitable AppendRelInfo, and attach to parent's list.
 541                  */
 542                 appinfo = makeNode(AppendRelInfo);
 543                 appinfo->parent_relid = parentRTindex;
 544                 appinfo->child_relid = childRTindex;
 545                 appinfo->parent_reltype = InvalidOid;
 546                 appinfo->child_reltype = InvalidOid;
 547                 make_setop_translation_lists(setOpQuery, childRTindex,
 548                                                                          &appinfo->col_mappings,
 549                                                                          &appinfo->translated_vars);
 550                 appinfo->parent_reloid = InvalidOid;
 551                 root->append_rel_list = lappend(root->append_rel_list, appinfo);
 552
 553                 /*
 554                  * Recursively apply pull_up_subqueries to the new child RTE.  (We
 555                  * must build the AppendRelInfo first, because this will modify it.)
 556                  * Note that we can pass below_outer_join = false even if we're
 557                  * actually under an outer join, because the child's expressions
 558                  * aren't going to propagate up above the join.
 559                  */
 560                 rtr = makeNode(RangeTblRef);
 561                 rtr->rtindex = childRTindex;
 562                 (void) pull_up_subqueries(root, (Node *) rtr, false, true);
 563         }
 564         else if (IsA(setOp, SetOperationStmt))
 565         {
 566                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 567
 568                 /* Recurse to reach leaf queries */
 569                 pull_up_union_leaf_queries(op->larg, root, parentRTindex, setOpQuery);
 570                 pull_up_union_leaf_queries(op->rarg, root, parentRTindex, setOpQuery);
 571         }
 572         else
 573         {
 574                 elog(ERROR, "unrecognized node type: %d",
 575                          (int) nodeTag(setOp));
 576         }
 577 }
 578
 579 /*
 580  * make_setop_translation_lists
 581  *        Build the lists of translations from parent Vars to child Vars for
 582  *        a UNION ALL member.  We need both a column number mapping list
 583  *        and a list of Vars representing the child columns.
 584  */
 585 static void
 586 make_setop_translation_lists(Query *query,
 587                                                          Index newvarno,
 588                                                          List **col_mappings, List **translated_vars)
 589 {
 590         List       *numbers = NIL;
 591         List       *vars = NIL;
 592         ListCell   *l;
 593
 594         foreach(l, query->targetList)
 595         {
 596                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 597
 598                 if (tle->resjunk)
 599                         continue;
 600
 601                 numbers = lappend_int(numbers, tle->resno);
 602                 vars = lappend(vars, makeVar(newvarno,
 603                                                                          tle->resno,
 604                                                                          exprType((Node *) tle->expr),
 605                                                                          exprTypmod((Node *) tle->expr),
 606                                                                          0));
 607         }
 608
 609         *col_mappings = numbers;
 610         *translated_vars = vars;
 611 }
 612
 613 /*
 614  * is_simple_subquery
 615  *        Check a subquery in the range table to see if it's simple enough
 616  *        to pull up into the parent query.
 617  */
 618 static bool
 619 is_simple_subquery(Query *subquery)
 620 {
 621         /*
 622          * Let's just make sure it's a valid subselect ...
 623          */
 624         if (!IsA(subquery, Query) ||
 625                 subquery->commandType != CMD_SELECT ||
 626                 subquery->into != NULL)
 627                 elog(ERROR, "subquery is bogus");
 628
 629         /*
 630          * Can't currently pull up a query with setops (unless it's simple UNION
 631          * ALL, which is handled by a different code path). Maybe after querytree
 632          * redesign...
 633          */
 634         if (subquery->setOperations)
 635                 return false;
 636
 637         /*
 638          * Can't pull up a subquery involving grouping, aggregation, sorting, or
 639          * limiting.
 640          */
 641         if (subquery->hasAggs ||
 642                 subquery->groupClause ||
 643                 subquery->havingQual ||
 644                 subquery->sortClause ||
 645                 subquery->distinctClause ||
 646                 subquery->limitOffset ||
 647                 subquery->limitCount)
 648                 return false;
 649
 650         /*
 651          * Don't pull up a subquery that has any set-returning functions in its
 652          * targetlist.  Otherwise we might well wind up inserting set-returning
 653          * functions into places where they mustn't go, such as quals of higher
 654          * queries.
 655          */
 656         if (expression_returns_set((Node *) subquery->targetList))
 657                 return false;
 658
 659         /*
 660          * Don't pull up a subquery that has any volatile functions in its
 661          * targetlist.  Otherwise we might introduce multiple evaluations of these
 662          * functions, if they get copied to multiple places in the upper query,
 663          * leading to surprising results.
 664          */
 665         if (contain_volatile_functions((Node *) subquery->targetList))
 666                 return false;
 667
 668         /*
 669          * Hack: don't try to pull up a subquery with an empty jointree.
 670          * query_planner() will correctly generate a Result plan for a jointree
 671          * that's totally empty, but I don't think the right things happen if an
 672          * empty FromExpr appears lower down in a jointree. Not worth working hard
 673          * on this, just to collapse SubqueryScan/Result into Result...
 674          */
 675         if (subquery->jointree->fromlist == NIL)
 676                 return false;
 677
 678         return true;
 679 }
 680
 681 /*
 682  * is_simple_union_all
 683  *        Check a subquery to see if it's a simple UNION ALL.
 684  *
 685  * We require all the setops to be UNION ALL (no mixing) and there can't be
 686  * any datatype coercions involved, ie, all the leaf queries must emit the
 687  * same datatypes.
 688  */
 689 static bool
 690 is_simple_union_all(Query *subquery)
 691 {
 692         SetOperationStmt *topop;
 693
 694         /* Let's just make sure it's a valid subselect ... */
 695         if (!IsA(subquery, Query) ||
 696                 subquery->commandType != CMD_SELECT ||
 697                 subquery->into != NULL)
 698                 elog(ERROR, "subquery is bogus");
 699
 700         /* Is it a set-operation query at all? */
 701         topop = (SetOperationStmt *) subquery->setOperations;
 702         if (!topop)
 703                 return false;
 704         Assert(IsA(topop, SetOperationStmt));
 705
 706         /* Can't handle ORDER BY, LIMIT/OFFSET, or locking */
 707         if (subquery->sortClause ||
 708                 subquery->limitOffset ||
 709                 subquery->limitCount ||
 710                 subquery->rowMarks)
 711                 return false;
 712
 713         /* Recursively check the tree of set operations */
 714         return is_simple_union_all_recurse((Node *) topop, subquery,
 715                                                                            topop->colTypes);
 716 }
 717
 718 static bool
 719 is_simple_union_all_recurse(Node *setOp, Query *setOpQuery, List *colTypes)
 720 {
 721         if (IsA(setOp, RangeTblRef))
 722         {
 723                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 724                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, setOpQuery->rtable);
 725                 Query      *subquery = rte->subquery;
 726
 727                 Assert(subquery != NULL);
 728
 729                 /* Leaf nodes are OK if they match the toplevel column types */
 730                 /* We don't have to compare typmods here */
 731                 return tlist_same_datatypes(subquery->targetList, colTypes, true);
 732         }
 733         else if (IsA(setOp, SetOperationStmt))
 734         {
 735                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 736
 737                 /* Must be UNION ALL */
 738                 if (op->op != SETOP_UNION || !op->all)
 739                         return false;
 740
 741                 /* Recurse to check inputs */
 742                 return is_simple_union_all_recurse(op->larg, setOpQuery, colTypes) &&
 743                         is_simple_union_all_recurse(op->rarg, setOpQuery, colTypes);
 744         }
 745         else
 746         {
 747                 elog(ERROR, "unrecognized node type: %d",
 748                          (int) nodeTag(setOp));
 749                 return false;                   /* keep compiler quiet */
 750         }
 751 }
 752
 753 /*
 754  * has_nullable_targetlist
 755  *        Check a subquery in the range table to see if all the non-junk
 756  *        targetlist items are simple variables or strict functions of simple
 757  *        variables (and, hence, will correctly go to NULL when examined above
 758  *        the point of an outer join).
 759  *
 760  * NOTE: it would be correct (and useful) to ignore output columns that aren't
 761  * actually referenced by the enclosing query ... but we do not have that
 762  * information available at this point.
 763  */
 764 static bool
 765 has_nullable_targetlist(Query *subquery)
 766 {
 767         ListCell   *l;
 768
 769         foreach(l, subquery->targetList)
 770         {
 771                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 772
 773                 /* ignore resjunk columns */
 774                 if (tle->resjunk)
 775                         continue;
 776
 777                 /* Must contain a Var of current level */
 778                 if (!contain_vars_of_level((Node *) tle->expr, 0))
 779                         return false;
 780
 781                 /* Must not contain any non-strict constructs */
 782                 if (contain_nonstrict_functions((Node *) tle->expr))
 783                         return false;
 784
 785                 /* This one's OK, keep scanning */
 786         }
 787         return true;
 788 }
 789
 790 /*
 791  * is_safe_append_member
 792  *        Check a subquery that is a leaf of a UNION ALL appendrel to see if it's
 793  *        safe to pull up.
 794  */
 795 static bool
 796 is_safe_append_member(Query *subquery)
 797 {
 798         FromExpr   *jtnode;
 799         ListCell   *l;
 800
 801         /*
 802          * It's only safe to pull up the child if its jointree contains exactly
 803          * one RTE, else the AppendRelInfo data structure breaks. The one base RTE
 804          * could be buried in several levels of FromExpr, however.
 805          *
 806          * Also, the child can't have any WHERE quals because there's no place to
 807          * put them in an appendrel.  (This is a bit annoying...) If we didn't
 808          * need to check this, we'd just test whether get_relids_in_jointree()
 809          * yields a singleton set, to be more consistent with the coding of
 810          * fix_append_rel_relids().
 811          */
 812         jtnode = subquery->jointree;
 813         while (IsA(jtnode, FromExpr))
 814         {
 815                 if (jtnode->quals != NULL)
 816                         return false;
 817                 if (list_length(jtnode->fromlist) != 1)
 818                         return false;
 819                 jtnode = linitial(jtnode->fromlist);
 820         }
 821         if (!IsA(jtnode, RangeTblRef))
 822                 return false;
 823
 824         /*
 825          * XXX For the moment we also have to insist that the subquery's tlist
 826          * includes only simple Vars.  This is pretty annoying, but fixing it
 827          * seems to require nontrivial changes --- mainly because joinrel tlists
 828          * are presently assumed to contain only Vars.  Perhaps a pseudo-variable
 829          * mechanism similar to the one speculated about in pull_up_subqueries'
 830          * comments would help?  FIXME someday.
 831          */
 832         foreach(l, subquery->targetList)
 833         {
 834                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 835
 836                 if (tle->resjunk)
 837                         continue;
 838                 if (!(tle->expr && IsA(tle->expr, Var)))
 839                         return false;
 840         }
 841
 842         return true;
 843 }
 844
 845 /*
 846  * Helper routine for pull_up_subqueries: do ResolveNew on every expression
 847  * in the jointree, without changing the jointree structure itself.  Ugly,
 848  * but there's no other way...
 849  */
 850 static void
 851 resolvenew_in_jointree(Node *jtnode, int varno,
 852                                            RangeTblEntry *rte, List *subtlist)
 853 {
 854         if (jtnode == NULL)
 855                 return;
 856         if (IsA(jtnode, RangeTblRef))
 857         {
 858                 /* nothing to do here */
 859         }
 860         else if (IsA(jtnode, FromExpr))
 861         {
 862                 FromExpr   *f = (FromExpr *) jtnode;
 863                 ListCell   *l;
 864
 865                 foreach(l, f->fromlist)
 866                         resolvenew_in_jointree(lfirst(l), varno, rte, subtlist);
 867                 f->quals = ResolveNew(f->quals,
 868                                                           varno, 0, rte,
 869                                                           subtlist, CMD_SELECT, 0);
 870         }
 871         else if (IsA(jtnode, JoinExpr))
 872         {
 873                 JoinExpr   *j = (JoinExpr *) jtnode;
 874
 875                 resolvenew_in_jointree(j->larg, varno, rte, subtlist);
 876                 resolvenew_in_jointree(j->rarg, varno, rte, subtlist);
 877                 j->quals = ResolveNew(j->quals,
 878                                                           varno, 0, rte,
 879                                                           subtlist, CMD_SELECT, 0);
 880
 881                 /*
 882                  * We don't bother to update the colvars list, since it won't be used
 883                  * again ...
 884                  */
 885         }
 886         else
 887                 elog(ERROR, "unrecognized node type: %d",
 888                          (int) nodeTag(jtnode));
 889 }
 890
 891 /*
 892  * reduce_outer_joins
 893  *              Attempt to reduce outer joins to plain inner joins.
 894  *
 895  * The idea here is that given a query like
 896  *              SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
 897  * we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
 898  * is strict.  The strict operator will always return NULL, causing the outer
 899  * WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
 900  * columns.  Therefore, there's no need for the join to produce null-extended
 901  * rows in the first place --- which makes it a plain join not an outer join.
 902  * (This scenario may not be very likely in a query written out by hand, but
 903  * it's reasonably likely when pushing quals down into complex views.)
 904  *
 905  * More generally, an outer join can be reduced in strength if there is a
 906  * strict qual above it in the qual tree that constrains a Var from the
 907  * nullable side of the join to be non-null.  (For FULL joins this applies
 908  * to each side separately.)
 909  *
 910  * To ease recognition of strict qual clauses, we require this routine to be
 911  * run after expression preprocessing (i.e., qual canonicalization and JOIN
 912  * alias-var expansion).
 913  */
 914 void
 915 reduce_outer_joins(PlannerInfo *root)
 916 {
 917         reduce_outer_joins_state *state;
 918
 919         /*
 920          * To avoid doing strictness checks on more quals than necessary, we want
 921          * to stop descending the jointree as soon as there are no outer joins
 922          * below our current point.  This consideration forces a two-pass process.
 923          * The first pass gathers information about which base rels appear below
 924          * each side of each join clause, and about whether there are outer
 925          * join(s) below each side of each join clause. The second pass examines
 926          * qual clauses and changes join types as it descends the tree.
 927          */
 928         state = reduce_outer_joins_pass1((Node *) root->parse->jointree);
 929
 930         /* planner.c shouldn't have called me if no outer joins */
 931         if (state == NULL || !state->contains_outer)
 932                 elog(ERROR, "so where are the outer joins?");
 933
 934         reduce_outer_joins_pass2((Node *) root->parse->jointree,
 935                                                          state, root, NULL);
 936 }
 937
 938 /*
 939  * reduce_outer_joins_pass1 - phase 1 data collection
 940  *
 941  * Returns a state node describing the given jointree node.
 942  */
 943 static reduce_outer_joins_state *
 944 reduce_outer_joins_pass1(Node *jtnode)
 945 {
 946         reduce_outer_joins_state *result;
 947
 948         result = (reduce_outer_joins_state *)
 949                 palloc(sizeof(reduce_outer_joins_state));
 950         result->relids = NULL;
 951         result->contains_outer = false;
 952         result->sub_states = NIL;
 953
 954         if (jtnode == NULL)
 955                 return result;
 956         if (IsA(jtnode, RangeTblRef))
 957         {
 958                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 959
 960                 result->relids = bms_make_singleton(varno);
 961         }
 962         else if (IsA(jtnode, FromExpr))
 963         {
 964                 FromExpr   *f = (FromExpr *) jtnode;
 965                 ListCell   *l;
 966
 967                 foreach(l, f->fromlist)
 968                 {
 969                         reduce_outer_joins_state *sub_state;
 970
 971                         sub_state = reduce_outer_joins_pass1(lfirst(l));
 972                         result->relids = bms_add_members(result->relids,
 973                                                                                          sub_state->relids);
 974                         result->contains_outer |= sub_state->contains_outer;
 975                         result->sub_states = lappend(result->sub_states, sub_state);
 976                 }
 977         }
 978         else if (IsA(jtnode, JoinExpr))
 979         {
 980                 JoinExpr   *j = (JoinExpr *) jtnode;
 981                 reduce_outer_joins_state *sub_state;
 982
 983                 /* join's own RT index is not wanted in result->relids */
 984                 if (IS_OUTER_JOIN(j->jointype))
 985                         result->contains_outer = true;
 986
 987                 sub_state = reduce_outer_joins_pass1(j->larg);
 988                 result->relids = bms_add_members(result->relids,
 989                                                                                  sub_state->relids);
 990                 result->contains_outer |= sub_state->contains_outer;
 991                 result->sub_states = lappend(result->sub_states, sub_state);
 992
 993                 sub_state = reduce_outer_joins_pass1(j->rarg);
 994                 result->relids = bms_add_members(result->relids,
 995                                                                                  sub_state->relids);
 996                 result->contains_outer |= sub_state->contains_outer;
 997                 result->sub_states = lappend(result->sub_states, sub_state);
 998         }
 999         else
1000                 elog(ERROR, "unrecognized node type: %d",
1001                          (int) nodeTag(jtnode));
1002         return result;
1003 }
1004
1005 /*
1006  * reduce_outer_joins_pass2 - phase 2 processing
1007  *
1008  *      jtnode: current jointree node
1009  *      state: state data collected by phase 1 for this node
1010  *      root: toplevel planner state
1011  *      nonnullable_rels: set of base relids forced non-null by upper quals
1012  */
1013 static void
1014 reduce_outer_joins_pass2(Node *jtnode,
1015                                                  reduce_outer_joins_state *state,
1016                                                  PlannerInfo *root,
1017                                                  Relids nonnullable_rels)
1018 {
1019         /*
1020          * pass 2 should never descend as far as an empty subnode or base rel,
1021          * because it's only called on subtrees marked as contains_outer.
1022          */
1023         if (jtnode == NULL)
1024                 elog(ERROR, "reached empty jointree");
1025         if (IsA(jtnode, RangeTblRef))
1026                 elog(ERROR, "reached base rel");
1027         else if (IsA(jtnode, FromExpr))
1028         {
1029                 FromExpr   *f = (FromExpr *) jtnode;
1030                 ListCell   *l;
1031                 ListCell   *s;
1032                 Relids          pass_nonnullable;
1033
1034                 /* Scan quals to see if we can add any nonnullability constraints */
1035                 pass_nonnullable = find_nonnullable_rels(f->quals);
1036                 pass_nonnullable = bms_add_members(pass_nonnullable,
1037                                                                                    nonnullable_rels);
1038                 /* And recurse --- but only into interesting subtrees */
1039                 Assert(list_length(f->fromlist) == list_length(state->sub_states));
1040                 forboth(l, f->fromlist, s, state->sub_states)
1041                 {
1042                         reduce_outer_joins_state *sub_state = lfirst(s);
1043
1044                         if (sub_state->contains_outer)
1045                                 reduce_outer_joins_pass2(lfirst(l), sub_state, root,
1046                                                                                  pass_nonnullable);
1047                 }
1048                 bms_free(pass_nonnullable);
1049         }
1050         else if (IsA(jtnode, JoinExpr))
1051         {
1052                 JoinExpr   *j = (JoinExpr *) jtnode;
1053                 int                     rtindex = j->rtindex;
1054                 JoinType        jointype = j->jointype;
1055                 reduce_outer_joins_state *left_state = linitial(state->sub_states);
1056                 reduce_outer_joins_state *right_state = lsecond(state->sub_states);
1057
1058                 /* Can we simplify this join? */
1059                 switch (jointype)
1060                 {
1061                         case JOIN_LEFT:
1062                                 if (bms_overlap(nonnullable_rels, right_state->relids))
1063                                         jointype = JOIN_INNER;
1064                                 break;
1065                         case JOIN_RIGHT:
1066                                 if (bms_overlap(nonnullable_rels, left_state->relids))
1067                                         jointype = JOIN_INNER;
1068                                 break;
1069                         case JOIN_FULL:
1070                                 if (bms_overlap(nonnullable_rels, left_state->relids))
1071                                 {
1072                                         if (bms_overlap(nonnullable_rels, right_state->relids))
1073                                                 jointype = JOIN_INNER;
1074                                         else
1075                                                 jointype = JOIN_LEFT;
1076                                 }
1077                                 else
1078                                 {
1079                                         if (bms_overlap(nonnullable_rels, right_state->relids))
1080                                                 jointype = JOIN_RIGHT;
1081                                 }
1082                                 break;
1083                         default:
1084                                 break;
1085                 }
1086                 if (jointype != j->jointype)
1087                 {
1088                         /* apply the change to both jointree node and RTE */
1089                         RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable);
1090
1091                         Assert(rte->rtekind == RTE_JOIN);
1092                         Assert(rte->jointype == j->jointype);
1093                         rte->jointype = j->jointype = jointype;
1094                 }
1095
1096                 /* Only recurse if there's more to do below here */
1097                 if (left_state->contains_outer || right_state->contains_outer)
1098                 {
1099                         Relids          local_nonnullable;
1100                         Relids          pass_nonnullable;
1101
1102                         /*
1103                          * If this join is (now) inner, we can add any nonnullability
1104                          * constraints its quals provide to those we got from above. But
1105                          * if it is outer, we can only pass down the local constraints
1106                          * into the nullable side, because an outer join never eliminates
1107                          * any rows from its non-nullable side.  If it's a FULL join then
1108                          * it doesn't eliminate anything from either side.
1109                          */
1110                         if (jointype != JOIN_FULL)
1111                         {
1112                                 local_nonnullable = find_nonnullable_rels(j->quals);
1113                                 local_nonnullable = bms_add_members(local_nonnullable,
1114                                                                                                         nonnullable_rels);
1115                         }
1116                         else
1117                                 local_nonnullable = NULL;               /* no use in calculating it */
1118
1119                         if (left_state->contains_outer)
1120                         {
1121                                 if (jointype == JOIN_INNER || jointype == JOIN_RIGHT)
1122                                         pass_nonnullable = local_nonnullable;
1123                                 else
1124                                         pass_nonnullable = nonnullable_rels;
1125                                 reduce_outer_joins_pass2(j->larg, left_state, root,
1126                                                                                  pass_nonnullable);
1127                         }
1128                         if (right_state->contains_outer)
1129                         {
1130                                 if (jointype == JOIN_INNER || jointype == JOIN_LEFT)
1131                                         pass_nonnullable = local_nonnullable;
1132                                 else
1133                                         pass_nonnullable = nonnullable_rels;
1134                                 reduce_outer_joins_pass2(j->rarg, right_state, root,
1135                                                                                  pass_nonnullable);
1136                         }
1137                         bms_free(local_nonnullable);
1138                 }
1139         }
1140         else
1141                 elog(ERROR, "unrecognized node type: %d",
1142                          (int) nodeTag(jtnode));
1143 }
1144
1145 /*
1146  * fix_in_clause_relids: update RT-index sets of InClauseInfo nodes
1147  *
1148  * When we pull up a subquery, any InClauseInfo references to the subquery's
1149  * RT index have to be replaced by the set of substituted relids.
1150  *
1151  * We assume we may modify the InClauseInfo nodes in-place.
1152  */
1153 static void
1154 fix_in_clause_relids(List *in_info_list, int varno, Relids subrelids)
1155 {
1156         ListCell   *l;
1157
1158         foreach(l, in_info_list)
1159         {
1160                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
1161
1162                 if (bms_is_member(varno, ininfo->lefthand))
1163                 {
1164                         ininfo->lefthand = bms_del_member(ininfo->lefthand, varno);
1165                         ininfo->lefthand = bms_add_members(ininfo->lefthand, subrelids);
1166                 }
1167                 if (bms_is_member(varno, ininfo->righthand))
1168                 {
1169                         ininfo->righthand = bms_del_member(ininfo->righthand, varno);
1170                         ininfo->righthand = bms_add_members(ininfo->righthand, subrelids);
1171                 }
1172         }
1173 }
1174
1175 /*
1176  * fix_append_rel_relids: update RT-index fields of AppendRelInfo nodes
1177  *
1178  * When we pull up a subquery, any AppendRelInfo references to the subquery's
1179  * RT index have to be replaced by the substituted relid (and there had better
1180  * be only one).
1181  *
1182  * We assume we may modify the AppendRelInfo nodes in-place.
1183  */
1184 static void
1185 fix_append_rel_relids(List *append_rel_list, int varno, Relids subrelids)
1186 {
1187         ListCell   *l;
1188         int                     subvarno = -1;
1189
1190         /*
1191          * We only want to extract the member relid once, but we mustn't fail
1192          * immediately if there are multiple members; it could be that none of the
1193          * AppendRelInfo nodes refer to it.  So compute it on first use. Note that
1194          * bms_singleton_member will complain if set is not singleton.
1195          */
1196         foreach(l, append_rel_list)
1197         {
1198                 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
1199
1200                 /* The parent_relid shouldn't ever be a pullup target */
1201                 Assert(appinfo->parent_relid != varno);
1202
1203                 if (appinfo->child_relid == varno)
1204                 {
1205                         if (subvarno < 0)
1206                                 subvarno = bms_singleton_member(subrelids);
1207                         appinfo->child_relid = subvarno;
1208                 }
1209         }
1210 }
1211
1212 /*
1213  * get_relids_in_jointree: get set of base RT indexes present in a jointree
1214  */
1215 Relids
1216 get_relids_in_jointree(Node *jtnode)
1217 {
1218         Relids          result = NULL;
1219
1220         if (jtnode == NULL)
1221                 return result;
1222         if (IsA(jtnode, RangeTblRef))
1223         {
1224                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1225
1226                 result = bms_make_singleton(varno);
1227         }
1228         else if (IsA(jtnode, FromExpr))
1229         {
1230                 FromExpr   *f = (FromExpr *) jtnode;
1231                 ListCell   *l;
1232
1233                 foreach(l, f->fromlist)
1234                 {
1235                         result = bms_join(result,
1236                                                           get_relids_in_jointree(lfirst(l)));
1237                 }
1238         }
1239         else if (IsA(jtnode, JoinExpr))
1240         {
1241                 JoinExpr   *j = (JoinExpr *) jtnode;
1242
1243                 /* join's own RT index is not wanted in result */
1244                 result = get_relids_in_jointree(j->larg);
1245                 result = bms_join(result, get_relids_in_jointree(j->rarg));
1246         }
1247         else
1248                 elog(ERROR, "unrecognized node type: %d",
1249                          (int) nodeTag(jtnode));
1250         return result;
1251 }
1252
1253 /*
1254  * get_relids_for_join: get set of base RT indexes making up a join
1255  */
1256 Relids
1257 get_relids_for_join(PlannerInfo *root, int joinrelid)
1258 {
1259         Node       *jtnode;
1260
1261         jtnode = find_jointree_node_for_rel((Node *) root->parse->jointree,
1262                                                                                 joinrelid);
1263         if (!jtnode)
1264                 elog(ERROR, "could not find join node %d", joinrelid);
1265         return get_relids_in_jointree(jtnode);
1266 }
1267
1268 /*
1269  * find_jointree_node_for_rel: locate jointree node for a base or join RT index
1270  *
1271  * Returns NULL if not found
1272  */
1273 static Node *
1274 find_jointree_node_for_rel(Node *jtnode, int relid)
1275 {
1276         if (jtnode == NULL)
1277                 return NULL;
1278         if (IsA(jtnode, RangeTblRef))
1279         {
1280                 int                     varno = ((RangeTblRef *) jtnode)->rtindex;
1281
1282                 if (relid == varno)
1283                         return jtnode;
1284         }
1285         else if (IsA(jtnode, FromExpr))
1286         {
1287                 FromExpr   *f = (FromExpr *) jtnode;
1288                 ListCell   *l;
1289
1290                 foreach(l, f->fromlist)
1291                 {
1292                         jtnode = find_jointree_node_for_rel(lfirst(l), relid);
1293                         if (jtnode)
1294                                 return jtnode;
1295                 }
1296         }
1297         else if (IsA(jtnode, JoinExpr))
1298         {
1299                 JoinExpr   *j = (JoinExpr *) jtnode;
1300
1301                 if (relid == j->rtindex)
1302                         return jtnode;
1303                 jtnode = find_jointree_node_for_rel(j->larg, relid);
1304                 if (jtnode)
1305                         return jtnode;
1306                 jtnode = find_jointree_node_for_rel(j->rarg, relid);
1307                 if (jtnode)
1308                         return jtnode;
1309         }
1310         else
1311                 elog(ERROR, "unrecognized node type: %d",
1312                          (int) nodeTag(jtnode));
1313         return NULL;
1314 }