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