1 /*------------------------------------------------------------------------- 2 * 3 * relnode.c 4 * Relation-node lookup/construction routines 5 * 6 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group 7 * Portions Copyright (c) 1994, Regents of the University of California 8 * 9 * 10 * IDENTIFICATION 11 * src/backend/optimizer/util/relnode.c 12 * 13 *------------------------------------------------------------------------- 14 */ 15 #include "postgres.h" 16 17 #include <limits.h> 18 19 #include "miscadmin.h" 20 #include "optimizer/appendinfo.h" 21 #include "optimizer/clauses.h" 22 #include "optimizer/cost.h" 23 #include "optimizer/inherit.h" 24 #include "optimizer/pathnode.h" 25 #include "optimizer/paths.h" 26 #include "optimizer/placeholder.h" 27 #include "optimizer/plancat.h" 28 #include "optimizer/restrictinfo.h" 29 #include "optimizer/tlist.h" 30 #include "partitioning/partbounds.h" 31 #include "utils/hsearch.h" 32 33 34 typedef struct JoinHashEntry 35 { 36 Relids join_relids; /* hash key --- MUST BE FIRST */ 37 RelOptInfo *join_rel; 38 } JoinHashEntry; 39 40 static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, 41 RelOptInfo *input_rel); 42 static List *build_joinrel_restrictlist(PlannerInfo *root, 43 RelOptInfo *joinrel, 44 RelOptInfo *outer_rel, 45 RelOptInfo *inner_rel); 46 static void build_joinrel_joinlist(RelOptInfo *joinrel, 47 RelOptInfo *outer_rel, 48 RelOptInfo *inner_rel); 49 static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel, 50 List *joininfo_list, 51 List *new_restrictlist); 52 static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel, 53 List *joininfo_list, 54 List *new_joininfo); 55 static void set_foreign_rel_properties(RelOptInfo *joinrel, 56 RelOptInfo *outer_rel, RelOptInfo *inner_rel); 57 static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel); 58 static void build_joinrel_partition_info(RelOptInfo *joinrel, 59 RelOptInfo *outer_rel, RelOptInfo *inner_rel, 60 List *restrictlist, JoinType jointype); 61 static void build_child_join_reltarget(PlannerInfo *root, 62 RelOptInfo *parentrel, 63 RelOptInfo *childrel, 64 int nappinfos, 65 AppendRelInfo **appinfos); 66 67 68 /* 69 * setup_simple_rel_arrays 70 * Prepare the arrays we use for quickly accessing base relations. 71 */ 72 void 73 setup_simple_rel_arrays(PlannerInfo *root) 74 { 75 Index rti; 76 ListCell *lc; 77 78 /* Arrays are accessed using RT indexes (1..N) */ 79 root->simple_rel_array_size = list_length(root->parse->rtable) + 1; 80 81 /* simple_rel_array is initialized to all NULLs */ 82 root->simple_rel_array = (RelOptInfo **) 83 palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *)); 84 85 /* simple_rte_array is an array equivalent of the rtable list */ 86 root->simple_rte_array = (RangeTblEntry **) 87 palloc0(root->simple_rel_array_size * sizeof(RangeTblEntry *)); 88 rti = 1; 89 foreach(lc, root->parse->rtable) 90 { 91 RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc); 92 93 root->simple_rte_array[rti++] = rte; 94 } 95 } 96 97 /* 98 * setup_append_rel_array 99 * Populate the append_rel_array to allow direct lookups of 100 * AppendRelInfos by child relid. 101 * 102 * The array remains unallocated if there are no AppendRelInfos. 103 */ 104 void 105 setup_append_rel_array(PlannerInfo *root) 106 { 107 ListCell *lc; 108 int size = list_length(root->parse->rtable) + 1; 109 110 if (root->append_rel_list == NIL) 111 { 112 root->append_rel_array = NULL; 113 return; 114 } 115 116 root->append_rel_array = (AppendRelInfo **) 117 palloc0(size * sizeof(AppendRelInfo *)); 118 119 foreach(lc, root->append_rel_list) 120 { 121 AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc); 122 int child_relid = appinfo->child_relid; 123 124 /* Sanity check */ 125 Assert(child_relid < size); 126 127 if (root->append_rel_array[child_relid]) 128 elog(ERROR, "child relation already exists"); 129 130 root->append_rel_array[child_relid] = appinfo; 131 } 132 } 133 134 /* 135 * expand_planner_arrays 136 * Expand the PlannerInfo's per-RTE arrays by add_size members 137 * and initialize the newly added entries to NULLs 138 */ 139 void 140 expand_planner_arrays(PlannerInfo *root, int add_size) 141 { 142 int new_size; 143 144 Assert(add_size > 0); 145 146 new_size = root->simple_rel_array_size + add_size; 147 148 root->simple_rte_array = (RangeTblEntry **) 149 repalloc(root->simple_rte_array, 150 sizeof(RangeTblEntry *) * new_size); 151 MemSet(root->simple_rte_array + root->simple_rel_array_size, 152 0, sizeof(RangeTblEntry *) * add_size); 153 154 root->simple_rel_array = (RelOptInfo **) 155 repalloc(root->simple_rel_array, 156 sizeof(RelOptInfo *) * new_size); 157 MemSet(root->simple_rel_array + root->simple_rel_array_size, 158 0, sizeof(RelOptInfo *) * add_size); 159 160 if (root->append_rel_array) 161 { 162 root->append_rel_array = (AppendRelInfo **) 163 repalloc(root->append_rel_array, 164 sizeof(AppendRelInfo *) * new_size); 165 MemSet(root->append_rel_array + root->simple_rel_array_size, 166 0, sizeof(AppendRelInfo *) * add_size); 167 } 168 else 169 { 170 root->append_rel_array = (AppendRelInfo **) 171 palloc0(sizeof(AppendRelInfo *) * new_size); 172 } 173 174 root->simple_rel_array_size = new_size; 175 } 176 177 /* 178 * build_simple_rel 179 * Construct a new RelOptInfo for a base relation or 'other' relation. 180 */ 181 RelOptInfo * 182 build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent) 183 { 184 RelOptInfo *rel; 185 RangeTblEntry *rte; 186 187 /* Rel should not exist already */ 188 Assert(relid > 0 && relid < root->simple_rel_array_size); 189 if (root->simple_rel_array[relid] != NULL) 190 elog(ERROR, "rel %d already exists", relid); 191 192 /* Fetch RTE for relation */ 193 rte = root->simple_rte_array[relid]; 194 Assert(rte != NULL); 195 196 rel = makeNode(RelOptInfo); 197 rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL; 198 rel->relids = bms_make_singleton(relid); 199 rel->rows = 0; 200 /* cheap startup cost is interesting iff not all tuples to be retrieved */ 201 rel->consider_startup = (root->tuple_fraction > 0); 202 rel->consider_param_startup = false; /* might get changed later */ 203 rel->consider_parallel = false; /* might get changed later */ 204 rel->reltarget = create_empty_pathtarget(); 205 rel->pathlist = NIL; 206 rel->ppilist = NIL; 207 rel->partial_pathlist = NIL; 208 rel->cheapest_startup_path = NULL; 209 rel->cheapest_total_path = NULL; 210 rel->cheapest_unique_path = NULL; 211 rel->cheapest_parameterized_paths = NIL; 212 rel->relid = relid; 213 rel->rtekind = rte->rtekind; 214 /* min_attr, max_attr, attr_needed, attr_widths are set below */ 215 rel->lateral_vars = NIL; 216 rel->indexlist = NIL; 217 rel->statlist = NIL; 218 rel->pages = 0; 219 rel->tuples = 0; 220 rel->allvisfrac = 0; 221 rel->subroot = NULL; 222 rel->subplan_params = NIL; 223 rel->rel_parallel_workers = -1; /* set up in get_relation_info */ 224 rel->serverid = InvalidOid; 225 rel->userid = rte->checkAsUser; 226 rel->useridiscurrent = false; 227 rel->fdwroutine = NULL; 228 rel->fdw_private = NULL; 229 rel->unique_for_rels = NIL; 230 rel->non_unique_for_rels = NIL; 231 rel->baserestrictinfo = NIL; 232 rel->baserestrictcost.startup = 0; 233 rel->baserestrictcost.per_tuple = 0; 234 rel->baserestrict_min_security = UINT_MAX; 235 rel->joininfo = NIL; 236 rel->has_eclass_joins = false; 237 rel->consider_partitionwise_join = false; /* might get changed later */ 238 rel->part_scheme = NULL; 239 rel->nparts = 0; 240 rel->boundinfo = NULL; 241 rel->partition_qual = NIL; 242 rel->part_rels = NULL; 243 rel->partexprs = NULL; 244 rel->nullable_partexprs = NULL; 245 rel->partitioned_child_rels = NIL; 246 247 /* 248 * Pass assorted information down the inheritance hierarchy. 249 */ 250 if (parent) 251 { 252 /* 253 * Each direct or indirect child wants to know the relids of its 254 * topmost parent. 255 */ 256 if (parent->top_parent_relids) 257 rel->top_parent_relids = parent->top_parent_relids; 258 else 259 rel->top_parent_relids = bms_copy(parent->relids); 260 261 /* 262 * Also propagate lateral-reference information from appendrel parent 263 * rels to their child rels. We intentionally give each child rel the 264 * same minimum parameterization, even though it's quite possible that 265 * some don't reference all the lateral rels. This is because any 266 * append path for the parent will have to have the same 267 * parameterization for every child anyway, and there's no value in 268 * forcing extra reparameterize_path() calls. Similarly, a lateral 269 * reference to the parent prevents use of otherwise-movable join rels 270 * for each child. 271 * 272 * It's possible for child rels to have their own children, in which 273 * case the topmost parent's lateral info propagates all the way down. 274 */ 275 rel->direct_lateral_relids = parent->direct_lateral_relids; 276 rel->lateral_relids = parent->lateral_relids; 277 rel->lateral_referencers = parent->lateral_referencers; 278 } 279 else 280 { 281 rel->top_parent_relids = NULL; 282 rel->direct_lateral_relids = NULL; 283 rel->lateral_relids = NULL; 284 rel->lateral_referencers = NULL; 285 } 286 287 /* Check type of rtable entry */ 288 switch (rte->rtekind) 289 { 290 case RTE_RELATION: 291 /* Table --- retrieve statistics from the system catalogs */ 292 get_relation_info(root, rte->relid, rte->inh, rel); 293 break; 294 case RTE_SUBQUERY: 295 case RTE_FUNCTION: 296 case RTE_TABLEFUNC: 297 case RTE_VALUES: 298 case RTE_CTE: 299 case RTE_NAMEDTUPLESTORE: 300 301 /* 302 * Subquery, function, tablefunc, values list, CTE, or ENR --- set 303 * up attr range and arrays 304 * 305 * Note: 0 is included in range to support whole-row Vars 306 */ 307 rel->min_attr = 0; 308 rel->max_attr = list_length(rte->eref->colnames); 309 rel->attr_needed = (Relids *) 310 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids)); 311 rel->attr_widths = (int32 *) 312 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32)); 313 break; 314 case RTE_RESULT: 315 /* RTE_RESULT has no columns, nor could it have whole-row Var */ 316 rel->min_attr = 0; 317 rel->max_attr = -1; 318 rel->attr_needed = NULL; 319 rel->attr_widths = NULL; 320 break; 321 default: 322 elog(ERROR, "unrecognized RTE kind: %d", 323 (int) rte->rtekind); 324 break; 325 } 326 327 /* 328 * Copy the parent's quals to the child, with appropriate substitution of 329 * variables. If any constant false or NULL clauses turn up, we can mark 330 * the child as dummy right away. (We must do this immediately so that 331 * pruning works correctly when recursing in expand_partitioned_rtentry.) 332 */ 333 if (parent) 334 { 335 AppendRelInfo *appinfo = root->append_rel_array[relid]; 336 337 Assert(appinfo != NULL); 338 if (!apply_child_basequals(root, parent, rel, rte, appinfo)) 339 { 340 /* 341 * Some restriction clause reduced to constant FALSE or NULL after 342 * substitution, so this child need not be scanned. 343 */ 344 mark_dummy_rel(rel); 345 } 346 } 347 348 /* Save the finished struct in the query's simple_rel_array */ 349 root->simple_rel_array[relid] = rel; 350 351 return rel; 352 } 353 354 /* 355 * find_base_rel 356 * Find a base or other relation entry, which must already exist. 357 */ 358 RelOptInfo * 359 find_base_rel(PlannerInfo *root, int relid) 360 { 361 RelOptInfo *rel; 362 363 Assert(relid > 0); 364 365 if (relid < root->simple_rel_array_size) 366 { 367 rel = root->simple_rel_array[relid]; 368 if (rel) 369 return rel; 370 } 371 372 elog(ERROR, "no relation entry for relid %d", relid); 373 374 return NULL; /* keep compiler quiet */ 375 } 376 377 /* 378 * build_join_rel_hash 379 * Construct the auxiliary hash table for join relations. 380 */ 381 static void 382 build_join_rel_hash(PlannerInfo *root) 383 { 384 HTAB *hashtab; 385 HASHCTL hash_ctl; 386 ListCell *l; 387 388 /* Create the hash table */ 389 MemSet(&hash_ctl, 0, sizeof(hash_ctl)); 390 hash_ctl.keysize = sizeof(Relids); 391 hash_ctl.entrysize = sizeof(JoinHashEntry); 392 hash_ctl.hash = bitmap_hash; 393 hash_ctl.match = bitmap_match; 394 hash_ctl.hcxt = CurrentMemoryContext; 395 hashtab = hash_create("JoinRelHashTable", 396 256L, 397 &hash_ctl, 398 HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); 399 400 /* Insert all the already-existing joinrels */ 401 foreach(l, root->join_rel_list) 402 { 403 RelOptInfo *rel = (RelOptInfo *) lfirst(l); 404 JoinHashEntry *hentry; 405 bool found; 406 407 hentry = (JoinHashEntry *) hash_search(hashtab, 408 &(rel->relids), 409 HASH_ENTER, 410 &found); 411 Assert(!found); 412 hentry->join_rel = rel; 413 } 414 415 root->join_rel_hash = hashtab; 416 } 417 418 /* 419 * find_join_rel 420 * Returns relation entry corresponding to 'relids' (a set of RT indexes), 421 * or NULL if none exists. This is for join relations. 422 */ 423 RelOptInfo * 424 find_join_rel(PlannerInfo *root, Relids relids) 425 { 426 /* 427 * Switch to using hash lookup when list grows "too long". The threshold 428 * is arbitrary and is known only here. 429 */ 430 if (!root->join_rel_hash && list_length(root->join_rel_list) > 32) 431 build_join_rel_hash(root); 432 433 /* 434 * Use either hashtable lookup or linear search, as appropriate. 435 * 436 * Note: the seemingly redundant hashkey variable is used to avoid taking 437 * the address of relids; unless the compiler is exceedingly smart, doing 438 * so would force relids out of a register and thus probably slow down the 439 * list-search case. 440 */ 441 if (root->join_rel_hash) 442 { 443 Relids hashkey = relids; 444 JoinHashEntry *hentry; 445 446 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, 447 &hashkey, 448 HASH_FIND, 449 NULL); 450 if (hentry) 451 return hentry->join_rel; 452 } 453 else 454 { 455 ListCell *l; 456 457 foreach(l, root->join_rel_list) 458 { 459 RelOptInfo *rel = (RelOptInfo *) lfirst(l); 460 461 if (bms_equal(rel->relids, relids)) 462 return rel; 463 } 464 } 465 466 return NULL; 467 } 468 469 /* 470 * set_foreign_rel_properties 471 * Set up foreign-join fields if outer and inner relation are foreign 472 * tables (or joins) belonging to the same server and assigned to the same 473 * user to check access permissions as. 474 * 475 * In addition to an exact match of userid, we allow the case where one side 476 * has zero userid (implying current user) and the other side has explicit 477 * userid that happens to equal the current user; but in that case, pushdown of 478 * the join is only valid for the current user. The useridiscurrent field 479 * records whether we had to make such an assumption for this join or any 480 * sub-join. 481 * 482 * Otherwise these fields are left invalid, so GetForeignJoinPaths will not be 483 * called for the join relation. 484 * 485 */ 486 static void 487 set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, 488 RelOptInfo *inner_rel) 489 { 490 if (OidIsValid(outer_rel->serverid) && 491 inner_rel->serverid == outer_rel->serverid) 492 { 493 if (inner_rel->userid == outer_rel->userid) 494 { 495 joinrel->serverid = outer_rel->serverid; 496 joinrel->userid = outer_rel->userid; 497 joinrel->useridiscurrent = outer_rel->useridiscurrent || inner_rel->useridiscurrent; 498 joinrel->fdwroutine = outer_rel->fdwroutine; 499 } 500 else if (!OidIsValid(inner_rel->userid) && 501 outer_rel->userid == GetUserId()) 502 { 503 joinrel->serverid = outer_rel->serverid; 504 joinrel->userid = outer_rel->userid; 505 joinrel->useridiscurrent = true; 506 joinrel->fdwroutine = outer_rel->fdwroutine; 507 } 508 else if (!OidIsValid(outer_rel->userid) && 509 inner_rel->userid == GetUserId()) 510 { 511 joinrel->serverid = outer_rel->serverid; 512 joinrel->userid = inner_rel->userid; 513 joinrel->useridiscurrent = true; 514 joinrel->fdwroutine = outer_rel->fdwroutine; 515 } 516 } 517 } 518 519 /* 520 * add_join_rel 521 * Add given join relation to the list of join relations in the given 522 * PlannerInfo. Also add it to the auxiliary hashtable if there is one. 523 */ 524 static void 525 add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) 526 { 527 /* GEQO requires us to append the new joinrel to the end of the list! */ 528 root->join_rel_list = lappend(root->join_rel_list, joinrel); 529 530 /* store it into the auxiliary hashtable if there is one. */ 531 if (root->join_rel_hash) 532 { 533 JoinHashEntry *hentry; 534 bool found; 535 536 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, 537 &(joinrel->relids), 538 HASH_ENTER, 539 &found); 540 Assert(!found); 541 hentry->join_rel = joinrel; 542 } 543 } 544 545 /* 546 * build_join_rel 547 * Returns relation entry corresponding to the union of two given rels, 548 * creating a new relation entry if none already exists. 549 * 550 * 'joinrelids' is the Relids set that uniquely identifies the join 551 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be 552 * joined 553 * 'sjinfo': join context info 554 * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr 555 * receives the list of RestrictInfo nodes that apply to this 556 * particular pair of joinable relations. 557 * 558 * restrictlist_ptr makes the routine's API a little grotty, but it saves 559 * duplicated calculation of the restrictlist... 560 */ 561 RelOptInfo * 562 build_join_rel(PlannerInfo *root, 563 Relids joinrelids, 564 RelOptInfo *outer_rel, 565 RelOptInfo *inner_rel, 566 SpecialJoinInfo *sjinfo, 567 List **restrictlist_ptr) 568 { 569 RelOptInfo *joinrel; 570 List *restrictlist; 571 572 /* This function should be used only for join between parents. */ 573 Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel)); 574 575 /* 576 * See if we already have a joinrel for this set of base rels. 577 */ 578 joinrel = find_join_rel(root, joinrelids); 579 580 if (joinrel) 581 { 582 /* 583 * Yes, so we only need to figure the restrictlist for this particular 584 * pair of component relations. 585 */ 586 if (restrictlist_ptr) 587 *restrictlist_ptr = build_joinrel_restrictlist(root, 588 joinrel, 589 outer_rel, 590 inner_rel); 591 return joinrel; 592 } 593 594 /* 595 * Nope, so make one. 596 */ 597 joinrel = makeNode(RelOptInfo); 598 joinrel->reloptkind = RELOPT_JOINREL; 599 joinrel->relids = bms_copy(joinrelids); 600 joinrel->rows = 0; 601 /* cheap startup cost is interesting iff not all tuples to be retrieved */ 602 joinrel->consider_startup = (root->tuple_fraction > 0); 603 joinrel->consider_param_startup = false; 604 joinrel->consider_parallel = false; 605 joinrel->reltarget = create_empty_pathtarget(); 606 joinrel->pathlist = NIL; 607 joinrel->ppilist = NIL; 608 joinrel->partial_pathlist = NIL; 609 joinrel->cheapest_startup_path = NULL; 610 joinrel->cheapest_total_path = NULL; 611 joinrel->cheapest_unique_path = NULL; 612 joinrel->cheapest_parameterized_paths = NIL; 613 /* init direct_lateral_relids from children; we'll finish it up below */ 614 joinrel->direct_lateral_relids = 615 bms_union(outer_rel->direct_lateral_relids, 616 inner_rel->direct_lateral_relids); 617 joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids, 618 outer_rel, inner_rel); 619 joinrel->relid = 0; /* indicates not a baserel */ 620 joinrel->rtekind = RTE_JOIN; 621 joinrel->min_attr = 0; 622 joinrel->max_attr = 0; 623 joinrel->attr_needed = NULL; 624 joinrel->attr_widths = NULL; 625 joinrel->lateral_vars = NIL; 626 joinrel->lateral_referencers = NULL; 627 joinrel->indexlist = NIL; 628 joinrel->statlist = NIL; 629 joinrel->pages = 0; 630 joinrel->tuples = 0; 631 joinrel->allvisfrac = 0; 632 joinrel->subroot = NULL; 633 joinrel->subplan_params = NIL; 634 joinrel->rel_parallel_workers = -1; 635 joinrel->serverid = InvalidOid; 636 joinrel->userid = InvalidOid; 637 joinrel->useridiscurrent = false; 638 joinrel->fdwroutine = NULL; 639 joinrel->fdw_private = NULL; 640 joinrel->unique_for_rels = NIL; 641 joinrel->non_unique_for_rels = NIL; 642 joinrel->baserestrictinfo = NIL; 643 joinrel->baserestrictcost.startup = 0; 644 joinrel->baserestrictcost.per_tuple = 0; 645 joinrel->baserestrict_min_security = UINT_MAX; 646 joinrel->joininfo = NIL; 647 joinrel->has_eclass_joins = false; 648 joinrel->consider_partitionwise_join = false; /* might get changed later */ 649 joinrel->top_parent_relids = NULL; 650 joinrel->part_scheme = NULL; ioctl(fd: ::c_int, request: ::c_int, ...) -> ::c_int651 joinrel->nparts = 0; 652 joinrel->boundinfo = NULL; 653 joinrel->partition_qual = NIL; 654 joinrel->part_rels = NULL; 655 joinrel->partexprs = NULL; 656 joinrel->nullable_partexprs = NULL; 657 joinrel->partitioned_child_rels = NIL; 658 659 /* Compute information relevant to the foreign relations. */ 660 set_foreign_rel_properties(joinrel, outer_rel, inner_rel); 661 662 /* 663 * Create a new tlist containing just the vars that need to be output from 664 * this join (ie, are needed for higher joinclauses or final output). 665 * 666 * NOTE: the tlist order for a join rel will depend on which pair of outer 667 * and inner rels we first try to build it from. But the contents should 668 * be the same regardless. 669 */ 670 build_joinrel_tlist(root, joinrel, outer_rel); 671 build_joinrel_tlist(root, joinrel, inner_rel); 672 add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel); 673 674 /* 675 * add_placeholders_to_joinrel also took care of adding the ph_lateral 676 * sets of any PlaceHolderVars computed here to direct_lateral_relids, so 677 * now we can finish computing that. This is much like the computation of 678 * the transitively-closed lateral_relids in min_join_parameterization, 679 * except that here we *do* have to consider the added PHVs. 680 */ 681 joinrel->direct_lateral_relids = 682 bms_del_members(joinrel->direct_lateral_relids, joinrel->relids); 683 if (bms_is_empty(joinrel->direct_lateral_relids)) 684 joinrel->direct_lateral_relids = NULL; 685 686 /* 687 * Construct restrict and join clause lists for the new joinrel. (The 688 * caller might or might not need the restrictlist, but I need it anyway 689 * for set_joinrel_size_estimates().) 690 */ 691 restrictlist = build_joinrel_restrictlist(root, joinrel, 692 outer_rel, inner_rel); 693 if (restrictlist_ptr) 694 *restrictlist_ptr = restrictlist; 695 build_joinrel_joinlist(joinrel, outer_rel, inner_rel); 696 697 /* 698 * This is also the right place to check whether the joinrel has any 699 * pending EquivalenceClass joins. 700 */ 701 joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel); 702 703 /* Store the partition information. */ 704 build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist, 705 sjinfo->jointype); 706 707 /* 708 * Set estimates of the joinrel's size. 709 */ 710 set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, 711 sjinfo, restrictlist); 712 713 /* 714 * Set the consider_parallel flag if this joinrel could potentially be 715 * scanned within a parallel worker. If this flag is false for either 716 * inner_rel or outer_rel, then it must be false for the joinrel also. 717 * Even if both are true, there might be parallel-restricted expressions 718 * in the targetlist or quals. 719 * 720 * Note that if there are more than two rels in this relation, they could 721 * be divided between inner_rel and outer_rel in any arbitrary way. We 722 * assume this doesn't matter, because we should hit all the same baserels 723 * and joinclauses while building up to this joinrel no matter which we 724 * take; therefore, we should make the same decision here however we get 725 * here. 726 */ 727 if (inner_rel->consider_parallel && outer_rel->consider_parallel && 728 is_parallel_safe(root, (Node *) restrictlist) && 729 is_parallel_safe(root, (Node *) joinrel->reltarget->exprs)) 730 joinrel->consider_parallel = true; 731 732 /* Add the joinrel to the PlannerInfo. */ 733 add_join_rel(root, joinrel); 734 735 /* 736 * Also, if dynamic-programming join search is active, add the new joinrel 737 * to the appropriate sublist. Note: you might think the Assert on number 738 * of members should be for equality, but some of the level 1 rels might 739 * have been joinrels already, so we can only assert <=. 740 */ 741 if (root->join_rel_level) 742 { 743 Assert(root->join_cur_level > 0); 744 Assert(root->join_cur_level <= bms_num_members(joinrel->relids)); 745 root->join_rel_level[root->join_cur_level] = 746 lappend(root->join_rel_level[root->join_cur_level], joinrel); 747 } 748 749 return joinrel; 750 } 751 752 /* 753 * build_child_join_rel 754 * Builds RelOptInfo representing join between given two child relations. 755 * 756 * 'outer_rel' and 'inner_rel' are the RelOptInfos of child relations being 757 * joined 758 * 'parent_joinrel' is the RelOptInfo representing the join between parent 759 * relations. Some of the members of new RelOptInfo are produced by 760 * translating corresponding members of this RelOptInfo 761 * 'sjinfo': child-join context info 762 * 'restrictlist': list of RestrictInfo nodes that apply to this particular 763 * pair of joinable relations 764 * 'jointype' is the join type (inner, left, full, etc) 765 */ 766 RelOptInfo * 767 build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, 768 RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, 769 List *restrictlist, SpecialJoinInfo *sjinfo, 770 JoinType jointype) 771 { 772 RelOptInfo *joinrel = makeNode(RelOptInfo); 773 AppendRelInfo **appinfos; 774 int nappinfos; 775 776 /* Only joins between "other" relations land here. */ 777 Assert(IS_OTHER_REL(outer_rel) && IS_OTHER_REL(inner_rel)); 778 779 /* The parent joinrel should have consider_partitionwise_join set. */ 780 Assert(parent_joinrel->consider_partitionwise_join); 781 782 joinrel->reloptkind = RELOPT_OTHER_JOINREL; 783 joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids); 784 joinrel->rows = 0; 785 /* cheap startup cost is interesting iff not all tuples to be retrieved */ 786 joinrel->consider_startup = (root->tuple_fraction > 0); 787 joinrel->consider_param_startup = false; 788 joinrel->consider_parallel = false; 789 joinrel->reltarget = create_empty_pathtarget(); 790 joinrel->pathlist = NIL; 791 joinrel->ppilist = NIL; 792 joinrel->partial_pathlist = NIL; 793 joinrel->cheapest_startup_path = NULL; 794 joinrel->cheapest_total_path = NULL; 795 joinrel->cheapest_unique_path = NULL; 796 joinrel->cheapest_parameterized_paths = NIL; 797 joinrel->direct_lateral_relids = NULL; 798 joinrel->lateral_relids = NULL; 799 joinrel->relid = 0; /* indicates not a baserel */ 800 joinrel->rtekind = RTE_JOIN; 801 joinrel->min_attr = 0; 802 joinrel->max_attr = 0; 803 joinrel->attr_needed = NULL; 804 joinrel->attr_widths = NULL; 805 joinrel->lateral_vars = NIL; 806 joinrel->lateral_referencers = NULL; 807 joinrel->indexlist = NIL; 808 joinrel->pages = 0; 809 joinrel->tuples = 0; 810 joinrel->allvisfrac = 0; 811 joinrel->subroot = NULL; 812 joinrel->subplan_params = NIL; 813 joinrel->serverid = InvalidOid; 814 joinrel->userid = InvalidOid; 815 joinrel->useridiscurrent = false; 816 joinrel->fdwroutine = NULL; 817 joinrel->fdw_private = NULL; 818 joinrel->baserestrictinfo = NIL; 819 joinrel->baserestrictcost.startup = 0; 820 joinrel->baserestrictcost.per_tuple = 0; 821 joinrel->joininfo = NIL; 822 joinrel->has_eclass_joins = false; 823 joinrel->consider_partitionwise_join = false; /* might get changed later */ 824 joinrel->top_parent_relids = NULL; 825 joinrel->part_scheme = NULL; 826 joinrel->nparts = 0; 827 joinrel->boundinfo = NULL; 828 joinrel->partition_qual = NIL; 829 joinrel->part_rels = NULL; 830 joinrel->partexprs = NULL; 831 joinrel->nullable_partexprs = NULL; 832 joinrel->partitioned_child_rels = NIL; 833 834 joinrel->top_parent_relids = bms_union(outer_rel->top_parent_relids, 835 inner_rel->top_parent_relids); 836 837 /* Compute information relevant to foreign relations. */ 838 set_foreign_rel_properties(joinrel, outer_rel, inner_rel); 839 840 /* Compute information needed for mapping Vars to the child rel */ 841 appinfos = find_appinfos_by_relids(root, joinrel->relids, &nappinfos); 842 843 /* Set up reltarget struct */ 844 build_child_join_reltarget(root, parent_joinrel, joinrel, 845 nappinfos, appinfos); 846 847 /* Construct joininfo list. */ 848 joinrel->joininfo = (List *) adjust_appendrel_attrs(root, 849 (Node *) parent_joinrel->joininfo, 850 nappinfos, 851 appinfos); 852 853 /* 854 * Lateral relids referred in child join will be same as that referred in 855 * the parent relation. Throw any partial result computed while building 856 * the targetlist. 857 */ 858 bms_free(joinrel->direct_lateral_relids); 859 bms_free(joinrel->lateral_relids); 860 joinrel->direct_lateral_relids = (Relids) bms_copy(parent_joinrel->direct_lateral_relids); 861 joinrel->lateral_relids = (Relids) bms_copy(parent_joinrel->lateral_relids); 862 863 /* 864 * If the parent joinrel has pending equivalence classes, so does the 865 * child. 866 */ 867 joinrel->has_eclass_joins = parent_joinrel->has_eclass_joins; 868 869 /* Is the join between partitions itself partitioned? */ 870 build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist, 871 jointype); 872 873 /* Child joinrel is parallel safe if parent is parallel safe. */ 874 joinrel->consider_parallel = parent_joinrel->consider_parallel; 875 876 /* Set estimates of the child-joinrel's size. */ 877 set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, 878 sjinfo, restrictlist); 879 880 /* We build the join only once. */ 881 Assert(!find_join_rel(root, joinrel->relids)); 882 883 /* Add the relation to the PlannerInfo. */ 884 add_join_rel(root, joinrel); 885 886 /* 887 * We might need EquivalenceClass members corresponding to the child join, 888 * so that we can represent sort pathkeys for it. As with children of 889 * baserels, we shouldn't need this unless there are relevant eclass joins 890 * (implying that a merge join might be possible) or pathkeys to sort by. 891 */ 892 if (joinrel->has_eclass_joins || has_useful_pathkeys(root, parent_joinrel)) 893 add_child_join_rel_equivalences(root, 894 nappinfos, appinfos, 895 parent_joinrel, joinrel); 896 897 pfree(appinfos); 898 899 return joinrel; 900 } 901 902 /* 903 * min_join_parameterization 904 * 905 * Determine the minimum possible parameterization of a joinrel, that is, the 906 * set of other rels it contains LATERAL references to. We save this value in 907 * the join's RelOptInfo. This function is split out of build_join_rel() 908 * because join_is_legal() needs the value to check a prospective join. 909 */ 910 Relids 911 min_join_parameterization(PlannerInfo *root, 912 Relids joinrelids, 913 RelOptInfo *outer_rel, 914 RelOptInfo *inner_rel) 915 { 916 Relids result; 917 918 /* 919 * Basically we just need the union of the inputs' lateral_relids, less 920 * whatever is already in the join. 921 * 922 * It's not immediately obvious that this is a valid way to compute the 923 * result, because it might seem that we're ignoring possible lateral refs 924 * of PlaceHolderVars that are due to be computed at the join but not in 925 * either input. However, because create_lateral_join_info() already 926 * charged all such PHV refs to each member baserel of the join, they'll 927 * be accounted for already in the inputs' lateral_relids. Likewise, we 928 * do not need to worry about doing transitive closure here, because that 929 * was already accounted for in the original baserel lateral_relids. 930 */ 931 result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids); 932 result = bms_del_members(result, joinrelids); 933 934 /* Maintain invariant that result is exactly NULL if empty */ 935 if (bms_is_empty(result)) 936 result = NULL; 937 938 return result; 939 } 940 941 /* 942 * build_joinrel_tlist 943 * Builds a join relation's target list from an input relation. 944 * (This is invoked twice to handle the two input relations.) 945 * 946 * The join's targetlist includes all Vars of its member relations that 947 * will still be needed above the join. This subroutine adds all such 948 * Vars from the specified input rel's tlist to the join rel's tlist. 949 * 950 * We also compute the expected width of the join's output, making use 951 * of data that was cached at the baserel level by set_rel_width(). 952 */ 953 static void 954 build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, 955 RelOptInfo *input_rel) 956 { 957 Relids relids = joinrel->relids; 958 ListCell *vars; 959 960 foreach(vars, input_rel->reltarget->exprs) 961 { 962 Var *var = (Var *) lfirst(vars); 963 RelOptInfo *baserel; 964 int ndx; 965 966 /* 967 * Ignore PlaceHolderVars in the input tlists; we'll make our own 968 * decisions about whether to copy them. 969 */ 970 if (IsA(var, PlaceHolderVar)) 971 continue; 972 973 /* 974 * Otherwise, anything in a baserel or joinrel targetlist ought to be 975 * a Var. (More general cases can only appear in appendrel child 976 * rels, which will never be seen here.) 977 */ 978 if (!IsA(var, Var)) 979 elog(ERROR, "unexpected node type in rel targetlist: %d", 980 (int) nodeTag(var)); 981 982 /* Get the Var's original base rel */ 983 baserel = find_base_rel(root, var->varno); 984 985 /* Is it still needed above this joinrel? */ 986 ndx = var->varattno - baserel->min_attr; 987 if (bms_nonempty_difference(baserel->attr_needed[ndx], relids)) 988 { 989 /* Yup, add it to the output */ 990 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, var); 991 /* Vars have cost zero, so no need to adjust reltarget->cost */ 992 joinrel->reltarget->width += baserel->attr_widths[ndx]; 993 } 994 } 995 } 996 997 /* 998 * build_joinrel_restrictlist 999 * build_joinrel_joinlist 1000 * These routines build lists of restriction and join clauses for a 1001 * join relation from the joininfo lists of the relations it joins. 1002 * 1003 * These routines are separate because the restriction list must be 1004 * built afresh for each pair of input sub-relations we consider, whereas 1005 * the join list need only be computed once for any join RelOptInfo. 1006 * The join list is fully determined by the set of rels making up the 1007 * joinrel, so we should get the same results (up to ordering) from any 1008 * candidate pair of sub-relations. But the restriction list is whatever 1009 * is not handled in the sub-relations, so it depends on which 1010 * sub-relations are considered. 1011 * 1012 * If a join clause from an input relation refers to base rels still not 1013 * present in the joinrel, then it is still a join clause for the joinrel; 1014 * we put it into the joininfo list for the joinrel. Otherwise, 1015 * the clause is now a restrict clause for the joined relation, and we 1016 * return it to the caller of build_joinrel_restrictlist() to be stored in 1017 * join paths made from this pair of sub-relations. (It will not need to 1018 * be considered further up the join tree.) 1019 * 1020 * In many cases we will find the same RestrictInfos in both input 1021 * relations' joinlists, so be careful to eliminate duplicates. 1022 * Pointer equality should be a sufficient test for dups, since all 1023 * the various joinlist entries ultimately refer to RestrictInfos 1024 * pushed into them by distribute_restrictinfo_to_rels(). 1025 * 1026 * 'joinrel' is a join relation node 1027 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined 1028 * to form joinrel. 1029 * 1030 * build_joinrel_restrictlist() returns a list of relevant restrictinfos, 1031 * whereas build_joinrel_joinlist() stores its results in the joinrel's 1032 * joininfo list. One or the other must accept each given clause! 1033 * 1034 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass 1035 * up to the join relation. I believe this is no longer necessary, because 1036 * RestrictInfo nodes are no longer context-dependent. Instead, just include 1037 * the original nodes in the lists made for the join relation. 1038 */ 1039 static List * 1040 build_joinrel_restrictlist(PlannerInfo *root, 1041 RelOptInfo *joinrel, 1042 RelOptInfo *outer_rel, 1043 RelOptInfo *inner_rel) 1044 { 1045 List *result; 1046 1047 /* 1048 * Collect all the clauses that syntactically belong at this level, 1049 * eliminating any duplicates (important since we will see many of the 1050 * same clauses arriving from both input relations). 1051 */ 1052 result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL); 1053 result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result); 1054 1055 /* 1056 * Add on any clauses derived from EquivalenceClasses. These cannot be 1057 * redundant with the clauses in the joininfo lists, so don't bother 1058 * checking. 1059 */ 1060 result = list_concat(result, 1061 generate_join_implied_equalities(root, 1062 joinrel->relids, 1063 outer_rel->relids, 1064 inner_rel)); 1065 1066 return result; 1067 } 1068 1069 static void 1070 build_joinrel_joinlist(RelOptInfo *joinrel, 1071 RelOptInfo *outer_rel, 1072 RelOptInfo *inner_rel) 1073 { 1074 List *result; 1075 1076 /* 1077 * Collect all the clauses that syntactically belong above this level, 1078 * eliminating any duplicates (important since we will see many of the 1079 * same clauses arriving from both input relations). 1080 */ 1081 result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL); 1082 result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result); 1083 1084 joinrel->joininfo = result; 1085 } 1086 1087 static List * 1088 subbuild_joinrel_restrictlist(RelOptInfo *joinrel, 1089 List *joininfo_list, 1090 List *new_restrictlist) 1091 { 1092 ListCell *l; 1093 1094 foreach(l, joininfo_list) 1095 { 1096 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); 1097 1098 if (bms_is_subset(rinfo->required_relids, joinrel->relids)) 1099 { 1100 /* 1101 * This clause becomes a restriction clause for the joinrel, since 1102 * it refers to no outside rels. Add it to the list, being 1103 * careful to eliminate duplicates. (Since RestrictInfo nodes in 1104 * different joinlists will have been multiply-linked rather than 1105 * copied, pointer equality should be a sufficient test.) 1106 */ 1107 new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo); 1108 } 1109 else 1110 { 1111 /* 1112 * This clause is still a join clause at this level, so we ignore 1113 * it in this routine. 1114 */ 1115 } 1116 } 1117 1118 return new_restrictlist; 1119 } 1120 1121 static List * 1122 subbuild_joinrel_joinlist(RelOptInfo *joinrel, 1123 List *joininfo_list, 1124 List *new_joininfo) 1125 { 1126 ListCell *l; 1127 1128 /* Expected to be called only for join between parent relations. */ 1129 Assert(joinrel->reloptkind == RELOPT_JOINREL); 1130 1131 foreach(l, joininfo_list) 1132 { 1133 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); 1134 1135 if (bms_is_subset(rinfo->required_relids, joinrel->relids)) 1136 { 1137 /* 1138 * This clause becomes a restriction clause for the joinrel, since 1139 * it refers to no outside rels. So we can ignore it in this 1140 * routine. 1141 */ 1142 } 1143 else 1144 { 1145 /* 1146 * This clause is still a join clause at this level, so add it to 1147 * the new joininfo list, being careful to eliminate duplicates. 1148 * (Since RestrictInfo nodes in different joinlists will have been 1149 * multiply-linked rather than copied, pointer equality should be 1150 * a sufficient test.) 1151 */ 1152 new_joininfo = list_append_unique_ptr(new_joininfo, rinfo); 1153 } 1154 } 1155 1156 return new_joininfo; 1157 } 1158 1159 1160 /* 1161 * fetch_upper_rel 1162 * Build a RelOptInfo describing some post-scan/join query processing, 1163 * or return a pre-existing one if somebody already built it. 1164 * 1165 * An "upper" relation is identified by an UpperRelationKind and a Relids set. 1166 * The meaning of the Relids set is not specified here, and very likely will 1167 * vary for different relation kinds. 1168 * 1169 * Most of the fields in an upper-level RelOptInfo are not used and are not 1170 * set here (though makeNode should ensure they're zeroes). We basically only 1171 * care about fields that are of interest to add_path() and set_cheapest(). 1172 */ 1173 RelOptInfo * 1174 fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) 1175 { 1176 RelOptInfo *upperrel; 1177 ListCell *lc; 1178 1179 /* 1180 * For the moment, our indexing data structure is just a List for each 1181 * relation kind. If we ever get so many of one kind that this stops 1182 * working well, we can improve it. No code outside this function should 1183 * assume anything about how to find a particular upperrel. 1184 */ 1185 1186 /* If we already made this upperrel for the query, return it */ 1187 foreach(lc, root->upper_rels[kind]) 1188 { 1189 upperrel = (RelOptInfo *) lfirst(lc); 1190 1191 if (bms_equal(upperrel->relids, relids)) 1192 return upperrel; 1193 } 1194 1195 upperrel = makeNode(RelOptInfo); 1196 upperrel->reloptkind = RELOPT_UPPER_REL; 1197 upperrel->relids = bms_copy(relids); 1198 1199 /* cheap startup cost is interesting iff not all tuples to be retrieved */ 1200 upperrel->consider_startup = (root->tuple_fraction > 0); 1201 upperrel->consider_param_startup = false; 1202 upperrel->consider_parallel = false; /* might get changed later */ 1203 upperrel->reltarget = create_empty_pathtarget(); 1204 upperrel->pathlist = NIL; 1205 upperrel->cheapest_startup_path = NULL; 1206 upperrel->cheapest_total_path = NULL; 1207 upperrel->cheapest_unique_path = NULL; 1208 upperrel->cheapest_parameterized_paths = NIL; 1209 1210 root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel); 1211 1212 return upperrel; 1213 } 1214 1215 1216 /* 1217 * find_childrel_parents 1218 * Compute the set of parent relids of an appendrel child rel. 1219 * 1220 * Since appendrels can be nested, a child could have multiple levels of 1221 * appendrel ancestors. This function computes a Relids set of all the 1222 * parent relation IDs. 1223 */ 1224 Relids 1225 find_childrel_parents(PlannerInfo *root, RelOptInfo *rel) 1226 { 1227 Relids result = NULL; 1228 1229 Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL); 1230 Assert(rel->relid > 0 && rel->relid < root->simple_rel_array_size); 1231 1232 do 1233 { 1234 AppendRelInfo *appinfo = root->append_rel_array[rel->relid]; 1235 Index prelid = appinfo->parent_relid; 1236 1237 result = bms_add_member(result, prelid); 1238 1239 /* traverse up to the parent rel, loop if it's also a child rel */ 1240 rel = find_base_rel(root, prelid); 1241 } while (rel->reloptkind == RELOPT_OTHER_MEMBER_REL); 1242 1243 Assert(rel->reloptkind == RELOPT_BASEREL); 1244 1245 return result; 1246 } 1247 1248 1249 /* 1250 * get_baserel_parampathinfo 1251 * Get the ParamPathInfo for a parameterized path for a base relation, 1252 * constructing one if we don't have one already. 1253 * 1254 * This centralizes estimating the rowcounts for parameterized paths. 1255 * We need to cache those to be sure we use the same rowcount for all paths 1256 * of the same parameterization for a given rel. This is also a convenient 1257 * place to determine which movable join clauses the parameterized path will 1258 * be responsible for evaluating. 1259 */ 1260 ParamPathInfo * 1261 get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel, 1262 Relids required_outer) 1263 { 1264 ParamPathInfo *ppi; 1265 Relids joinrelids; 1266 List *pclauses; 1267 double rows; 1268 ListCell *lc; 1269 1270 /* If rel has LATERAL refs, every path for it should account for them */ 1271 Assert(bms_is_subset(baserel->lateral_relids, required_outer)); 1272 1273 /* Unparameterized paths have no ParamPathInfo */ 1274 if (bms_is_empty(required_outer)) 1275 return NULL; 1276 1277 Assert(!bms_overlap(baserel->relids, required_outer)); 1278 1279 /* If we already have a PPI for this parameterization, just return it */ 1280 if ((ppi = find_param_path_info(baserel, required_outer))) 1281 return ppi; 1282 1283 /* 1284 * Identify all joinclauses that are movable to this base rel given this 1285 * parameterization. 1286 */ 1287 joinrelids = bms_union(baserel->relids, required_outer); 1288 pclauses = NIL; 1289 foreach(lc, baserel->joininfo) 1290 { 1291 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); 1292 1293 if (join_clause_is_movable_into(rinfo, 1294 baserel->relids, 1295 joinrelids)) 1296 pclauses = lappend(pclauses, rinfo); 1297 } 1298 1299 /* 1300 * Add in joinclauses generated by EquivalenceClasses, too. (These 1301 * necessarily satisfy join_clause_is_movable_into.) 1302 */ 1303 pclauses = list_concat(pclauses, 1304 generate_join_implied_equalities(root, 1305 joinrelids, 1306 required_outer, 1307 baserel)); 1308 1309 /* Estimate the number of rows returned by the parameterized scan */ 1310 rows = get_parameterized_baserel_size(root, baserel, pclauses); 1311 1312 /* And now we can build the ParamPathInfo */ 1313 ppi = makeNode(ParamPathInfo); 1314 ppi->ppi_req_outer = required_outer; 1315 ppi->ppi_rows = rows; 1316 ppi->ppi_clauses = pclauses; 1317 baserel->ppilist = lappend(baserel->ppilist, ppi); 1318 1319 return ppi; 1320 } 1321 1322 /* 1323 * get_joinrel_parampathinfo 1324 * Get the ParamPathInfo for a parameterized path for a join relation, 1325 * constructing one if we don't have one already. 1326 * 1327 * This centralizes estimating the rowcounts for parameterized paths. 1328 * We need to cache those to be sure we use the same rowcount for all paths 1329 * of the same parameterization for a given rel. This is also a convenient 1330 * place to determine which movable join clauses the parameterized path will 1331 * be responsible for evaluating. 1332 * 1333 * outer_path and inner_path are a pair of input paths that can be used to 1334 * construct the join, and restrict_clauses is the list of regular join 1335 * clauses (including clauses derived from EquivalenceClasses) that must be 1336 * applied at the join node when using these inputs. 1337 * 1338 * Unlike the situation for base rels, the set of movable join clauses to be 1339 * enforced at a join varies with the selected pair of input paths, so we 1340 * must calculate that and pass it back, even if we already have a matching 1341 * ParamPathInfo. We handle this by adding any clauses moved down to this 1342 * join to *restrict_clauses, which is an in/out parameter. (The addition 1343 * is done in such a way as to not modify the passed-in List structure.) 1344 * 1345 * Note: when considering a nestloop join, the caller must have removed from 1346 * restrict_clauses any movable clauses that are themselves scheduled to be 1347 * pushed into the right-hand path. We do not do that here since it's 1348 * unnecessary for other join types. 1349 */ 1350 ParamPathInfo * 1351 get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel, 1352 Path *outer_path, 1353 Path *inner_path, 1354 SpecialJoinInfo *sjinfo, 1355 Relids required_outer, 1356 List **restrict_clauses) 1357 { 1358 ParamPathInfo *ppi; 1359 Relids join_and_req; 1360 Relids outer_and_req; 1361 Relids inner_and_req; 1362 List *pclauses; 1363 List *eclauses; 1364 List *dropped_ecs; 1365 double rows; 1366 ListCell *lc; 1367 1368 /* If rel has LATERAL refs, every path for it should account for them */ 1369 Assert(bms_is_subset(joinrel->lateral_relids, required_outer)); 1370 1371 /* Unparameterized paths have no ParamPathInfo or extra join clauses */ 1372 if (bms_is_empty(required_outer)) 1373 return NULL; 1374 1375 Assert(!bms_overlap(joinrel->relids, required_outer)); 1376 1377 /* 1378 * Identify all joinclauses that are movable to this join rel given this 1379 * parameterization. These are the clauses that are movable into this 1380 * join, but not movable into either input path. Treat an unparameterized 1381 * input path as not accepting parameterized clauses (because it won't, 1382 * per the shortcut exit above), even though the joinclause movement rules 1383 * might allow the same clauses to be moved into a parameterized path for 1384 * that rel. 1385 */ 1386 join_and_req = bms_union(joinrel->relids, required_outer); 1387 if (outer_path->param_info) 1388 outer_and_req = bms_union(outer_path->parent->relids, 1389 PATH_REQ_OUTER(outer_path)); 1390 else 1391 outer_and_req = NULL; /* outer path does not accept parameters */ 1392 if (inner_path->param_info) 1393 inner_and_req = bms_union(inner_path->parent->relids, 1394 PATH_REQ_OUTER(inner_path)); 1395 else 1396 inner_and_req = NULL; /* inner path does not accept parameters */ 1397 1398 pclauses = NIL; 1399 foreach(lc, joinrel->joininfo) 1400 { 1401 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); 1402 1403 if (join_clause_is_movable_into(rinfo, 1404 joinrel->relids, 1405 join_and_req) && 1406 !join_clause_is_movable_into(rinfo, 1407 outer_path->parent->relids, 1408 outer_and_req) && 1409 !join_clause_is_movable_into(rinfo, 1410 inner_path->parent->relids, 1411 inner_and_req)) 1412 pclauses = lappend(pclauses, rinfo); 1413 } 1414 1415 /* Consider joinclauses generated by EquivalenceClasses, too */ 1416 eclauses = generate_join_implied_equalities(root, 1417 join_and_req, 1418 required_outer, 1419 joinrel); 1420 /* We only want ones that aren't movable to lower levels */ 1421 dropped_ecs = NIL; 1422 foreach(lc, eclauses) 1423 { 1424 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); 1425 1426 /* 1427 * In principle, join_clause_is_movable_into() should accept anything 1428 * returned by generate_join_implied_equalities(); but because its 1429 * analysis is only approximate, sometimes it doesn't. So we 1430 * currently cannot use this Assert; instead just assume it's okay to 1431 * apply the joinclause at this level. 1432 */ 1433 #ifdef NOT_USED 1434 Assert(join_clause_is_movable_into(rinfo, 1435 joinrel->relids, 1436 join_and_req)); 1437 #endif 1438 if (join_clause_is_movable_into(rinfo, 1439 outer_path->parent->relids, 1440 outer_and_req)) 1441 continue; /* drop if movable into LHS */ 1442 if (join_clause_is_movable_into(rinfo, 1443 inner_path->parent->relids, 1444 inner_and_req)) 1445 { 1446 /* drop if movable into RHS, but remember EC for use below */ 1447 Assert(rinfo->left_ec == rinfo->right_ec); 1448 dropped_ecs = lappend(dropped_ecs, rinfo->left_ec); 1449 continue; 1450 } 1451 pclauses = lappend(pclauses, rinfo); 1452 } 1453 1454 /* 1455 * EquivalenceClasses are harder to deal with than we could wish, because 1456 * of the fact that a given EC can generate different clauses depending on 1457 * context. Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the 1458 * LHS and RHS of the current join and Z is in required_outer, and further 1459 * suppose that the inner_path is parameterized by both X and Z. The code 1460 * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC, 1461 * and in the latter case will have discarded it as being movable into the 1462 * RHS. However, the EC machinery might have produced either Y.Y = X.X or 1463 * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will 1464 * not have produced both, and we can't readily tell from here which one 1465 * it did pick. If we add no clause to this join, we'll end up with 1466 * insufficient enforcement of the EC; either Z.Z or X.X will fail to be 1467 * constrained to be equal to the other members of the EC. (When we come 1468 * to join Z to this X/Y path, we will certainly drop whichever EC clause 1469 * is generated at that join, so this omission won't get fixed later.) 1470 * 1471 * To handle this, for each EC we discarded such a clause from, try to 1472 * generate a clause connecting the required_outer rels to the join's LHS 1473 * ("Z.Z = X.X" in the terms of the above example). If successful, and if 1474 * the clause can't be moved to the LHS, add it to the current join's 1475 * restriction clauses. (If an EC cannot generate such a clause then it 1476 * has nothing that needs to be enforced here, while if the clause can be 1477 * moved into the LHS then it should have been enforced within that path.) 1478 * 1479 * Note that we don't need similar processing for ECs whose clause was 1480 * considered to be movable into the LHS, because the LHS can't refer to 1481 * the RHS so there is no comparable ambiguity about what it might 1482 * actually be enforcing internally. 1483 */ 1484 if (dropped_ecs) 1485 { 1486 Relids real_outer_and_req; 1487 1488 real_outer_and_req = bms_union(outer_path->parent->relids, 1489 required_outer); 1490 eclauses = 1491 generate_join_implied_equalities_for_ecs(root, 1492 dropped_ecs, 1493 real_outer_and_req, 1494 required_outer, 1495 outer_path->parent); 1496 foreach(lc, eclauses) 1497 { 1498 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); 1499 1500 /* As above, can't quite assert this here */ 1501 #ifdef NOT_USED 1502 Assert(join_clause_is_movable_into(rinfo, 1503 outer_path->parent->relids, 1504 real_outer_and_req)); 1505 #endif 1506 if (!join_clause_is_movable_into(rinfo, 1507 outer_path->parent->relids, 1508 outer_and_req)) 1509 pclauses = lappend(pclauses, rinfo); 1510 } 1511 } 1512 1513 /* 1514 * Now, attach the identified moved-down clauses to the caller's 1515 * restrict_clauses list. By using list_concat in this order, we leave 1516 * the original list structure of restrict_clauses undamaged. 1517 */ 1518 *restrict_clauses = list_concat(pclauses, *restrict_clauses); 1519 1520 /* If we already have a PPI for this parameterization, just return it */ 1521 if ((ppi = find_param_path_info(joinrel, required_outer))) 1522 return ppi; 1523 1524 /* Estimate the number of rows returned by the parameterized join */ 1525 rows = get_parameterized_joinrel_size(root, joinrel, 1526 outer_path, 1527 inner_path, 1528 sjinfo, 1529 *restrict_clauses); 1530 1531 /* 1532 * And now we can build the ParamPathInfo. No point in saving the 1533 * input-pair-dependent clause list, though. 1534 * 1535 * Note: in GEQO mode, we'll be called in a temporary memory context, but 1536 * the joinrel structure is there too, so no problem. 1537 */ 1538 ppi = makeNode(ParamPathInfo); 1539 ppi->ppi_req_outer = required_outer; 1540 ppi->ppi_rows = rows; 1541 ppi->ppi_clauses = NIL; 1542 joinrel->ppilist = lappend(joinrel->ppilist, ppi); 1543 1544 return ppi; 1545 } 1546 1547 /* 1548 * get_appendrel_parampathinfo 1549 * Get the ParamPathInfo for a parameterized path for an append relation. 1550 * 1551 * For an append relation, the rowcount estimate will just be the sum of 1552 * the estimates for its children. However, we still need a ParamPathInfo 1553 * to flag the fact that the path requires parameters. So this just creates 1554 * a suitable struct with zero ppi_rows (and no ppi_clauses either, since 1555 * the Append node isn't responsible for checking quals). 1556 */ 1557 ParamPathInfo * 1558 get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer) 1559 { 1560 ParamPathInfo *ppi; 1561 1562 /* If rel has LATERAL refs, every path for it should account for them */ 1563 Assert(bms_is_subset(appendrel->lateral_relids, required_outer)); 1564 1565 /* Unparameterized paths have no ParamPathInfo */ 1566 if (bms_is_empty(required_outer)) 1567 return NULL; 1568 1569 Assert(!bms_overlap(appendrel->relids, required_outer)); 1570 1571 /* If we already have a PPI for this parameterization, just return it */ 1572 if ((ppi = find_param_path_info(appendrel, required_outer))) 1573 return ppi; 1574 1575 /* Else build the ParamPathInfo */ 1576 ppi = makeNode(ParamPathInfo); 1577 ppi->ppi_req_outer = required_outer; 1578 ppi->ppi_rows = 0; 1579 ppi->ppi_clauses = NIL; 1580 appendrel->ppilist = lappend(appendrel->ppilist, ppi); 1581 1582 return ppi; 1583 } 1584 1585 /* 1586 * Returns a ParamPathInfo for the parameterization given by required_outer, if 1587 * already available in the given rel. Returns NULL otherwise. 1588 */ 1589 ParamPathInfo * 1590 find_param_path_info(RelOptInfo *rel, Relids required_outer) 1591 { 1592 ListCell *lc; 1593 1594 foreach(lc, rel->ppilist) 1595 { 1596 ParamPathInfo *ppi = (ParamPathInfo *) lfirst(lc); 1597 1598 if (bms_equal(ppi->ppi_req_outer, required_outer)) 1599 return ppi; 1600 } 1601 1602 return NULL; 1603 } 1604 1605 /* 1606 * build_joinrel_partition_info 1607 * If the two relations have same partitioning scheme, their join may be 1608 * partitioned and will follow the same partitioning scheme as the joining 1609 * relations. Set the partition scheme and partition key expressions in 1610 * the join relation. 1611 */ 1612 static void 1613 build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, 1614 RelOptInfo *inner_rel, List *restrictlist, 1615 JoinType jointype) 1616 { 1617 int partnatts; 1618 int cnt; 1619 PartitionScheme part_scheme; 1620 1621 /* Nothing to do if partitionwise join technique is disabled. */ 1622 if (!enable_partitionwise_join) 1623 { 1624 Assert(!IS_PARTITIONED_REL(joinrel)); 1625 return; 1626 } 1627 1628 /* 1629 * We can only consider this join as an input to further partitionwise 1630 * joins if (a) the input relations are partitioned and have 1631 * consider_partitionwise_join=true, (b) the partition schemes match, and 1632 * (c) we can identify an equi-join between the partition keys. Note that 1633 * if it were possible for have_partkey_equi_join to return different 1634 * answers for the same joinrel depending on which join ordering we try 1635 * first, this logic would break. That shouldn't happen, though, because 1636 * of the way the query planner deduces implied equalities and reorders 1637 * the joins. Please see optimizer/README for details. 1638 */ 1639 if (!IS_PARTITIONED_REL(outer_rel) || !IS_PARTITIONED_REL(inner_rel) || 1640 !outer_rel->consider_partitionwise_join || 1641 !inner_rel->consider_partitionwise_join || 1642 outer_rel->part_scheme != inner_rel->part_scheme || 1643 !have_partkey_equi_join(joinrel, outer_rel, inner_rel, 1644 jointype, restrictlist)) 1645 { 1646 Assert(!IS_PARTITIONED_REL(joinrel)); 1647 return; 1648 } 1649 1650 part_scheme = outer_rel->part_scheme; 1651 1652 Assert(REL_HAS_ALL_PART_PROPS(outer_rel) && 1653 REL_HAS_ALL_PART_PROPS(inner_rel)); 1654 1655 /* 1656 * For now, our partition matching algorithm can match partitions only 1657 * when the partition bounds of the joining relations are exactly same. 1658 * So, bail out otherwise. 1659 */ 1660 if (outer_rel->nparts != inner_rel->nparts || 1661 !partition_bounds_equal(part_scheme->partnatts, 1662 part_scheme->parttyplen, 1663 part_scheme->parttypbyval, 1664 outer_rel->boundinfo, inner_rel->boundinfo)) 1665 { 1666 Assert(!IS_PARTITIONED_REL(joinrel)); 1667 return; 1668 } 1669 1670 /* 1671 * This function will be called only once for each joinrel, hence it 1672 * should not have partition scheme, partition bounds, partition key 1673 * expressions and array for storing child relations set. 1674 */ 1675 Assert(!joinrel->part_scheme && !joinrel->partexprs && 1676 !joinrel->nullable_partexprs && !joinrel->part_rels && 1677 !joinrel->boundinfo); 1678 1679 /* 1680 * Join relation is partitioned using the same partitioning scheme as the 1681 * joining relations and has same bounds. 1682 */ 1683 joinrel->part_scheme = part_scheme; 1684 joinrel->boundinfo = outer_rel->boundinfo; 1685 partnatts = joinrel->part_scheme->partnatts; 1686 joinrel->partexprs = (List **) palloc0(sizeof(List *) * partnatts); 1687 joinrel->nullable_partexprs = 1688 (List **) palloc0(sizeof(List *) * partnatts); 1689 joinrel->nparts = outer_rel->nparts; 1690 joinrel->part_rels = 1691 (RelOptInfo **) palloc0(sizeof(RelOptInfo *) * joinrel->nparts); 1692 1693 /* 1694 * Set the consider_partitionwise_join flag. 1695 */ 1696 Assert(outer_rel->consider_partitionwise_join); 1697 Assert(inner_rel->consider_partitionwise_join); 1698 joinrel->consider_partitionwise_join = true; 1699 1700 /* 1701 * Construct partition keys for the join. 1702 * 1703 * An INNER join between two partitioned relations can be regarded as 1704 * partitioned by either key expression. For example, A INNER JOIN B ON 1705 * A.a = B.b can be regarded as partitioned on A.a or on B.b; they are 1706 * equivalent. 1707 * 1708 * For a SEMI or ANTI join, the result can only be regarded as being 1709 * partitioned in the same manner as the outer side, since the inner 1710 * columns are not retained. 1711 * 1712 * An OUTER join like (A LEFT JOIN B ON A.a = B.b) may produce rows with 1713 * B.b NULL. These rows may not fit the partitioning conditions imposed on 1714 * B.b. Hence, strictly speaking, the join is not partitioned by B.b and 1715 * thus partition keys of an OUTER join should include partition key 1716 * expressions from the OUTER side only. However, because all 1717 * commonly-used comparison operators are strict, the presence of nulls on 1718 * the outer side doesn't cause any problem; they can't match anything at 1719 * future join levels anyway. Therefore, we track two sets of 1720 * expressions: those that authentically partition the relation 1721 * (partexprs) and those that partition the relation with the exception 1722 * that extra nulls may be present (nullable_partexprs). When the 1723 * comparison operator is strict, the latter is just as good as the 1724 * former. 1725 */ 1726 for (cnt = 0; cnt < partnatts; cnt++) 1727 { 1728 List *outer_expr; 1729 List *outer_null_expr; 1730 List *inner_expr; 1731 List *inner_null_expr; 1732 List *partexpr = NIL; 1733 List *nullable_partexpr = NIL; 1734 1735 outer_expr = list_copy(outer_rel->partexprs[cnt]); 1736 outer_null_expr = list_copy(outer_rel->nullable_partexprs[cnt]); 1737 inner_expr = list_copy(inner_rel->partexprs[cnt]); 1738 inner_null_expr = list_copy(inner_rel->nullable_partexprs[cnt]); 1739 1740 switch (jointype) 1741 { 1742 case JOIN_INNER: 1743 partexpr = list_concat(outer_expr, inner_expr); 1744 nullable_partexpr = list_concat(outer_null_expr, 1745 inner_null_expr); 1746 break; 1747 1748 case JOIN_SEMI: 1749 case JOIN_ANTI: 1750 partexpr = outer_expr; 1751 nullable_partexpr = outer_null_expr; 1752 break; 1753 1754 case JOIN_LEFT: 1755 partexpr = outer_expr; 1756 nullable_partexpr = list_concat(inner_expr, 1757 outer_null_expr); 1758 nullable_partexpr = list_concat(nullable_partexpr, 1759 inner_null_expr); 1760 break; 1761 1762 case JOIN_FULL: 1763 nullable_partexpr = list_concat(outer_expr, 1764 inner_expr); 1765 nullable_partexpr = list_concat(nullable_partexpr, 1766 outer_null_expr); 1767 nullable_partexpr = list_concat(nullable_partexpr, 1768 inner_null_expr); 1769 break; 1770 1771 default: 1772 elog(ERROR, "unrecognized join type: %d", (int) jointype); 1773 1774 } 1775 1776 joinrel->partexprs[cnt] = partexpr; 1777 joinrel->nullable_partexprs[cnt] = nullable_partexpr; 1778 } 1779 } 1780 1781 /* 1782 * build_child_join_reltarget 1783 * Set up a child-join relation's reltarget from a parent-join relation. 1784 */ 1785 static void 1786 build_child_join_reltarget(PlannerInfo *root, 1787 RelOptInfo *parentrel, 1788 RelOptInfo *childrel, 1789 int nappinfos, 1790 AppendRelInfo **appinfos) 1791 { 1792 /* Build the targetlist */ 1793 childrel->reltarget->exprs = (List *) 1794 adjust_appendrel_attrs(root, 1795 (Node *) parentrel->reltarget->exprs, 1796 nappinfos, appinfos); 1797 1798 /* Set the cost and width fields */ 1799 childrel->reltarget->cost.startup = parentrel->reltarget->cost.startup; 1800 childrel->reltarget->cost.per_tuple = parentrel->reltarget->cost.per_tuple; 1801 childrel->reltarget->width = parentrel->reltarget->width; 1802 } 1803