| 1 |
/*------------------------------------------------------------------------- |
| 2 |
* |
| 3 |
* joinrels.c |
| 4 |
* Routines to determine which relations should be joined |
| 5 |
* |
| 6 |
* Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group |
| 7 |
* Portions Copyright (c) 1994, Regents of the University of California |
| 8 |
* |
| 9 |
* |
| 10 |
* IDENTIFICATION |
| 11 |
* src/backend/optimizer/path/joinrels.c |
| 12 |
* |
| 13 |
*------------------------------------------------------------------------- |
| 14 |
*/ |
| 15 |
#include "postgres.h" |
| 16 |
|
| 17 |
#include "miscadmin.h" |
| 18 |
#include "optimizer/appendinfo.h" |
| 19 |
#include "optimizer/joininfo.h" |
| 20 |
#include "optimizer/pathnode.h" |
| 21 |
#include "optimizer/paths.h" |
| 22 |
#include "partitioning/partbounds.h" |
| 23 |
#include "utils/memutils.h" |
| 24 |
|
| 25 |
|
| 26 |
static void make_rels_by_clause_joins(PlannerInfo *root, |
| 27 |
RelOptInfo *old_rel, |
| 28 |
List *other_rels, |
| 29 |
int first_rel_idx); |
| 30 |
static void make_rels_by_clauseless_joins(PlannerInfo *root, |
| 31 |
RelOptInfo *old_rel, |
| 32 |
List *other_rels); |
| 33 |
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel); |
| 34 |
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel); |
| 35 |
static bool restriction_is_constant_false(List *restrictlist, |
| 36 |
RelOptInfo *joinrel, |
| 37 |
bool only_pushed_down); |
| 38 |
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, |
| 39 |
RelOptInfo *rel2, RelOptInfo *joinrel, |
| 40 |
SpecialJoinInfo *sjinfo, List *restrictlist); |
| 41 |
static void try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, |
| 42 |
RelOptInfo *rel2, RelOptInfo *joinrel, |
| 43 |
SpecialJoinInfo *parent_sjinfo, |
| 44 |
List *parent_restrictlist); |
| 45 |
static SpecialJoinInfo *build_child_join_sjinfo(PlannerInfo *root, |
| 46 |
SpecialJoinInfo *parent_sjinfo, |
| 47 |
Relids left_relids, Relids right_relids); |
| 48 |
static void free_child_join_sjinfo(SpecialJoinInfo *child_sjinfo, |
| 49 |
SpecialJoinInfo *parent_sjinfo); |
| 50 |
static void compute_partition_bounds(PlannerInfo *root, RelOptInfo *rel1, |
| 51 |
RelOptInfo *rel2, RelOptInfo *joinrel, |
| 52 |
SpecialJoinInfo *parent_sjinfo, |
| 53 |
List **parts1, List **parts2); |
| 54 |
static void get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel, |
| 55 |
RelOptInfo *rel1, RelOptInfo *rel2, |
| 56 |
List **parts1, List **parts2); |
| 57 |
|
| 58 |
|
| 59 |
/* |
| 60 |
* join_search_one_level |
| 61 |
* Consider ways to produce join relations containing exactly 'level' |
| 62 |
* jointree items. (This is one step of the dynamic-programming method |
| 63 |
* embodied in standard_join_search.) Join rel nodes for each feasible |
| 64 |
* combination of lower-level rels are created and returned in a list. |
| 65 |
* Implementation paths are created for each such joinrel, too. |
| 66 |
* |
| 67 |
* level: level of rels we want to make this time |
| 68 |
* root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items |
| 69 |
* |
| 70 |
* The result is returned in root->join_rel_level[level]. |
| 71 |
*/ |
| 72 |
void |
| 73 |
join_search_one_level(PlannerInfo *root, int level) |
| 74 |
{ |
| 75 |
List **joinrels = root->join_rel_level; |
| 76 |
ListCell *r; |
| 77 |
int k; |
| 78 |
|
| 79 |
Assert(joinrels[level] == NIL); |
| 80 |
|
| 81 |
/* Set join_cur_level so that new joinrels are added to proper list */ |
| 82 |
root->join_cur_level = level; |
| 83 |
|
| 84 |
/* |
| 85 |
* First, consider left-sided and right-sided plans, in which rels of |
| 86 |
* exactly level-1 member relations are joined against initial relations. |
| 87 |
* We prefer to join using join clauses, but if we find a rel of level-1 |
| 88 |
* members that has no join clauses, we will generate Cartesian-product |
| 89 |
* joins against all initial rels not already contained in it. |
| 90 |
*/ |
| 91 |
foreach(r, joinrels[level - 1]) |
| 92 |
{ |
| 93 |
RelOptInfo *old_rel = (RelOptInfo *) lfirst(r); |
| 94 |
|
| 95 |
if (old_rel->joininfo != NIL || old_rel->has_eclass_joins || |
| 96 |
has_join_restriction(root, old_rel)) |
| 97 |
{ |
| 98 |
int first_rel; |
| 99 |
|
| 100 |
/* |
| 101 |
* There are join clauses or join order restrictions relevant to |
| 102 |
* this rel, so consider joins between this rel and (only) those |
| 103 |
* initial rels it is linked to by a clause or restriction. |
| 104 |
* |
| 105 |
* At level 2 this condition is symmetric, so there is no need to |
| 106 |
* look at initial rels before this one in the list; we already |
| 107 |
* considered such joins when we were at the earlier rel. (The |
| 108 |
* mirror-image joins are handled automatically by make_join_rel.) |
| 109 |
* In later passes (level > 2), we join rels of the previous level |
| 110 |
* to each initial rel they don't already include but have a join |
| 111 |
* clause or restriction with. |
| 112 |
*/ |
| 113 |
if (level == 2) /* consider remaining initial rels */ |
| 114 |
first_rel = foreach_current_index(r) + 1; |
| 115 |
else |
| 116 |
first_rel = 0; |
| 117 |
|
| 118 |
make_rels_by_clause_joins(root, old_rel, joinrels[1], first_rel); |
| 119 |
} |
| 120 |
else |
| 121 |
{ |
| 122 |
/* |
| 123 |
* Oops, we have a relation that is not joined to any other |
| 124 |
* relation, either directly or by join-order restrictions. |
| 125 |
* Cartesian product time. |
| 126 |
* |
| 127 |
* We consider a cartesian product with each not-already-included |
| 128 |
* initial rel, whether it has other join clauses or not. At |
| 129 |
* level 2, if there are two or more clauseless initial rels, we |
| 130 |
* will redundantly consider joining them in both directions; but |
| 131 |
* such cases aren't common enough to justify adding complexity to |
| 132 |
* avoid the duplicated effort. |
| 133 |
*/ |
| 134 |
make_rels_by_clauseless_joins(root, |
| 135 |
old_rel, |
| 136 |
joinrels[1]); |
| 137 |
} |
| 138 |
} |
| 139 |
|
| 140 |
/* |
| 141 |
* Now, consider "bushy plans" in which relations of k initial rels are |
| 142 |
* joined to relations of level-k initial rels, for 2 <= k <= level-2. |
| 143 |
* |
| 144 |
* We only consider bushy-plan joins for pairs of rels where there is a |
| 145 |
* suitable join clause (or join order restriction), in order to avoid |
| 146 |
* unreasonable growth of planning time. |
| 147 |
*/ |
| 148 |
for (k = 2;; k++) |
| 149 |
{ |
| 150 |
int other_level = level - k; |
| 151 |
|
| 152 |
/* |
| 153 |
* Since make_join_rel(x, y) handles both x,y and y,x cases, we only |
| 154 |
* need to go as far as the halfway point. |
| 155 |
*/ |
| 156 |
if (k > other_level) |
| 157 |
break; |
| 158 |
|
| 159 |
foreach(r, joinrels[k]) |
| 160 |
{ |
| 161 |
RelOptInfo *old_rel = (RelOptInfo *) lfirst(r); |
| 162 |
int first_rel; |
| 163 |
ListCell *r2; |
| 164 |
|
| 165 |
/* |
| 166 |
* We can ignore relations without join clauses here, unless they |
| 167 |
* participate in join-order restrictions --- then we might have |
| 168 |
* to force a bushy join plan. |
| 169 |
*/ |
| 170 |
if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins && |
| 171 |
!has_join_restriction(root, old_rel)) |
| 172 |
continue; |
| 173 |
|
| 174 |
if (k == other_level) /* only consider remaining rels */ |
| 175 |
first_rel = foreach_current_index(r) + 1; |
| 176 |
else |
| 177 |
first_rel = 0; |
| 178 |
|
| 179 |
for_each_from(r2, joinrels[other_level], first_rel) |
| 180 |
{ |
| 181 |
RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2); |
| 182 |
|
| 183 |
if (!bms_overlap(old_rel->relids, new_rel->relids)) |
| 184 |
{ |
| 185 |
/* |
| 186 |
* OK, we can build a rel of the right level from this |
| 187 |
* pair of rels. Do so if there is at least one relevant |
| 188 |
* join clause or join order restriction. |
| 189 |
*/ |
| 190 |
if (have_relevant_joinclause(root, old_rel, new_rel) || |
| 191 |
have_join_order_restriction(root, old_rel, new_rel)) |
| 192 |
{ |
| 193 |
(void) make_join_rel(root, old_rel, new_rel); |
| 194 |
} |
| 195 |
} |
| 196 |
} |
| 197 |
} |
| 198 |
} |
| 199 |
|
| 200 |
/*---------- |
| 201 |
* Last-ditch effort: if we failed to find any usable joins so far, force |
| 202 |
* a set of cartesian-product joins to be generated. This handles the |
| 203 |
* special case where all the available rels have join clauses but we |
| 204 |
* cannot use any of those clauses yet. This can only happen when we are |
| 205 |
* considering a join sub-problem (a sub-joinlist) and all the rels in the |
| 206 |
* sub-problem have only join clauses with rels outside the sub-problem. |
| 207 |
* An example is |
| 208 |
* |
| 209 |
* SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ... |
| 210 |
* WHERE a.w = c.x and b.y = d.z; |
| 211 |
* |
| 212 |
* If the "a INNER JOIN b" sub-problem does not get flattened into the |
| 213 |
* upper level, we must be willing to make a cartesian join of a and b; |
| 214 |
* but the code above will not have done so, because it thought that both |
| 215 |
* a and b have joinclauses. We consider only left-sided and right-sided |
| 216 |
* cartesian joins in this case (no bushy). |
| 217 |
*---------- |
| 218 |
*/ |
| 219 |
if (joinrels[level] == NIL) |
| 220 |
{ |
| 221 |
/* |
| 222 |
* This loop is just like the first one, except we always call |
| 223 |
* make_rels_by_clauseless_joins(). |
| 224 |
*/ |
| 225 |
foreach(r, joinrels[level - 1]) |
| 226 |
{ |
| 227 |
RelOptInfo *old_rel = (RelOptInfo *) lfirst(r); |
| 228 |
|
| 229 |
make_rels_by_clauseless_joins(root, |
| 230 |
old_rel, |
| 231 |
joinrels[1]); |
| 232 |
} |
| 233 |
|
| 234 |
/*---------- |
| 235 |
* When special joins are involved, there may be no legal way |
| 236 |
* to make an N-way join for some values of N. For example consider |
| 237 |
* |
| 238 |
* SELECT ... FROM t1 WHERE |
| 239 |
* x IN (SELECT ... FROM t2,t3 WHERE ...) AND |
| 240 |
* y IN (SELECT ... FROM t4,t5 WHERE ...) |
| 241 |
* |
| 242 |
* We will flatten this query to a 5-way join problem, but there are |
| 243 |
* no 4-way joins that join_is_legal() will consider legal. We have |
| 244 |
* to accept failure at level 4 and go on to discover a workable |
| 245 |
* bushy plan at level 5. |
| 246 |
* |
| 247 |
* However, if there are no special joins and no lateral references |
| 248 |
* then join_is_legal() should never fail, and so the following sanity |
| 249 |
* check is useful. |
| 250 |
*---------- |
| 251 |
*/ |
| 252 |
if (joinrels[level] == NIL && |
| 253 |
root->join_info_list == NIL && |
| 254 |
!root->hasLateralRTEs) |
| 255 |
elog(ERROR, "failed to build any %d-way joins", level); |
| 256 |
} |
| 257 |
} |
| 258 |
|
| 259 |
/* |
| 260 |
* make_rels_by_clause_joins |
| 261 |
* Build joins between the given relation 'old_rel' and other relations |
| 262 |
* that participate in join clauses that 'old_rel' also participates in |
| 263 |
* (or participate in join-order restrictions with it). |
| 264 |
* The join rels are returned in root->join_rel_level[join_cur_level]. |
| 265 |
* |
| 266 |
* Note: at levels above 2 we will generate the same joined relation in |
| 267 |
* multiple ways --- for example (a join b) join c is the same RelOptInfo as |
| 268 |
* (b join c) join a, though the second case will add a different set of Paths |
| 269 |
* to it. This is the reason for using the join_rel_level mechanism, which |
| 270 |
* automatically ensures that each new joinrel is only added to the list once. |
| 271 |
* |
| 272 |
* 'old_rel' is the relation entry for the relation to be joined |
| 273 |
* 'other_rels': a list containing the other rels to be considered for joining |
| 274 |
* 'first_rel_idx': the first rel to be considered in 'other_rels' |
| 275 |
* |
| 276 |
* Currently, this is only used with initial rels in other_rels, but it |
| 277 |
* will work for joining to joinrels too. |
| 278 |
*/ |
| 279 |
static void |
| 280 |
make_rels_by_clause_joins(PlannerInfo *root, |
| 281 |
RelOptInfo *old_rel, |
| 282 |
List *other_rels, |
| 283 |
int first_rel_idx) |
| 284 |
{ |
| 285 |
ListCell *l; |
| 286 |
|
| 287 |
for_each_from(l, other_rels, first_rel_idx) |
| 288 |
{ |
| 289 |
RelOptInfo *other_rel = (RelOptInfo *) lfirst(l); |
| 290 |
|
| 291 |
if (!bms_overlap(old_rel->relids, other_rel->relids) && |
| 292 |
(have_relevant_joinclause(root, old_rel, other_rel) || |
| 293 |
have_join_order_restriction(root, old_rel, other_rel))) |
| 294 |
{ |
| 295 |
(void) make_join_rel(root, old_rel, other_rel); |
| 296 |
} |
| 297 |
} |
| 298 |
} |
| 299 |
|
| 300 |
/* |
| 301 |
* make_rels_by_clauseless_joins |
| 302 |
* Given a relation 'old_rel' and a list of other relations |
| 303 |
* 'other_rels', create a join relation between 'old_rel' and each |
| 304 |
* member of 'other_rels' that isn't already included in 'old_rel'. |
| 305 |
* The join rels are returned in root->join_rel_level[join_cur_level]. |
| 306 |
* |
| 307 |
* 'old_rel' is the relation entry for the relation to be joined |
| 308 |
* 'other_rels': a list containing the other rels to be considered for joining |
| 309 |
* |
| 310 |
* Currently, this is only used with initial rels in other_rels, but it would |
| 311 |
* work for joining to joinrels too. |
| 312 |
*/ |
| 313 |
static void |
| 314 |
make_rels_by_clauseless_joins(PlannerInfo *root, |
| 315 |
RelOptInfo *old_rel, |
| 316 |
List *other_rels) |
| 317 |
{ |
| 318 |
ListCell *l; |
| 319 |
|
| 320 |
foreach(l, other_rels) |
| 321 |
{ |
| 322 |
RelOptInfo *other_rel = (RelOptInfo *) lfirst(l); |
| 323 |
|
| 324 |
if (!bms_overlap(other_rel->relids, old_rel->relids)) |
| 325 |
{ |
| 326 |
(void) make_join_rel(root, old_rel, other_rel); |
| 327 |
} |
| 328 |
} |
| 329 |
} |
| 330 |
|
| 331 |
|
| 332 |
/* |
| 333 |
* join_is_legal |
| 334 |
* Determine whether a proposed join is legal given the query's |
| 335 |
* join order constraints; and if it is, determine the join type. |
| 336 |
* |
| 337 |
* Caller must supply not only the two rels, but the union of their relids. |
| 338 |
* (We could simplify the API by computing joinrelids locally, but this |
| 339 |
* would be redundant work in the normal path through make_join_rel. |
| 340 |
* Note that this value does NOT include the RT index of any outer join that |
| 341 |
* might need to be performed here, so it's not the canonical identifier |
| 342 |
* of the join relation.) |
| 343 |
* |
| 344 |
* On success, *sjinfo_p is set to NULL if this is to be a plain inner join, |
| 345 |
* else it's set to point to the associated SpecialJoinInfo node. Also, |
| 346 |
* *reversed_p is set true if the given relations need to be swapped to |
| 347 |
* match the SpecialJoinInfo node. |
| 348 |
*/ |
| 349 |
static bool |
| 350 |
join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, |
| 351 |
Relids joinrelids, |
| 352 |
SpecialJoinInfo **sjinfo_p, bool *reversed_p) |
| 353 |
{ |
| 354 |
SpecialJoinInfo *match_sjinfo; |
| 355 |
bool reversed; |
| 356 |
bool unique_ified; |
| 357 |
bool must_be_leftjoin; |
| 358 |
ListCell *l; |
| 359 |
|
| 360 |
/* |
| 361 |
* Ensure output params are set on failure return. This is just to |
| 362 |
* suppress uninitialized-variable warnings from overly anal compilers. |
| 363 |
*/ |
| 364 |
*sjinfo_p = NULL; |
| 365 |
*reversed_p = false; |
| 366 |
|
| 367 |
/* |
| 368 |
* If we have any special joins, the proposed join might be illegal; and |
| 369 |
* in any case we have to determine its join type. Scan the join info |
| 370 |
* list for matches and conflicts. |
| 371 |
*/ |
| 372 |
match_sjinfo = NULL; |
| 373 |
reversed = false; |
| 374 |
unique_ified = false; |
| 375 |
must_be_leftjoin = false; |
| 376 |
|
| 377 |
foreach(l, root->join_info_list) |
| 378 |
{ |
| 379 |
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l); |
| 380 |
|
| 381 |
/* |
| 382 |
* This special join is not relevant unless its RHS overlaps the |
| 383 |
* proposed join. (Check this first as a fast path for dismissing |
| 384 |
* most irrelevant SJs quickly.) |
| 385 |
*/ |
| 386 |
if (!bms_overlap(sjinfo->min_righthand, joinrelids)) |
| 387 |
continue; |
| 388 |
|
| 389 |
/* |
| 390 |
* Also, not relevant if proposed join is fully contained within RHS |
| 391 |
* (ie, we're still building up the RHS). |
| 392 |
*/ |
| 393 |
if (bms_is_subset(joinrelids, sjinfo->min_righthand)) |
| 394 |
continue; |
| 395 |
|
| 396 |
/* |
| 397 |
* Also, not relevant if SJ is already done within either input. |
| 398 |
*/ |
| 399 |
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) && |
| 400 |
bms_is_subset(sjinfo->min_righthand, rel1->relids)) |
| 401 |
continue; |
| 402 |
if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) && |
| 403 |
bms_is_subset(sjinfo->min_righthand, rel2->relids)) |
| 404 |
continue; |
| 405 |
|
| 406 |
/* |
| 407 |
* If it's a semijoin and we already joined the RHS to any other rels |
| 408 |
* within either input, then we must have unique-ified the RHS at that |
| 409 |
* point (see below). Therefore the semijoin is no longer relevant in |
| 410 |
* this join path. |
| 411 |
*/ |
| 412 |
if (sjinfo->jointype == JOIN_SEMI) |
| 413 |
{ |
| 414 |
if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) && |
| 415 |
!bms_equal(sjinfo->syn_righthand, rel1->relids)) |
| 416 |
continue; |
| 417 |
if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) && |
| 418 |
!bms_equal(sjinfo->syn_righthand, rel2->relids)) |
| 419 |
continue; |
| 420 |
} |
| 421 |
|
| 422 |
/* |
| 423 |
* If one input contains min_lefthand and the other contains |
| 424 |
* min_righthand, then we can perform the SJ at this join. |
| 425 |
* |
| 426 |
* Reject if we get matches to more than one SJ; that implies we're |
| 427 |
* considering something that's not really valid. |
| 428 |
*/ |
| 429 |
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) && |
| 430 |
bms_is_subset(sjinfo->min_righthand, rel2->relids)) |
| 431 |
{ |
| 432 |
if (match_sjinfo) |
| 433 |
return false; /* invalid join path */ |
| 434 |
match_sjinfo = sjinfo; |
| 435 |
reversed = false; |
| 436 |
} |
| 437 |
else if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) && |
| 438 |
bms_is_subset(sjinfo->min_righthand, rel1->relids)) |
| 439 |
{ |
| 440 |
if (match_sjinfo) |
| 441 |
return false; /* invalid join path */ |
| 442 |
match_sjinfo = sjinfo; |
| 443 |
reversed = true; |
| 444 |
} |
| 445 |
else if (sjinfo->jointype == JOIN_SEMI && |
| 446 |
bms_equal(sjinfo->syn_righthand, rel2->relids) && |
| 447 |
create_unique_path(root, rel2, rel2->cheapest_total_path, |
| 448 |
sjinfo) != NULL) |
| 449 |
{ |
| 450 |
/*---------- |
| 451 |
* For a semijoin, we can join the RHS to anything else by |
| 452 |
* unique-ifying the RHS (if the RHS can be unique-ified). |
| 453 |
* We will only get here if we have the full RHS but less |
| 454 |
* than min_lefthand on the LHS. |
| 455 |
* |
| 456 |
* The reason to consider such a join path is exemplified by |
| 457 |
* SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c) |
| 458 |
* If we insist on doing this as a semijoin we will first have |
| 459 |
* to form the cartesian product of A*B. But if we unique-ify |
| 460 |
* C then the semijoin becomes a plain innerjoin and we can join |
| 461 |
* in any order, eg C to A and then to B. When C is much smaller |
| 462 |
* than A and B this can be a huge win. So we allow C to be |
| 463 |
* joined to just A or just B here, and then make_join_rel has |
| 464 |
* to handle the case properly. |
| 465 |
* |
| 466 |
* Note that actually we'll allow unique-ified C to be joined to |
| 467 |
* some other relation D here, too. That is legal, if usually not |
| 468 |
* very sane, and this routine is only concerned with legality not |
| 469 |
* with whether the join is good strategy. |
| 470 |
*---------- |
| 471 |
*/ |
| 472 |
if (match_sjinfo) |
| 473 |
return false; /* invalid join path */ |
| 474 |
match_sjinfo = sjinfo; |
| 475 |
reversed = false; |
| 476 |
unique_ified = true; |
| 477 |
} |
| 478 |
else if (sjinfo->jointype == JOIN_SEMI && |
| 479 |
bms_equal(sjinfo->syn_righthand, rel1->relids) && |
| 480 |
create_unique_path(root, rel1, rel1->cheapest_total_path, |
| 481 |
sjinfo) != NULL) |
| 482 |
{ |
| 483 |
/* Reversed semijoin case */ |
| 484 |
if (match_sjinfo) |
| 485 |
return false; /* invalid join path */ |
| 486 |
match_sjinfo = sjinfo; |
| 487 |
reversed = true; |
| 488 |
unique_ified = true; |
| 489 |
} |
| 490 |
else |
| 491 |
{ |
| 492 |
/* |
| 493 |
* Otherwise, the proposed join overlaps the RHS but isn't a valid |
| 494 |
* implementation of this SJ. But don't panic quite yet: the RHS |
| 495 |
* violation might have occurred previously, in one or both input |
| 496 |
* relations, in which case we must have previously decided that |
| 497 |
* it was OK to commute some other SJ with this one. If we need |
| 498 |
* to perform this join to finish building up the RHS, rejecting |
| 499 |
* it could lead to not finding any plan at all. (This can occur |
| 500 |
* because of the heuristics elsewhere in this file that postpone |
| 501 |
* clauseless joins: we might not consider doing a clauseless join |
| 502 |
* within the RHS until after we've performed other, validly |
| 503 |
* commutable SJs with one or both sides of the clauseless join.) |
| 504 |
* This consideration boils down to the rule that if both inputs |
| 505 |
* overlap the RHS, we can allow the join --- they are either |
| 506 |
* fully within the RHS, or represent previously-allowed joins to |
| 507 |
* rels outside it. |
| 508 |
*/ |
| 509 |
if (bms_overlap(rel1->relids, sjinfo->min_righthand) && |
| 510 |
bms_overlap(rel2->relids, sjinfo->min_righthand)) |
| 511 |
continue; /* assume valid previous violation of RHS */ |
| 512 |
|
| 513 |
/* |
| 514 |
* The proposed join could still be legal, but only if we're |
| 515 |
* allowed to associate it into the RHS of this SJ. That means |
| 516 |
* this SJ must be a LEFT join (not SEMI or ANTI, and certainly |
| 517 |
* not FULL) and the proposed join must not overlap the LHS. |
| 518 |
*/ |
| 519 |
if (sjinfo->jointype != JOIN_LEFT || |
| 520 |
bms_overlap(joinrelids, sjinfo->min_lefthand)) |
| 521 |
return false; /* invalid join path */ |
| 522 |
|
| 523 |
/* |
| 524 |
* To be valid, the proposed join must be a LEFT join; otherwise |
| 525 |
* it can't associate into this SJ's RHS. But we may not yet have |
| 526 |
* found the SpecialJoinInfo matching the proposed join, so we |
| 527 |
* can't test that yet. Remember the requirement for later. |
| 528 |
*/ |
| 529 |
must_be_leftjoin = true; |
| 530 |
} |
| 531 |
} |
| 532 |
|
| 533 |
/* |
| 534 |
* Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the |
| 535 |
* proposed join can't associate into an SJ's RHS. |
| 536 |
* |
| 537 |
* Also, fail if the proposed join's predicate isn't strict; we're |
| 538 |
* essentially checking to see if we can apply outer-join identity 3, and |
| 539 |
* that's a requirement. (This check may be redundant with checks in |
| 540 |
* make_outerjoininfo, but I'm not quite sure, and it's cheap to test.) |
| 541 |
*/ |
| 542 |
if (must_be_leftjoin && |
| 543 |
(match_sjinfo == NULL || |
| 544 |
match_sjinfo->jointype != JOIN_LEFT || |
| 545 |
!match_sjinfo->lhs_strict)) |
| 546 |
return false; /* invalid join path */ |
| 547 |
|
| 548 |
/* |
| 549 |
* We also have to check for constraints imposed by LATERAL references. |
| 550 |
*/ |
| 551 |
if (root->hasLateralRTEs) |
| 552 |
{ |
| 553 |
bool lateral_fwd; |
| 554 |
bool lateral_rev; |
| 555 |
Relids join_lateral_rels; |
| 556 |
|
| 557 |
/* |
| 558 |
* The proposed rels could each contain lateral references to the |
| 559 |
* other, in which case the join is impossible. If there are lateral |
| 560 |
* references in just one direction, then the join has to be done with |
| 561 |
* a nestloop with the lateral referencer on the inside. If the join |
| 562 |
* matches an SJ that cannot be implemented by such a nestloop, the |
| 563 |
* join is impossible. |
| 564 |
* |
| 565 |
* Also, if the lateral reference is only indirect, we should reject |
| 566 |
* the join; whatever rel(s) the reference chain goes through must be |
| 567 |
* joined to first. |
| 568 |
*/ |
| 569 |
lateral_fwd = bms_overlap(rel1->relids, rel2->lateral_relids); |
| 570 |
lateral_rev = bms_overlap(rel2->relids, rel1->lateral_relids); |
| 571 |
if (lateral_fwd && lateral_rev) |
| 572 |
return false; /* have lateral refs in both directions */ |
| 573 |
if (lateral_fwd) |
| 574 |
{ |
| 575 |
/* has to be implemented as nestloop with rel1 on left */ |
| 576 |
if (match_sjinfo && |
| 577 |
(reversed || |
| 578 |
unique_ified || |
| 579 |
match_sjinfo->jointype == JOIN_FULL)) |
| 580 |
return false; /* not implementable as nestloop */ |
| 581 |
/* check there is a direct reference from rel2 to rel1 */ |
| 582 |
if (!bms_overlap(rel1->relids, rel2->direct_lateral_relids)) |
| 583 |
return false; /* only indirect refs, so reject */ |
| 584 |
} |
| 585 |
else if (lateral_rev) |
| 586 |
{ |
| 587 |
/* has to be implemented as nestloop with rel2 on left */ |
| 588 |
if (match_sjinfo && |
| 589 |
(!reversed || |
| 590 |
unique_ified || |
| 591 |
match_sjinfo->jointype == JOIN_FULL)) |
| 592 |
return false; /* not implementable as nestloop */ |
| 593 |
/* check there is a direct reference from rel1 to rel2 */ |
| 594 |
if (!bms_overlap(rel2->relids, rel1->direct_lateral_relids)) |
| 595 |
return false; /* only indirect refs, so reject */ |
| 596 |
} |
| 597 |
|
| 598 |
/* |
| 599 |
* LATERAL references could also cause problems later on if we accept |
| 600 |
* this join: if the join's minimum parameterization includes any rels |
| 601 |
* that would have to be on the inside of an outer join with this join |
| 602 |
* rel, then it's never going to be possible to build the complete |
| 603 |
* query using this join. We should reject this join not only because |
| 604 |
* it'll save work, but because if we don't, the clauseless-join |
| 605 |
* heuristics might think that legality of this join means that some |
| 606 |
* other join rel need not be formed, and that could lead to failure |
| 607 |
* to find any plan at all. We have to consider not only rels that |
| 608 |
* are directly on the inner side of an OJ with the joinrel, but also |
| 609 |
* ones that are indirectly so, so search to find all such rels. |
| 610 |
*/ |
| 611 |
join_lateral_rels = min_join_parameterization(root, joinrelids, |
| 612 |
rel1, rel2); |
| 613 |
if (join_lateral_rels) |
| 614 |
{ |
| 615 |
Relids join_plus_rhs = bms_copy(joinrelids); |
| 616 |
bool more; |
| 617 |
|
| 618 |
do |
| 619 |
{ |
| 620 |
more = false; |
| 621 |
foreach(l, root->join_info_list) |
| 622 |
{ |
| 623 |
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l); |
| 624 |
|
| 625 |
/* ignore full joins --- their ordering is predetermined */ |
| 626 |
if (sjinfo->jointype == JOIN_FULL) |
| 627 |
continue; |
| 628 |
|
| 629 |
if (bms_overlap(sjinfo->min_lefthand, join_plus_rhs) && |
| 630 |
!bms_is_subset(sjinfo->min_righthand, join_plus_rhs)) |
| 631 |
{ |
| 632 |
join_plus_rhs = bms_add_members(join_plus_rhs, |
| 633 |
sjinfo->min_righthand); |
| 634 |
more = true; |
| 635 |
} |
| 636 |
} |
| 637 |
} while (more); |
| 638 |
if (bms_overlap(join_plus_rhs, join_lateral_rels)) |
| 639 |
return false; /* will not be able to join to some RHS rel */ |
| 640 |
} |
| 641 |
} |
| 642 |
|
| 643 |
/* Otherwise, it's a valid join */ |
| 644 |
*sjinfo_p = match_sjinfo; |
| 645 |
*reversed_p = reversed; |
| 646 |
return true; |
| 647 |
} |
| 648 |
|
| 649 |
/* |
| 650 |
* init_dummy_sjinfo |
| 651 |
* Populate the given SpecialJoinInfo for a plain inner join between the |
| 652 |
* left and right relations specified by left_relids and right_relids |
| 653 |
* respectively. |
| 654 |
* |
| 655 |
* Normally, an inner join does not have a SpecialJoinInfo node associated with |
| 656 |
* it. But some functions involved in join planning require one containing at |
| 657 |
* least the information of which relations are being joined. So we initialize |
| 658 |
* that information here. |
| 659 |
*/ |
| 660 |
void |
| 661 |
init_dummy_sjinfo(SpecialJoinInfo *sjinfo, Relids left_relids, |
| 662 |
Relids right_relids) |
| 663 |
{ |
| 664 |
sjinfo->type = T_SpecialJoinInfo; |
| 665 |
sjinfo->min_lefthand = left_relids; |
| 666 |
sjinfo->min_righthand = right_relids; |
| 667 |
sjinfo->syn_lefthand = left_relids; |
| 668 |
sjinfo->syn_righthand = right_relids; |
| 669 |
sjinfo->jointype = JOIN_INNER; |
| 670 |
sjinfo->ojrelid = 0; |
| 671 |
sjinfo->commute_above_l = NULL; |
| 672 |
sjinfo->commute_above_r = NULL; |
| 673 |
sjinfo->commute_below_l = NULL; |
| 674 |
sjinfo->commute_below_r = NULL; |
| 675 |
/* we don't bother trying to make the remaining fields valid */ |
| 676 |
sjinfo->lhs_strict = false; |
| 677 |
sjinfo->semi_can_btree = false; |
| 678 |
sjinfo->semi_can_hash = false; |
| 679 |
sjinfo->semi_operators = NIL; |
| 680 |
sjinfo->semi_rhs_exprs = NIL; |
| 681 |
} |
| 682 |
|
| 683 |
/* |
| 684 |
* make_join_rel |
| 685 |
* Find or create a join RelOptInfo that represents the join of |
| 686 |
* the two given rels, and add to it path information for paths |
| 687 |
* created with the two rels as outer and inner rel. |
| 688 |
* (The join rel may already contain paths generated from other |
| 689 |
* pairs of rels that add up to the same set of base rels.) |
| 690 |
* |
| 691 |
* NB: will return NULL if attempted join is not valid. This can happen |
| 692 |
* when working with outer joins, or with IN or EXISTS clauses that have been |
| 693 |
* turned into joins. |
| 694 |
*/ |
| 695 |
RelOptInfo * |
| 696 |
make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) |
| 697 |
{ |
| 698 |
Relids joinrelids; |
| 699 |
SpecialJoinInfo *sjinfo; |
| 700 |
bool reversed; |
| 701 |
List *pushed_down_joins = NIL; |
| 702 |
SpecialJoinInfo sjinfo_data; |
| 703 |
RelOptInfo *joinrel; |
| 704 |
List *restrictlist; |
| 705 |
|
| 706 |
/* We should never try to join two overlapping sets of rels. */ |
| 707 |
Assert(!bms_overlap(rel1->relids, rel2->relids)); |
| 708 |
|
| 709 |
/* Construct Relids set that identifies the joinrel (without OJ as yet). */ |
| 710 |
joinrelids = bms_union(rel1->relids, rel2->relids); |
| 711 |
|
| 712 |
/* Check validity and determine join type. */ |
| 713 |
if (!join_is_legal(root, rel1, rel2, joinrelids, |
| 714 |
&sjinfo, &reversed)) |
| 715 |
{ |
| 716 |
/* invalid join path */ |
| 717 |
bms_free(joinrelids); |
| 718 |
return NULL; |
| 719 |
} |
| 720 |
|
| 721 |
/* |
| 722 |
* Add outer join relid(s) to form the canonical relids. Any added outer |
| 723 |
* joins besides sjinfo itself are appended to pushed_down_joins. |
| 724 |
*/ |
| 725 |
joinrelids = add_outer_joins_to_relids(root, joinrelids, sjinfo, |
| 726 |
&pushed_down_joins); |
| 727 |
|
| 728 |
/* Swap rels if needed to match the join info. */ |
| 729 |
if (reversed) |
| 730 |
{ |
| 731 |
RelOptInfo *trel = rel1; |
| 732 |
|
| 733 |
rel1 = rel2; |
| 734 |
rel2 = trel; |
| 735 |
} |
| 736 |
|
| 737 |
/* |
| 738 |
* If it's a plain inner join, then we won't have found anything in |
| 739 |
* join_info_list. Make up a SpecialJoinInfo so that selectivity |
| 740 |
* estimation functions will know what's being joined. |
| 741 |
*/ |
| 742 |
if (sjinfo == NULL) |
| 743 |
{ |
| 744 |
sjinfo = &sjinfo_data; |
| 745 |
init_dummy_sjinfo(sjinfo, rel1->relids, rel2->relids); |
| 746 |
} |
| 747 |
|
| 748 |
/* |
| 749 |
* Find or build the join RelOptInfo, and compute the restrictlist that |
| 750 |
* goes with this particular joining. |
| 751 |
*/ |
| 752 |
joinrel = build_join_rel(root, joinrelids, rel1, rel2, |
| 753 |
sjinfo, pushed_down_joins, |
| 754 |
&restrictlist); |
| 755 |
|
| 756 |
/* |
| 757 |
* If we've already proven this join is empty, we needn't consider any |
| 758 |
* more paths for it. |
| 759 |
*/ |
| 760 |
if (is_dummy_rel(joinrel)) |
| 761 |
{ |
| 762 |
bms_free(joinrelids); |
| 763 |
return joinrel; |
| 764 |
} |
| 765 |
|
| 766 |
/* Add paths to the join relation. */ |
| 767 |
populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo, |
| 768 |
restrictlist); |
| 769 |
|
| 770 |
bms_free(joinrelids); |
| 771 |
|
| 772 |
return joinrel; |
| 773 |
} |
| 774 |
|
| 775 |
/* |
| 776 |
* add_outer_joins_to_relids |
| 777 |
* Add relids to input_relids to represent any outer joins that will be |
| 778 |
* calculated at this join. |
| 779 |
* |
| 780 |
* input_relids is the union of the relid sets of the two input relations. |
| 781 |
* Note that we modify this in-place and return it; caller must bms_copy() |
| 782 |
* it first, if a separate value is desired. |
| 783 |
* |
| 784 |
* sjinfo represents the join being performed. |
| 785 |
* |
| 786 |
* If the current join completes the calculation of any outer joins that |
| 787 |
* have been pushed down per outer-join identity 3, those relids will be |
| 788 |
* added to the result along with sjinfo's own relid. If pushed_down_joins |
| 789 |
* is not NULL, then also the SpecialJoinInfos for such added outer joins will |
| 790 |
* be appended to *pushed_down_joins (so caller must initialize it to NIL). |
| 791 |
*/ |
| 792 |
Relids |
| 793 |
add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids, |
| 794 |
SpecialJoinInfo *sjinfo, |
| 795 |
List **pushed_down_joins) |
| 796 |
{ |
| 797 |
/* Nothing to do if this isn't an outer join with an assigned relid. */ |
| 798 |
if (sjinfo == NULL || sjinfo->ojrelid == 0) |
| 799 |
return input_relids; |
| 800 |
|
| 801 |
/* |
| 802 |
* If it's not a left join, we have no rules that would permit executing |
| 803 |
* it in non-syntactic order, so just form the syntactic relid set. (This |
| 804 |
* is just a quick-exit test; we'd come to the same conclusion anyway, |
| 805 |
* since its commute_below_l and commute_above_l sets must be empty.) |
| 806 |
*/ |
| 807 |
if (sjinfo->jointype != JOIN_LEFT) |
| 808 |
return bms_add_member(input_relids, sjinfo->ojrelid); |
| 809 |
|
| 810 |
/* |
| 811 |
* We cannot add the OJ relid if this join has been pushed into the RHS of |
| 812 |
* a syntactically-lower left join per OJ identity 3. (If it has, then we |
| 813 |
* cannot claim that its outputs represent the final state of its RHS.) |
| 814 |
* There will not be any other OJs that can be added either, so we're |
| 815 |
* done. |
| 816 |
*/ |
| 817 |
if (!bms_is_subset(sjinfo->commute_below_l, input_relids)) |
| 818 |
return input_relids; |
| 819 |
|
| 820 |
/* OK to add OJ's own relid */ |
| 821 |
input_relids = bms_add_member(input_relids, sjinfo->ojrelid); |
| 822 |
|
| 823 |
/* |
| 824 |
* Contrariwise, if we are now forming the final result of such a commuted |
| 825 |
* pair of OJs, it's time to add the relid(s) of the pushed-down join(s). |
| 826 |
* We can skip this if this join was never a candidate to be pushed up. |
| 827 |
*/ |
| 828 |
if (sjinfo->commute_above_l) |
| 829 |
{ |
| 830 |
Relids commute_above_rels = bms_copy(sjinfo->commute_above_l); |
| 831 |
ListCell *lc; |
| 832 |
|
| 833 |
/* |
| 834 |
* The current join could complete the nulling of more than one |
| 835 |
* pushed-down join, so we have to examine all the SpecialJoinInfos. |
| 836 |
* Because join_info_list was built in bottom-up order, it's |
| 837 |
* sufficient to traverse it once: an ojrelid we add in one loop |
| 838 |
* iteration would not have affected decisions of earlier iterations. |
| 839 |
*/ |
| 840 |
foreach(lc, root->join_info_list) |
| 841 |
{ |
| 842 |
SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc); |
| 843 |
|
| 844 |
if (othersj == sjinfo || |
| 845 |
othersj->ojrelid == 0 || othersj->jointype != JOIN_LEFT) |
| 846 |
continue; /* definitely not interesting */ |
| 847 |
|
| 848 |
if (!bms_is_member(othersj->ojrelid, commute_above_rels)) |
| 849 |
continue; |
| 850 |
|
| 851 |
/* Add it if not already present but conditions now satisfied */ |
| 852 |
if (!bms_is_member(othersj->ojrelid, input_relids) && |
| 853 |
bms_is_subset(othersj->min_lefthand, input_relids) && |
| 854 |
bms_is_subset(othersj->min_righthand, input_relids) && |
| 855 |
bms_is_subset(othersj->commute_below_l, input_relids)) |
| 856 |
{ |
| 857 |
input_relids = bms_add_member(input_relids, othersj->ojrelid); |
| 858 |
/* report such pushed down outer joins, if asked */ |
| 859 |
if (pushed_down_joins != NULL) |
| 860 |
*pushed_down_joins = lappend(*pushed_down_joins, othersj); |
| 861 |
|
| 862 |
/* |
| 863 |
* We must also check any joins that othersj potentially |
| 864 |
* commutes with. They likewise must appear later in |
| 865 |
* join_info_list than othersj itself, so we can visit them |
| 866 |
* later in this loop. |
| 867 |
*/ |
| 868 |
commute_above_rels = bms_add_members(commute_above_rels, |
| 869 |
othersj->commute_above_l); |
| 870 |
} |
| 871 |
} |
| 872 |
} |
| 873 |
|
| 874 |
return input_relids; |
| 875 |
} |
| 876 |
|
| 877 |
/* |
| 878 |
* populate_joinrel_with_paths |
| 879 |
* Add paths to the given joinrel for given pair of joining relations. The |
| 880 |
* SpecialJoinInfo provides details about the join and the restrictlist |
| 881 |
* contains the join clauses and the other clauses applicable for given pair |
| 882 |
* of the joining relations. |
| 883 |
*/ |
| 884 |
static void |
| 885 |
populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, |
| 886 |
RelOptInfo *rel2, RelOptInfo *joinrel, |
| 887 |
SpecialJoinInfo *sjinfo, List *restrictlist) |
| 888 |
{ |
| 889 |
/* |
| 890 |
* Consider paths using each rel as both outer and inner. Depending on |
| 891 |
* the join type, a provably empty outer or inner rel might mean the join |
| 892 |
* is provably empty too; in which case throw away any previously computed |
| 893 |
* paths and mark the join as dummy. (We do it this way since it's |
| 894 |
* conceivable that dummy-ness of a multi-element join might only be |
| 895 |
* noticeable for certain construction paths.) |
| 896 |
* |
| 897 |
* Also, a provably constant-false join restriction typically means that |
| 898 |
* we can skip evaluating one or both sides of the join. We do this by |
| 899 |
* marking the appropriate rel as dummy. For outer joins, a |
| 900 |
* constant-false restriction that is pushed down still means the whole |
| 901 |
* join is dummy, while a non-pushed-down one means that no inner rows |
| 902 |
* will join so we can treat the inner rel as dummy. |
| 903 |
* |
| 904 |
* We need only consider the jointypes that appear in join_info_list, plus |
| 905 |
* JOIN_INNER. |
| 906 |
*/ |
| 907 |
switch (sjinfo->jointype) |
| 908 |
{ |
| 909 |
case JOIN_INNER: |
| 910 |
if (is_dummy_rel(rel1) || is_dummy_rel(rel2) || |
| 911 |
restriction_is_constant_false(restrictlist, joinrel, false)) |
| 912 |
{ |
| 913 |
mark_dummy_rel(joinrel); |
| 914 |
break; |
| 915 |
} |
| 916 |
add_paths_to_joinrel(root, joinrel, rel1, rel2, |
| 917 |
JOIN_INNER, sjinfo, |
| 918 |
restrictlist); |
| 919 |
add_paths_to_joinrel(root, joinrel, rel2, rel1, |
| 920 |
JOIN_INNER, sjinfo, |
| 921 |
restrictlist); |
| 922 |
break; |
| 923 |
case JOIN_LEFT: |
| 924 |
if (is_dummy_rel(rel1) || |
| 925 |
restriction_is_constant_false(restrictlist, joinrel, true)) |
| 926 |
{ |
| 927 |
mark_dummy_rel(joinrel); |
| 928 |
break; |
| 929 |
} |
| 930 |
if (restriction_is_constant_false(restrictlist, joinrel, false) && |
| 931 |
bms_is_subset(rel2->relids, sjinfo->syn_righthand)) |
| 932 |
mark_dummy_rel(rel2); |
| 933 |
add_paths_to_joinrel(root, joinrel, rel1, rel2, |
| 934 |
JOIN_LEFT, sjinfo, |
| 935 |
restrictlist); |
| 936 |
add_paths_to_joinrel(root, joinrel, rel2, rel1, |
| 937 |
JOIN_RIGHT, sjinfo, |
| 938 |
restrictlist); |
| 939 |
break; |
| 940 |
case JOIN_FULL: |
| 941 |
if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) || |
| 942 |
restriction_is_constant_false(restrictlist, joinrel, true)) |
| 943 |
{ |
| 944 |
mark_dummy_rel(joinrel); |
| 945 |
break; |
| 946 |
} |
| 947 |
add_paths_to_joinrel(root, joinrel, rel1, rel2, |
| 948 |
JOIN_FULL, sjinfo, |
| 949 |
restrictlist); |
| 950 |
add_paths_to_joinrel(root, joinrel, rel2, rel1, |
| 951 |
JOIN_FULL, sjinfo, |
| 952 |
restrictlist); |
| 953 |
|
| 954 |
/* |
| 955 |
* If there are join quals that aren't mergeable or hashable, we |
| 956 |
* may not be able to build any valid plan. Complain here so that |
| 957 |
* we can give a somewhat-useful error message. (Since we have no |
| 958 |
* flexibility of planning for a full join, there's no chance of |
| 959 |
* succeeding later with another pair of input rels.) |
| 960 |
*/ |
| 961 |
if (joinrel->pathlist == NIL) |
| 962 |
ereport(ERROR, |
| 963 |
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED), |
| 964 |
errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions"))); |
| 965 |
break; |
| 966 |
case JOIN_SEMI: |
| 967 |
|
| 968 |
/* |
| 969 |
* We might have a normal semijoin, or a case where we don't have |
| 970 |
* enough rels to do the semijoin but can unique-ify the RHS and |
| 971 |
* then do an innerjoin (see comments in join_is_legal). In the |
| 972 |
* latter case we can't apply JOIN_SEMI joining. |
| 973 |
*/ |
| 974 |
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) && |
| 975 |
bms_is_subset(sjinfo->min_righthand, rel2->relids)) |
| 976 |
{ |
| 977 |
if (is_dummy_rel(rel1) || is_dummy_rel(rel2) || |
| 978 |
restriction_is_constant_false(restrictlist, joinrel, false)) |
| 979 |
{ |
| 980 |
mark_dummy_rel(joinrel); |
| 981 |
break; |
| 982 |
} |
| 983 |
add_paths_to_joinrel(root, joinrel, rel1, rel2, |
| 984 |
JOIN_SEMI, sjinfo, |
| 985 |
restrictlist); |
| 986 |
add_paths_to_joinrel(root, joinrel, rel2, rel1, |
| 987 |
JOIN_RIGHT_SEMI, sjinfo, |
| 988 |
restrictlist); |
| 989 |
} |
| 990 |
|
| 991 |
/* |
| 992 |
* If we know how to unique-ify the RHS and one input rel is |
| 993 |
* exactly the RHS (not a superset) we can consider unique-ifying |
| 994 |
* it and then doing a regular join. (The create_unique_path |
| 995 |
* check here is probably redundant with what join_is_legal did, |
| 996 |
* but if so the check is cheap because it's cached. So test |
| 997 |
* anyway to be sure.) |
| 998 |
*/ |
| 999 |
if (bms_equal(sjinfo->syn_righthand, rel2->relids) && |
| 1000 |
create_unique_path(root, rel2, rel2->cheapest_total_path, |
| 1001 |
sjinfo) != NULL) |
| 1002 |
{ |
| 1003 |
if (is_dummy_rel(rel1) || is_dummy_rel(rel2) || |
| 1004 |
restriction_is_constant_false(restrictlist, joinrel, false)) |
| 1005 |
{ |
| 1006 |
mark_dummy_rel(joinrel); |
| 1007 |
break; |
| 1008 |
} |
| 1009 |
add_paths_to_joinrel(root, joinrel, rel1, rel2, |
| 1010 |
JOIN_UNIQUE_INNER, sjinfo, |
| 1011 |
restrictlist); |
| 1012 |
add_paths_to_joinrel(root, joinrel, rel2, rel1, |
| 1013 |
JOIN_UNIQUE_OUTER, sjinfo, |
| 1014 |
restrictlist); |
| 1015 |
} |
| 1016 |
break; |
| 1017 |
case JOIN_ANTI: |
| 1018 |
if (is_dummy_rel(rel1) || |
| 1019 |
restriction_is_constant_false(restrictlist, joinrel, true)) |
| 1020 |
{ |
| 1021 |
mark_dummy_rel(joinrel); |
| 1022 |
break; |
| 1023 |
} |
| 1024 |
if (restriction_is_constant_false(restrictlist, joinrel, false) && |
| 1025 |
bms_is_subset(rel2->relids, sjinfo->syn_righthand)) |
| 1026 |
mark_dummy_rel(rel2); |
| 1027 |
add_paths_to_joinrel(root, joinrel, rel1, rel2, |
| 1028 |
JOIN_ANTI, sjinfo, |
| 1029 |
restrictlist); |
| 1030 |
add_paths_to_joinrel(root, joinrel, rel2, rel1, |
| 1031 |
JOIN_RIGHT_ANTI, sjinfo, |
| 1032 |
restrictlist); |
| 1033 |
break; |
| 1034 |
default: |
| 1035 |
/* other values not expected here */ |
| 1036 |
elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype); |
| 1037 |
break; |
| 1038 |
} |
| 1039 |
|
| 1040 |
/* Apply partitionwise join technique, if possible. */ |
| 1041 |
try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist); |
| 1042 |
} |
| 1043 |
|
| 1044 |
|
| 1045 |
/* |
| 1046 |
* have_join_order_restriction |
| 1047 |
* Detect whether the two relations should be joined to satisfy |
| 1048 |
* a join-order restriction arising from special or lateral joins. |
| 1049 |
* |
| 1050 |
* In practice this is always used with have_relevant_joinclause(), and so |
| 1051 |
* could be merged with that function, but it seems clearer to separate the |
| 1052 |
* two concerns. We need this test because there are degenerate cases where |
| 1053 |
* a clauseless join must be performed to satisfy join-order restrictions. |
| 1054 |
* Also, if one rel has a lateral reference to the other, or both are needed |
| 1055 |
* to compute some PHV, we should consider joining them even if the join would |
| 1056 |
* be clauseless. |
| 1057 |
* |
| 1058 |
* Note: this is only a problem if one side of a degenerate outer join |
| 1059 |
* contains multiple rels, or a clauseless join is required within an |
| 1060 |
* IN/EXISTS RHS; else we will find a join path via the "last ditch" case in |
| 1061 |
* join_search_one_level(). We could dispense with this test if we were |
| 1062 |
* willing to try bushy plans in the "last ditch" case, but that seems much |
| 1063 |
* less efficient. |
| 1064 |
*/ |
| 1065 |
bool |
| 1066 |
have_join_order_restriction(PlannerInfo *root, |
| 1067 |
RelOptInfo *rel1, RelOptInfo *rel2) |
| 1068 |
{ |
| 1069 |
bool result = false; |
| 1070 |
ListCell *l; |
| 1071 |
|
| 1072 |
/* |
| 1073 |
* If either side has a direct lateral reference to the other, attempt the |
| 1074 |
* join regardless of outer-join considerations. |
| 1075 |
*/ |
| 1076 |
if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) || |
| 1077 |
bms_overlap(rel2->relids, rel1->direct_lateral_relids)) |
| 1078 |
return true; |
| 1079 |
|
| 1080 |
/* |
| 1081 |
* Likewise, if both rels are needed to compute some PlaceHolderVar, |
| 1082 |
* attempt the join regardless of outer-join considerations. (This is not |
| 1083 |
* very desirable, because a PHV with a large eval_at set will cause a lot |
| 1084 |
* of probably-useless joins to be considered, but failing to do this can |
| 1085 |
* cause us to fail to construct a plan at all.) |
| 1086 |
*/ |
| 1087 |
foreach(l, root->placeholder_list) |
| 1088 |
{ |
| 1089 |
PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l); |
| 1090 |
|
| 1091 |
if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) && |
| 1092 |
bms_is_subset(rel2->relids, phinfo->ph_eval_at)) |
| 1093 |
return true; |
| 1094 |
} |
| 1095 |
|
| 1096 |
/* |
| 1097 |
* It's possible that the rels correspond to the left and right sides of a |
| 1098 |
* degenerate outer join, that is, one with no joinclause mentioning the |
| 1099 |
* non-nullable side; in which case we should force the join to occur. |
| 1100 |
* |
| 1101 |
* Also, the two rels could represent a clauseless join that has to be |
| 1102 |
* completed to build up the LHS or RHS of an outer join. |
| 1103 |
*/ |
| 1104 |
foreach(l, root->join_info_list) |
| 1105 |
{ |
| 1106 |
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l); |
| 1107 |
|
| 1108 |
/* ignore full joins --- other mechanisms handle them */ |
| 1109 |
if (sjinfo->jointype == JOIN_FULL) |
| 1110 |
continue; |
| 1111 |
|
| 1112 |
/* Can we perform the SJ with these rels? */ |
| 1113 |
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) && |
| 1114 |
bms_is_subset(sjinfo->min_righthand, rel2->relids)) |
| 1115 |
{ |
| 1116 |
result = true; |
| 1117 |
break; |
| 1118 |
} |
| 1119 |
if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) && |
| 1120 |
bms_is_subset(sjinfo->min_righthand, rel1->relids)) |
| 1121 |
{ |
| 1122 |
result = true; |
| 1123 |
break; |
| 1124 |
} |
| 1125 |
|
| 1126 |
/* |
| 1127 |
* Might we need to join these rels to complete the RHS? We have to |
| 1128 |
* use "overlap" tests since either rel might include a lower SJ that |
| 1129 |
* has been proven to commute with this one. |
| 1130 |
*/ |
| 1131 |
if (bms_overlap(sjinfo->min_righthand, rel1->relids) && |
| 1132 |
bms_overlap(sjinfo->min_righthand, rel2->relids)) |
| 1133 |
{ |
| 1134 |
result = true; |
| 1135 |
break; |
| 1136 |
} |
| 1137 |
|
| 1138 |
/* Likewise for the LHS. */ |
| 1139 |
if (bms_overlap(sjinfo->min_lefthand, rel1->relids) && |
| 1140 |
bms_overlap(sjinfo->min_lefthand, rel2->relids)) |
| 1141 |
{ |
| 1142 |
result = true; |
| 1143 |
break; |
| 1144 |
} |
| 1145 |
} |
| 1146 |
|
| 1147 |
/* |
| 1148 |
* We do not force the join to occur if either input rel can legally be |
| 1149 |
* joined to anything else using joinclauses. This essentially means that |
| 1150 |
* clauseless bushy joins are put off as long as possible. The reason is |
| 1151 |
* that when there is a join order restriction high up in the join tree |
| 1152 |
* (that is, with many rels inside the LHS or RHS), we would otherwise |
| 1153 |
* expend lots of effort considering very stupid join combinations within |
| 1154 |
* its LHS or RHS. |
| 1155 |
*/ |
| 1156 |
if (result) |
| 1157 |
{ |
| 1158 |
if (has_legal_joinclause(root, rel1) || |
| 1159 |
has_legal_joinclause(root, rel2)) |
| 1160 |
result = false; |
| 1161 |
} |
| 1162 |
|
| 1163 |
return result; |
| 1164 |
} |
| 1165 |
|
| 1166 |
|
| 1167 |
/* |
| 1168 |
* has_join_restriction |
| 1169 |
* Detect whether the specified relation has join-order restrictions, |
| 1170 |
* due to being inside an outer join or an IN (sub-SELECT), |
| 1171 |
* or participating in any LATERAL references or multi-rel PHVs. |
| 1172 |
* |
| 1173 |
* Essentially, this tests whether have_join_order_restriction() could |
| 1174 |
* succeed with this rel and some other one. It's OK if we sometimes |
| 1175 |
* say "true" incorrectly. (Therefore, we don't bother with the relatively |
| 1176 |
* expensive has_legal_joinclause test.) |
| 1177 |
*/ |
| 1178 |
static bool |
| 1179 |
has_join_restriction(PlannerInfo *root, RelOptInfo *rel) |
| 1180 |
{ |
| 1181 |
ListCell *l; |
| 1182 |
|
| 1183 |
if (rel->lateral_relids != NULL || rel->lateral_referencers != NULL) |
| 1184 |
return true; |
| 1185 |
|
| 1186 |
foreach(l, root->placeholder_list) |
| 1187 |
{ |
| 1188 |
PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l); |
| 1189 |
|
| 1190 |
if (bms_is_subset(rel->relids, phinfo->ph_eval_at) && |
| 1191 |
!bms_equal(rel->relids, phinfo->ph_eval_at)) |
| 1192 |
return true; |
| 1193 |
} |
| 1194 |
|
| 1195 |
foreach(l, root->join_info_list) |
| 1196 |
{ |
| 1197 |
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l); |
| 1198 |
|
| 1199 |
/* ignore full joins --- other mechanisms preserve their ordering */ |
| 1200 |
if (sjinfo->jointype == JOIN_FULL) |
| 1201 |
continue; |
| 1202 |
|
| 1203 |
/* ignore if SJ is already contained in rel */ |
| 1204 |
if (bms_is_subset(sjinfo->min_lefthand, rel->relids) && |
| 1205 |
bms_is_subset(sjinfo->min_righthand, rel->relids)) |
| 1206 |
continue; |
| 1207 |
|
| 1208 |
/* restricted if it overlaps LHS or RHS, but doesn't contain SJ */ |
| 1209 |
if (bms_overlap(sjinfo->min_lefthand, rel->relids) || |
| 1210 |
bms_overlap(sjinfo->min_righthand, rel->relids)) |
| 1211 |
return true; |
| 1212 |
} |
| 1213 |
|
| 1214 |
return false; |
| 1215 |
} |
| 1216 |
|
| 1217 |
|
| 1218 |
/* |
| 1219 |
* has_legal_joinclause |
| 1220 |
* Detect whether the specified relation can legally be joined |
| 1221 |
* to any other rels using join clauses. |
| 1222 |
* |
| 1223 |
* We consider only joins to single other relations in the current |
| 1224 |
* initial_rels list. This is sufficient to get a "true" result in most real |
| 1225 |
* queries, and an occasional erroneous "false" will only cost a bit more |
| 1226 |
* planning time. The reason for this limitation is that considering joins to |
| 1227 |
* other joins would require proving that the other join rel can legally be |
| 1228 |
* formed, which seems like too much trouble for something that's only a |
| 1229 |
* heuristic to save planning time. (Note: we must look at initial_rels |
| 1230 |
* and not all of the query, since when we are planning a sub-joinlist we |
| 1231 |
* may be forced to make clauseless joins within initial_rels even though |
| 1232 |
* there are join clauses linking to other parts of the query.) |
| 1233 |
*/ |
| 1234 |
static bool |
| 1235 |
has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel) |
| 1236 |
{ |
| 1237 |
ListCell *lc; |
| 1238 |
|
| 1239 |
foreach(lc, root->initial_rels) |
| 1240 |
{ |
| 1241 |
RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc); |
| 1242 |
|
| 1243 |
/* ignore rels that are already in "rel" */ |
| 1244 |
if (bms_overlap(rel->relids, rel2->relids)) |
| 1245 |
continue; |
| 1246 |
|
| 1247 |
if (have_relevant_joinclause(root, rel, rel2)) |
| 1248 |
{ |
| 1249 |
Relids joinrelids; |
| 1250 |
SpecialJoinInfo *sjinfo; |
| 1251 |
bool reversed; |
| 1252 |
|
| 1253 |
/* join_is_legal needs relids of the union */ |
| 1254 |
joinrelids = bms_union(rel->relids, rel2->relids); |
| 1255 |
|
| 1256 |
if (join_is_legal(root, rel, rel2, joinrelids, |
| 1257 |
&sjinfo, &reversed)) |
| 1258 |
{ |
| 1259 |
/* Yes, this will work */ |
| 1260 |
bms_free(joinrelids); |
| 1261 |
return true; |
| 1262 |
} |
| 1263 |
|
| 1264 |
bms_free(joinrelids); |
| 1265 |
} |
| 1266 |
} |
| 1267 |
|
| 1268 |
return false; |
| 1269 |
} |
| 1270 |
|
| 1271 |
|
| 1272 |
/* |
| 1273 |
* is_dummy_rel --- has relation been proven empty? |
| 1274 |
*/ |
| 1275 |
bool |
| 1276 |
is_dummy_rel(RelOptInfo *rel) |
| 1277 |
{ |
| 1278 |
Path *path; |
| 1279 |
|
| 1280 |
/* |
| 1281 |
* A rel that is known dummy will have just one path that is a childless |
| 1282 |
* Append. (Even if somehow it has more paths, a childless Append will |
| 1283 |
* have cost zero and hence should be at the front of the pathlist.) |
| 1284 |
*/ |
| 1285 |
if (rel->pathlist == NIL) |
| 1286 |
return false; |
| 1287 |
path = (Path *) linitial(rel->pathlist); |
| 1288 |
|
| 1289 |
/* |
| 1290 |
* Initially, a dummy path will just be a childless Append. But in later |
| 1291 |
* planning stages we might stick a ProjectSetPath and/or ProjectionPath |
| 1292 |
* on top, since Append can't project. Rather than make assumptions about |
| 1293 |
* which combinations can occur, just descend through whatever we find. |
| 1294 |
*/ |
| 1295 |
for (;;) |
| 1296 |
{ |
| 1297 |
if (IsA(path, ProjectionPath)) |
| 1298 |
path = ((ProjectionPath *) path)->subpath; |
| 1299 |
else if (IsA(path, ProjectSetPath)) |
| 1300 |
path = ((ProjectSetPath *) path)->subpath; |
| 1301 |
else |
| 1302 |
break; |
| 1303 |
} |
| 1304 |
if (IS_DUMMY_APPEND(path)) |
| 1305 |
return true; |
| 1306 |
return false; |
| 1307 |
} |
| 1308 |
|
| 1309 |
/* |
| 1310 |
* Mark a relation as proven empty. |
| 1311 |
* |
| 1312 |
* During GEQO planning, this can get invoked more than once on the same |
| 1313 |
* baserel struct, so it's worth checking to see if the rel is already marked |
| 1314 |
* dummy. |
| 1315 |
* |
| 1316 |
* Also, when called during GEQO join planning, we are in a short-lived |
| 1317 |
* memory context. We must make sure that the dummy path attached to a |
| 1318 |
* baserel survives the GEQO cycle, else the baserel is trashed for future |
| 1319 |
* GEQO cycles. On the other hand, when we are marking a joinrel during GEQO, |
| 1320 |
* we don't want the dummy path to clutter the main planning context. Upshot |
| 1321 |
* is that the best solution is to explicitly make the dummy path in the same |
| 1322 |
* context the given RelOptInfo is in. |
| 1323 |
*/ |
| 1324 |
void |
| 1325 |
mark_dummy_rel(RelOptInfo *rel) |
| 1326 |
{ |
| 1327 |
MemoryContext oldcontext; |
| 1328 |
|
| 1329 |
/* Already marked? */ |
| 1330 |
if (is_dummy_rel(rel)) |
| 1331 |
return; |
| 1332 |
|
| 1333 |
/* No, so choose correct context to make the dummy path in */ |
| 1334 |
oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel)); |
| 1335 |
|
| 1336 |
/* Set dummy size estimate */ |
| 1337 |
rel->rows = 0; |
| 1338 |
|
| 1339 |
/* Evict any previously chosen paths */ |
| 1340 |
rel->pathlist = NIL; |
| 1341 |
rel->partial_pathlist = NIL; |
| 1342 |
|
| 1343 |
/* Set up the dummy path */ |
| 1344 |
add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL, |
| 1345 |
NIL, rel->lateral_relids, |
| 1346 |
0, false, -1)); |
| 1347 |
|
| 1348 |
/* Set or update cheapest_total_path and related fields */ |
| 1349 |
set_cheapest(rel); |
| 1350 |
|
| 1351 |
MemoryContextSwitchTo(oldcontext); |
| 1352 |
} |
| 1353 |
|
| 1354 |
|
| 1355 |
/* |
| 1356 |
* restriction_is_constant_false --- is a restrictlist just FALSE? |
| 1357 |
* |
| 1358 |
* In cases where a qual is provably constant FALSE, eval_const_expressions |
| 1359 |
* will generally have thrown away anything that's ANDed with it. In outer |
| 1360 |
* join situations this will leave us computing cartesian products only to |
| 1361 |
* decide there's no match for an outer row, which is pretty stupid. So, |
| 1362 |
* we need to detect the case. |
| 1363 |
* |
| 1364 |
* If only_pushed_down is true, then consider only quals that are pushed-down |
| 1365 |
* from the point of view of the joinrel. |
| 1366 |
*/ |
| 1367 |
static bool |
| 1368 |
restriction_is_constant_false(List *restrictlist, |
| 1369 |
RelOptInfo *joinrel, |
| 1370 |
bool only_pushed_down) |
| 1371 |
{ |
| 1372 |
ListCell *lc; |
| 1373 |
|
| 1374 |
/* |
| 1375 |
* Despite the above comment, the restriction list we see here might |
| 1376 |
* possibly have other members besides the FALSE constant, since other |
| 1377 |
* quals could get "pushed down" to the outer join level. So we check |
| 1378 |
* each member of the list. |
| 1379 |
*/ |
| 1380 |
foreach(lc, restrictlist) |
| 1381 |
{ |
| 1382 |
RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc); |
| 1383 |
|
| 1384 |
if (only_pushed_down && !RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids)) |
| 1385 |
continue; |
| 1386 |
|
| 1387 |
if (rinfo->clause && IsA(rinfo->clause, Const)) |
| 1388 |
{ |
| 1389 |
Const *con = (Const *) rinfo->clause; |
| 1390 |
|
| 1391 |
/* constant NULL is as good as constant FALSE for our purposes */ |
| 1392 |
if (con->constisnull) |
| 1393 |
return true; |
| 1394 |
if (!DatumGetBool(con->constvalue)) |
| 1395 |
return true; |
| 1396 |
} |
| 1397 |
} |
| 1398 |
return false; |
| 1399 |
} |
| 1400 |
|
| 1401 |
/* |
| 1402 |
* Assess whether join between given two partitioned relations can be broken |
| 1403 |
* down into joins between matching partitions; a technique called |
| 1404 |
* "partitionwise join" |
| 1405 |
* |
| 1406 |
* Partitionwise join is possible when a. Joining relations have same |
| 1407 |
* partitioning scheme b. There exists an equi-join between the partition keys |
| 1408 |
* of the two relations. |
| 1409 |
* |
| 1410 |
* Partitionwise join is planned as follows (details: optimizer/README.) |
| 1411 |
* |
| 1412 |
* 1. Create the RelOptInfos for joins between matching partitions i.e |
| 1413 |
* child-joins and add paths to them. |
| 1414 |
* |
| 1415 |
* 2. Construct Append or MergeAppend paths across the set of child joins. |
| 1416 |
* This second phase is implemented by generate_partitionwise_join_paths(). |
| 1417 |
* |
| 1418 |
* The RelOptInfo, SpecialJoinInfo and restrictlist for each child join are |
| 1419 |
* obtained by translating the respective parent join structures. |
| 1420 |
*/ |
| 1421 |
static void |
| 1422 |
try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, |
| 1423 |
RelOptInfo *joinrel, SpecialJoinInfo *parent_sjinfo, |
| 1424 |
List *parent_restrictlist) |
| 1425 |
{ |
| 1426 |
bool rel1_is_simple = IS_SIMPLE_REL(rel1); |
| 1427 |
bool rel2_is_simple = IS_SIMPLE_REL(rel2); |
| 1428 |
List *parts1 = NIL; |
| 1429 |
List *parts2 = NIL; |
| 1430 |
ListCell *lcr1 = NULL; |
| 1431 |
ListCell *lcr2 = NULL; |
| 1432 |
int cnt_parts; |
| 1433 |
|
| 1434 |
/* Guard against stack overflow due to overly deep partition hierarchy. */ |
| 1435 |
check_stack_depth(); |
| 1436 |
|
| 1437 |
/* Nothing to do, if the join relation is not partitioned. */ |
| 1438 |
if (joinrel->part_scheme == NULL || joinrel->nparts == 0) |
| 1439 |
return; |
| 1440 |
|
| 1441 |
/* The join relation should have consider_partitionwise_join set. */ |
| 1442 |
Assert(joinrel->consider_partitionwise_join); |
| 1443 |
|
| 1444 |
/* |
| 1445 |
* We can not perform partitionwise join if either of the joining |
| 1446 |
* relations is not partitioned. |
| 1447 |
*/ |
| 1448 |
if (!IS_PARTITIONED_REL(rel1) || !IS_PARTITIONED_REL(rel2)) |
| 1449 |
return; |
| 1450 |
|
| 1451 |
Assert(REL_HAS_ALL_PART_PROPS(rel1) && REL_HAS_ALL_PART_PROPS(rel2)); |
| 1452 |
|
| 1453 |
/* The joining relations should have consider_partitionwise_join set. */ |
| 1454 |
Assert(rel1->consider_partitionwise_join && |
| 1455 |
rel2->consider_partitionwise_join); |
| 1456 |
|
| 1457 |
/* |
| 1458 |
* The partition scheme of the join relation should match that of the |
| 1459 |
* joining relations. |
| 1460 |
*/ |
| 1461 |
Assert(joinrel->part_scheme == rel1->part_scheme && |
| 1462 |
joinrel->part_scheme == rel2->part_scheme); |
| 1463 |
|
| 1464 |
Assert(!(joinrel->partbounds_merged && (joinrel->nparts <= 0))); |
| 1465 |
|
| 1466 |
compute_partition_bounds(root, rel1, rel2, joinrel, parent_sjinfo, |
| 1467 |
&parts1, &parts2); |
| 1468 |
|
| 1469 |
if (joinrel->partbounds_merged) |
| 1470 |
{ |
| 1471 |
lcr1 = list_head(parts1); |
| 1472 |
lcr2 = list_head(parts2); |
| 1473 |
} |
| 1474 |
|
| 1475 |
/* |
| 1476 |
* Create child-join relations for this partitioned join, if those don't |
| 1477 |
* exist. Add paths to child-joins for a pair of child relations |
| 1478 |
* corresponding to the given pair of parent relations. |
| 1479 |
*/ |
| 1480 |
for (cnt_parts = 0; cnt_parts < joinrel->nparts; cnt_parts++) |
| 1481 |
{ |
| 1482 |
RelOptInfo *child_rel1; |
| 1483 |
RelOptInfo *child_rel2; |
| 1484 |
bool rel1_empty; |
| 1485 |
bool rel2_empty; |
| 1486 |
SpecialJoinInfo *child_sjinfo; |
| 1487 |
List *child_restrictlist; |
| 1488 |
RelOptInfo *child_joinrel; |
| 1489 |
AppendRelInfo **appinfos; |
| 1490 |
int nappinfos; |
| 1491 |
Relids child_relids; |
| 1492 |
|
| 1493 |
if (joinrel->partbounds_merged) |
| 1494 |
{ |
| 1495 |
child_rel1 = lfirst_node(RelOptInfo, lcr1); |
| 1496 |
child_rel2 = lfirst_node(RelOptInfo, lcr2); |
| 1497 |
lcr1 = lnext(parts1, lcr1); |
| 1498 |
lcr2 = lnext(parts2, lcr2); |
| 1499 |
} |
| 1500 |
else |
| 1501 |
{ |
| 1502 |
child_rel1 = rel1->part_rels[cnt_parts]; |
| 1503 |
child_rel2 = rel2->part_rels[cnt_parts]; |
| 1504 |
} |
| 1505 |
|
| 1506 |
rel1_empty = (child_rel1 == NULL || IS_DUMMY_REL(child_rel1)); |
| 1507 |
rel2_empty = (child_rel2 == NULL || IS_DUMMY_REL(child_rel2)); |
| 1508 |
|
| 1509 |
/* |
| 1510 |
* Check for cases where we can prove that this segment of the join |
| 1511 |
* returns no rows, due to one or both inputs being empty (including |
| 1512 |
* inputs that have been pruned away entirely). If so just ignore it. |
| 1513 |
* These rules are equivalent to populate_joinrel_with_paths's rules |
| 1514 |
* for dummy input relations. |
| 1515 |
*/ |
| 1516 |
switch (parent_sjinfo->jointype) |
| 1517 |
{ |
| 1518 |
case JOIN_INNER: |
| 1519 |
case JOIN_SEMI: |
| 1520 |
if (rel1_empty || rel2_empty) |
| 1521 |
continue; /* ignore this join segment */ |
| 1522 |
break; |
| 1523 |
case JOIN_LEFT: |
| 1524 |
case JOIN_ANTI: |
| 1525 |
if (rel1_empty) |
| 1526 |
continue; /* ignore this join segment */ |
| 1527 |
break; |
| 1528 |
case JOIN_FULL: |
| 1529 |
if (rel1_empty && rel2_empty) |
| 1530 |
continue; /* ignore this join segment */ |
| 1531 |
break; |
| 1532 |
default: |
| 1533 |
/* other values not expected here */ |
| 1534 |
elog(ERROR, "unrecognized join type: %d", |
| 1535 |
(int) parent_sjinfo->jointype); |
| 1536 |
break; |
| 1537 |
} |
| 1538 |
|
| 1539 |
/* |
| 1540 |
* If a child has been pruned entirely then we can't generate paths |
| 1541 |
* for it, so we have to reject partitionwise joining unless we were |
| 1542 |
* able to eliminate this partition above. |
| 1543 |
*/ |
| 1544 |
if (child_rel1 == NULL || child_rel2 == NULL) |
| 1545 |
{ |
| 1546 |
/* |
| 1547 |
* Mark the joinrel as unpartitioned so that later functions treat |
| 1548 |
* it correctly. |
| 1549 |
*/ |
| 1550 |
joinrel->nparts = 0; |
| 1551 |
return; |
| 1552 |
} |
| 1553 |
|
| 1554 |
/* |
| 1555 |
* If a leaf relation has consider_partitionwise_join=false, it means |
| 1556 |
* that it's a dummy relation for which we skipped setting up tlist |
| 1557 |
* expressions and adding EC members in set_append_rel_size(), so |
| 1558 |
* again we have to fail here. |
| 1559 |
*/ |
| 1560 |
if (rel1_is_simple && !child_rel1->consider_partitionwise_join) |
| 1561 |
{ |
| 1562 |
Assert(child_rel1->reloptkind == RELOPT_OTHER_MEMBER_REL); |
| 1563 |
Assert(IS_DUMMY_REL(child_rel1)); |
| 1564 |
joinrel->nparts = 0; |
| 1565 |
return; |
| 1566 |
} |
| 1567 |
if (rel2_is_simple && !child_rel2->consider_partitionwise_join) |
| 1568 |
{ |
| 1569 |
Assert(child_rel2->reloptkind == RELOPT_OTHER_MEMBER_REL); |
| 1570 |
Assert(IS_DUMMY_REL(child_rel2)); |
| 1571 |
joinrel->nparts = 0; |
| 1572 |
return; |
| 1573 |
} |
| 1574 |
|
| 1575 |
/* We should never try to join two overlapping sets of rels. */ |
| 1576 |
Assert(!bms_overlap(child_rel1->relids, child_rel2->relids)); |
| 1577 |
|
| 1578 |
/* |
| 1579 |
* Construct SpecialJoinInfo from parent join relations's |
| 1580 |
* SpecialJoinInfo. |
| 1581 |
*/ |
| 1582 |
child_sjinfo = build_child_join_sjinfo(root, parent_sjinfo, |
| 1583 |
child_rel1->relids, |
| 1584 |
child_rel2->relids); |
| 1585 |
|
| 1586 |
/* Find the AppendRelInfo structures */ |
| 1587 |
child_relids = bms_union(child_rel1->relids, child_rel2->relids); |
| 1588 |
appinfos = find_appinfos_by_relids(root, child_relids, |
| 1589 |
&nappinfos); |
| 1590 |
|
| 1591 |
/* |
| 1592 |
* Construct restrictions applicable to the child join from those |
| 1593 |
* applicable to the parent join. |
| 1594 |
*/ |
| 1595 |
child_restrictlist = |
| 1596 |
(List *) adjust_appendrel_attrs(root, |
| 1597 |
(Node *) parent_restrictlist, |
| 1598 |
nappinfos, appinfos); |
| 1599 |
|
| 1600 |
/* Find or construct the child join's RelOptInfo */ |
| 1601 |
child_joinrel = joinrel->part_rels[cnt_parts]; |
| 1602 |
if (!child_joinrel) |
| 1603 |
{ |
| 1604 |
child_joinrel = build_child_join_rel(root, child_rel1, child_rel2, |
| 1605 |
joinrel, child_restrictlist, |
| 1606 |
child_sjinfo, nappinfos, appinfos); |
| 1607 |
joinrel->part_rels[cnt_parts] = child_joinrel; |
| 1608 |
joinrel->live_parts = bms_add_member(joinrel->live_parts, cnt_parts); |
| 1609 |
joinrel->all_partrels = bms_add_members(joinrel->all_partrels, |
| 1610 |
child_joinrel->relids); |
| 1611 |
} |
| 1612 |
|
| 1613 |
/* Assert we got the right one */ |
| 1614 |
Assert(bms_equal(child_joinrel->relids, |
| 1615 |
adjust_child_relids(joinrel->relids, |
| 1616 |
nappinfos, appinfos))); |
| 1617 |
|
| 1618 |
/* And make paths for the child join */ |
| 1619 |
populate_joinrel_with_paths(root, child_rel1, child_rel2, |
| 1620 |
child_joinrel, child_sjinfo, |
| 1621 |
child_restrictlist); |
| 1622 |
|
| 1623 |
/* |
| 1624 |
* When there are thousands of partitions involved, this loop will |
| 1625 |
* accumulate a significant amount of memory usage from objects that |
| 1626 |
* are only needed within the loop. Free these local objects eagerly |
| 1627 |
* at the end of each iteration. |
| 1628 |
*/ |
| 1629 |
pfree(appinfos); |
| 1630 |
bms_free(child_relids); |
| 1631 |
free_child_join_sjinfo(child_sjinfo, parent_sjinfo); |
| 1632 |
} |
| 1633 |
} |
| 1634 |
|
| 1635 |
/* |
| 1636 |
* Construct the SpecialJoinInfo for a child-join by translating |
| 1637 |
* SpecialJoinInfo for the join between parents. left_relids and right_relids |
| 1638 |
* are the relids of left and right side of the join respectively. |
| 1639 |
* |
| 1640 |
* If translations are added to or removed from this function, consider |
| 1641 |
* updating free_child_join_sjinfo() accordingly. |
| 1642 |
*/ |
| 1643 |
static SpecialJoinInfo * |
| 1644 |
build_child_join_sjinfo(PlannerInfo *root, SpecialJoinInfo *parent_sjinfo, |
| 1645 |
Relids left_relids, Relids right_relids) |
| 1646 |
{ |
| 1647 |
SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo); |
| 1648 |
AppendRelInfo **left_appinfos; |
| 1649 |
int left_nappinfos; |
| 1650 |
AppendRelInfo **right_appinfos; |
| 1651 |
int right_nappinfos; |
| 1652 |
|
| 1653 |
/* Dummy SpecialJoinInfos can be created without any translation. */ |
| 1654 |
if (parent_sjinfo->jointype == JOIN_INNER) |
| 1655 |
{ |
| 1656 |
Assert(parent_sjinfo->ojrelid == 0); |
| 1657 |
init_dummy_sjinfo(sjinfo, left_relids, right_relids); |
| 1658 |
return sjinfo; |
| 1659 |
} |
| 1660 |
|
| 1661 |
memcpy(sjinfo, parent_sjinfo, sizeof(SpecialJoinInfo)); |
| 1662 |
left_appinfos = find_appinfos_by_relids(root, left_relids, |
| 1663 |
&left_nappinfos); |
| 1664 |
right_appinfos = find_appinfos_by_relids(root, right_relids, |
| 1665 |
&right_nappinfos); |
| 1666 |
|
| 1667 |
sjinfo->min_lefthand = adjust_child_relids(sjinfo->min_lefthand, |
| 1668 |
left_nappinfos, left_appinfos); |
| 1669 |
sjinfo->min_righthand = adjust_child_relids(sjinfo->min_righthand, |
| 1670 |
right_nappinfos, |
| 1671 |
right_appinfos); |
| 1672 |
sjinfo->syn_lefthand = adjust_child_relids(sjinfo->syn_lefthand, |
| 1673 |
left_nappinfos, left_appinfos); |
| 1674 |
sjinfo->syn_righthand = adjust_child_relids(sjinfo->syn_righthand, |
| 1675 |
right_nappinfos, |
| 1676 |
right_appinfos); |
| 1677 |
/* outer-join relids need no adjustment */ |
| 1678 |
sjinfo->semi_rhs_exprs = (List *) adjust_appendrel_attrs(root, |
| 1679 |
(Node *) sjinfo->semi_rhs_exprs, |
| 1680 |
right_nappinfos, |
| 1681 |
right_appinfos); |
| 1682 |
|
| 1683 |
pfree(left_appinfos); |
| 1684 |
pfree(right_appinfos); |
| 1685 |
|
| 1686 |
return sjinfo; |
| 1687 |
} |
| 1688 |
|
| 1689 |
/* |
| 1690 |
* free_child_join_sjinfo |
| 1691 |
* Free memory consumed by a SpecialJoinInfo created by |
| 1692 |
* build_child_join_sjinfo() |
| 1693 |
* |
| 1694 |
* Only members that are translated copies of their counterpart in the parent |
| 1695 |
* SpecialJoinInfo are freed here. |
| 1696 |
*/ |
| 1697 |
static void |
| 1698 |
free_child_join_sjinfo(SpecialJoinInfo *child_sjinfo, |
| 1699 |
SpecialJoinInfo *parent_sjinfo) |
| 1700 |
{ |
| 1701 |
/* |
| 1702 |
* Dummy SpecialJoinInfos of inner joins do not have any translated fields |
| 1703 |
* and hence no fields that to be freed. |
| 1704 |
*/ |
| 1705 |
if (child_sjinfo->jointype != JOIN_INNER) |
| 1706 |
{ |
| 1707 |
if (child_sjinfo->min_lefthand != parent_sjinfo->min_lefthand) |
| 1708 |
bms_free(child_sjinfo->min_lefthand); |
| 1709 |
|
| 1710 |
if (child_sjinfo->min_righthand != parent_sjinfo->min_righthand) |
| 1711 |
bms_free(child_sjinfo->min_righthand); |
| 1712 |
|
| 1713 |
if (child_sjinfo->syn_lefthand != parent_sjinfo->syn_lefthand) |
| 1714 |
bms_free(child_sjinfo->syn_lefthand); |
| 1715 |
|
| 1716 |
if (child_sjinfo->syn_righthand != parent_sjinfo->syn_righthand) |
| 1717 |
bms_free(child_sjinfo->syn_righthand); |
| 1718 |
|
| 1719 |
Assert(child_sjinfo->commute_above_l == parent_sjinfo->commute_above_l); |
| 1720 |
Assert(child_sjinfo->commute_above_r == parent_sjinfo->commute_above_r); |
| 1721 |
Assert(child_sjinfo->commute_below_l == parent_sjinfo->commute_below_l); |
| 1722 |
Assert(child_sjinfo->commute_below_r == parent_sjinfo->commute_below_r); |
| 1723 |
|
| 1724 |
Assert(child_sjinfo->semi_operators == parent_sjinfo->semi_operators); |
| 1725 |
|
| 1726 |
/* |
| 1727 |
* semi_rhs_exprs may in principle be freed, but a simple pfree() does |
| 1728 |
* not suffice, so we leave it alone. |
| 1729 |
*/ |
| 1730 |
} |
| 1731 |
|
| 1732 |
pfree(child_sjinfo); |
| 1733 |
} |
| 1734 |
|
| 1735 |
/* |
| 1736 |
* compute_partition_bounds |
| 1737 |
* Compute the partition bounds for a join rel from those for inputs |
| 1738 |
*/ |
| 1739 |
static void |
| 1740 |
compute_partition_bounds(PlannerInfo *root, RelOptInfo *rel1, |
| 1741 |
RelOptInfo *rel2, RelOptInfo *joinrel, |
| 1742 |
SpecialJoinInfo *parent_sjinfo, |
| 1743 |
List **parts1, List **parts2) |
| 1744 |
{ |
| 1745 |
/* |
| 1746 |
* If we don't have the partition bounds for the join rel yet, try to |
| 1747 |
* compute those along with pairs of partitions to be joined. |
| 1748 |
*/ |
| 1749 |
if (joinrel->nparts == -1) |
| 1750 |
{ |
| 1751 |
PartitionScheme part_scheme = joinrel->part_scheme; |
| 1752 |
PartitionBoundInfo boundinfo = NULL; |
| 1753 |
int nparts = 0; |
| 1754 |
|
| 1755 |
Assert(joinrel->boundinfo == NULL); |
| 1756 |
Assert(joinrel->part_rels == NULL); |
| 1757 |
|
| 1758 |
/* |
| 1759 |
* See if the partition bounds for inputs are exactly the same, in |
| 1760 |
* which case we don't need to work hard: the join rel will have the |
| 1761 |
* same partition bounds as inputs, and the partitions with the same |
| 1762 |
* cardinal positions will form the pairs. |
| 1763 |
* |
| 1764 |
* Note: even in cases where one or both inputs have merged bounds, it |
| 1765 |
* would be possible for both the bounds to be exactly the same, but |
| 1766 |
* it seems unlikely to be worth the cycles to check. |
| 1767 |
*/ |
| 1768 |
if (!rel1->partbounds_merged && |
| 1769 |
!rel2->partbounds_merged && |
| 1770 |
rel1->nparts == rel2->nparts && |
| 1771 |
partition_bounds_equal(part_scheme->partnatts, |
| 1772 |
part_scheme->parttyplen, |
| 1773 |
part_scheme->parttypbyval, |
| 1774 |
rel1->boundinfo, rel2->boundinfo)) |
| 1775 |
{ |
| 1776 |
boundinfo = rel1->boundinfo; |
| 1777 |
nparts = rel1->nparts; |
| 1778 |
} |
| 1779 |
else |
| 1780 |
{ |
| 1781 |
/* Try merging the partition bounds for inputs. */ |
| 1782 |
boundinfo = partition_bounds_merge(part_scheme->partnatts, |
| 1783 |
part_scheme->partsupfunc, |
| 1784 |
part_scheme->partcollation, |
| 1785 |
rel1, rel2, |
| 1786 |
parent_sjinfo->jointype, |
| 1787 |
parts1, parts2); |
| 1788 |
if (boundinfo == NULL) |
| 1789 |
{ |
| 1790 |
joinrel->nparts = 0; |
| 1791 |
return; |
| 1792 |
} |
| 1793 |
nparts = list_length(*parts1); |
| 1794 |
joinrel->partbounds_merged = true; |
| 1795 |
} |
| 1796 |
|
| 1797 |
Assert(nparts > 0); |
| 1798 |
joinrel->boundinfo = boundinfo; |
| 1799 |
joinrel->nparts = nparts; |
| 1800 |
joinrel->part_rels = |
| 1801 |
(RelOptInfo **) palloc0(sizeof(RelOptInfo *) * nparts); |
| 1802 |
} |
| 1803 |
else |
| 1804 |
{ |
| 1805 |
Assert(joinrel->nparts > 0); |
| 1806 |
Assert(joinrel->boundinfo); |
| 1807 |
Assert(joinrel->part_rels); |
| 1808 |
|
| 1809 |
/* |
| 1810 |
* If the join rel's partbounds_merged flag is true, it means inputs |
| 1811 |
* are not guaranteed to have the same partition bounds, therefore we |
| 1812 |
* can't assume that the partitions at the same cardinal positions |
| 1813 |
* form the pairs; let get_matching_part_pairs() generate the pairs. |
| 1814 |
* Otherwise, nothing to do since we can assume that. |
| 1815 |
*/ |
| 1816 |
if (joinrel->partbounds_merged) |
| 1817 |
{ |
| 1818 |
get_matching_part_pairs(root, joinrel, rel1, rel2, |
| 1819 |
parts1, parts2); |
| 1820 |
Assert(list_length(*parts1) == joinrel->nparts); |
| 1821 |
Assert(list_length(*parts2) == joinrel->nparts); |
| 1822 |
} |
| 1823 |
} |
| 1824 |
} |
| 1825 |
|
| 1826 |
/* |
| 1827 |
* get_matching_part_pairs |
| 1828 |
* Generate pairs of partitions to be joined from inputs |
| 1829 |
*/ |
| 1830 |
static void |
| 1831 |
get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel, |
| 1832 |
RelOptInfo *rel1, RelOptInfo *rel2, |
| 1833 |
List **parts1, List **parts2) |
| 1834 |
{ |
| 1835 |
bool rel1_is_simple = IS_SIMPLE_REL(rel1); |
| 1836 |
bool rel2_is_simple = IS_SIMPLE_REL(rel2); |
| 1837 |
int cnt_parts; |
| 1838 |
|
| 1839 |
*parts1 = NIL; |
| 1840 |
*parts2 = NIL; |
| 1841 |
|
| 1842 |
for (cnt_parts = 0; cnt_parts < joinrel->nparts; cnt_parts++) |
| 1843 |
{ |
| 1844 |
RelOptInfo *child_joinrel = joinrel->part_rels[cnt_parts]; |
| 1845 |
RelOptInfo *child_rel1; |
| 1846 |
RelOptInfo *child_rel2; |
| 1847 |
Relids child_relids1; |
| 1848 |
Relids child_relids2; |
| 1849 |
|
| 1850 |
/* |
| 1851 |
* If this segment of the join is empty, it means that this segment |
| 1852 |
* was ignored when previously creating child-join paths for it in |
| 1853 |
* try_partitionwise_join() as it would not contribute to the join |
| 1854 |
* result, due to one or both inputs being empty; add NULL to each of |
| 1855 |
* the given lists so that this segment will be ignored again in that |
| 1856 |
* function. |
| 1857 |
*/ |
| 1858 |
if (!child_joinrel) |
| 1859 |
{ |
| 1860 |
*parts1 = lappend(*parts1, NULL); |
| 1861 |
*parts2 = lappend(*parts2, NULL); |
| 1862 |
continue; |
| 1863 |
} |
| 1864 |
|
| 1865 |
/* |
| 1866 |
* Get a relids set of partition(s) involved in this join segment that |
| 1867 |
* are from the rel1 side. |
| 1868 |
*/ |
| 1869 |
child_relids1 = bms_intersect(child_joinrel->relids, |
| 1870 |
rel1->all_partrels); |
| 1871 |
Assert(bms_num_members(child_relids1) == bms_num_members(rel1->relids)); |
| 1872 |
|
| 1873 |
/* |
| 1874 |
* Get a child rel for rel1 with the relids. Note that we should have |
| 1875 |
* the child rel even if rel1 is a join rel, because in that case the |
| 1876 |
* partitions specified in the relids would have matching/overlapping |
| 1877 |
* boundaries, so the specified partitions should be considered as |
| 1878 |
* ones to be joined when planning partitionwise joins of rel1, |
| 1879 |
* meaning that the child rel would have been built by the time we get |
| 1880 |
* here. |
| 1881 |
*/ |
| 1882 |
if (rel1_is_simple) |
| 1883 |
{ |
| 1884 |
int varno = bms_singleton_member(child_relids1); |
| 1885 |
|
| 1886 |
child_rel1 = find_base_rel(root, varno); |
| 1887 |
} |
| 1888 |
else |
| 1889 |
child_rel1 = find_join_rel(root, child_relids1); |
| 1890 |
Assert(child_rel1); |
| 1891 |
|
| 1892 |
/* |
| 1893 |
* Get a relids set of partition(s) involved in this join segment that |
| 1894 |
* are from the rel2 side. |
| 1895 |
*/ |
| 1896 |
child_relids2 = bms_intersect(child_joinrel->relids, |
| 1897 |
rel2->all_partrels); |
| 1898 |
Assert(bms_num_members(child_relids2) == bms_num_members(rel2->relids)); |
| 1899 |
|
| 1900 |
/* |
| 1901 |
* Get a child rel for rel2 with the relids. See above comments. |
| 1902 |
*/ |
| 1903 |
if (rel2_is_simple) |
| 1904 |
{ |
| 1905 |
int varno = bms_singleton_member(child_relids2); |
| 1906 |
|
| 1907 |
child_rel2 = find_base_rel(root, varno); |
| 1908 |
} |
| 1909 |
else |
| 1910 |
child_rel2 = find_join_rel(root, child_relids2); |
| 1911 |
Assert(child_rel2); |
| 1912 |
|
| 1913 |
/* |
| 1914 |
* The join of rel1 and rel2 is legal, so is the join of the child |
| 1915 |
* rels obtained above; add them to the given lists as a join pair |
| 1916 |
* producing this join segment. |
| 1917 |
*/ |
| 1918 |
*parts1 = lappend(*parts1, child_rel1); |
| 1919 |
*parts2 = lappend(*parts2, child_rel2); |
| 1920 |
} |
| 1921 |
} |