| 1 |
/*------------------------------------------------------------------------- |
| 2 |
* |
| 3 |
* joinpath.c |
| 4 |
* Routines to find all possible paths for processing a set of joins |
| 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/joinpath.c |
| 12 |
* |
| 13 |
*------------------------------------------------------------------------- |
| 14 |
*/ |
| 15 |
#include "postgres.h" |
| 16 |
|
| 17 |
#include <math.h> |
| 18 |
|
| 19 |
#include "executor/executor.h" |
| 20 |
#include "foreign/fdwapi.h" |
| 21 |
#include "nodes/nodeFuncs.h" |
| 22 |
#include "optimizer/cost.h" |
| 23 |
#include "optimizer/optimizer.h" |
| 24 |
#include "optimizer/pathnode.h" |
| 25 |
#include "optimizer/paths.h" |
| 26 |
#include "optimizer/placeholder.h" |
| 27 |
#include "optimizer/planmain.h" |
| 28 |
#include "optimizer/restrictinfo.h" |
| 29 |
#include "utils/lsyscache.h" |
| 30 |
#include "utils/typcache.h" |
| 31 |
|
| 32 |
/* Hook for plugins to get control in add_paths_to_joinrel() */ |
| 33 |
set_join_pathlist_hook_type set_join_pathlist_hook = NULL; |
| 34 |
|
| 35 |
/* |
| 36 |
* Paths parameterized by a parent rel can be considered to be parameterized |
| 37 |
* by any of its children, when we are performing partitionwise joins. These |
| 38 |
* macros simplify checking for such cases. Beware multiple eval of args. |
| 39 |
*/ |
| 40 |
#define PATH_PARAM_BY_PARENT(path, rel) \ |
| 41 |
((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), \ |
| 42 |
(rel)->top_parent_relids)) |
| 43 |
#define PATH_PARAM_BY_REL_SELF(path, rel) \ |
| 44 |
((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids)) |
| 45 |
|
| 46 |
#define PATH_PARAM_BY_REL(path, rel) \ |
| 47 |
(PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel)) |
| 48 |
|
| 49 |
static void try_partial_mergejoin_path(PlannerInfo *root, |
| 50 |
RelOptInfo *joinrel, |
| 51 |
Path *outer_path, |
| 52 |
Path *inner_path, |
| 53 |
List *pathkeys, |
| 54 |
List *mergeclauses, |
| 55 |
List *outersortkeys, |
| 56 |
List *innersortkeys, |
| 57 |
JoinType jointype, |
| 58 |
JoinPathExtraData *extra); |
| 59 |
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, |
| 60 |
RelOptInfo *outerrel, RelOptInfo *innerrel, |
| 61 |
JoinType jointype, JoinPathExtraData *extra); |
| 62 |
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, |
| 63 |
RelOptInfo *outerrel, RelOptInfo *innerrel, |
| 64 |
JoinType jointype, JoinPathExtraData *extra); |
| 65 |
static void consider_parallel_nestloop(PlannerInfo *root, |
| 66 |
RelOptInfo *joinrel, |
| 67 |
RelOptInfo *outerrel, |
| 68 |
RelOptInfo *innerrel, |
| 69 |
JoinType jointype, |
| 70 |
JoinPathExtraData *extra); |
| 71 |
static void consider_parallel_mergejoin(PlannerInfo *root, |
| 72 |
RelOptInfo *joinrel, |
| 73 |
RelOptInfo *outerrel, |
| 74 |
RelOptInfo *innerrel, |
| 75 |
JoinType jointype, |
| 76 |
JoinPathExtraData *extra, |
| 77 |
Path *inner_cheapest_total); |
| 78 |
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, |
| 79 |
RelOptInfo *outerrel, RelOptInfo *innerrel, |
| 80 |
JoinType jointype, JoinPathExtraData *extra); |
| 81 |
static List *select_mergejoin_clauses(PlannerInfo *root, |
| 82 |
RelOptInfo *joinrel, |
| 83 |
RelOptInfo *outerrel, |
| 84 |
RelOptInfo *innerrel, |
| 85 |
List *restrictlist, |
| 86 |
JoinType jointype, |
| 87 |
bool *mergejoin_allowed); |
| 88 |
static void generate_mergejoin_paths(PlannerInfo *root, |
| 89 |
RelOptInfo *joinrel, |
| 90 |
RelOptInfo *innerrel, |
| 91 |
Path *outerpath, |
| 92 |
JoinType jointype, |
| 93 |
JoinPathExtraData *extra, |
| 94 |
bool useallclauses, |
| 95 |
Path *inner_cheapest_total, |
| 96 |
List *merge_pathkeys, |
| 97 |
bool is_partial); |
| 98 |
|
| 99 |
|
| 100 |
/* |
| 101 |
* add_paths_to_joinrel |
| 102 |
* Given a join relation and two component rels from which it can be made, |
| 103 |
* consider all possible paths that use the two component rels as outer |
| 104 |
* and inner rel respectively. Add these paths to the join rel's pathlist |
| 105 |
* if they survive comparison with other paths (and remove any existing |
| 106 |
* paths that are dominated by these paths). |
| 107 |
* |
| 108 |
* Modifies the pathlist field of the joinrel node to contain the best |
| 109 |
* paths found so far. |
| 110 |
* |
| 111 |
* jointype is not necessarily the same as sjinfo->jointype; it might be |
| 112 |
* "flipped around" if we are considering joining the rels in the opposite |
| 113 |
* direction from what's indicated in sjinfo. |
| 114 |
* |
| 115 |
* Also, this routine and others in this module accept the special JoinTypes |
| 116 |
* JOIN_UNIQUE_OUTER and JOIN_UNIQUE_INNER to indicate that we should |
| 117 |
* unique-ify the outer or inner relation and then apply a regular inner |
| 118 |
* join. These values are not allowed to propagate outside this module, |
| 119 |
* however. Path cost estimation code may need to recognize that it's |
| 120 |
* dealing with such a case --- the combination of nominal jointype INNER |
| 121 |
* with sjinfo->jointype == JOIN_SEMI indicates that. |
| 122 |
*/ |
| 123 |
void |
| 124 |
add_paths_to_joinrel(PlannerInfo *root, |
| 125 |
RelOptInfo *joinrel, |
| 126 |
RelOptInfo *outerrel, |
| 127 |
RelOptInfo *innerrel, |
| 128 |
JoinType jointype, |
| 129 |
SpecialJoinInfo *sjinfo, |
| 130 |
List *restrictlist) |
| 131 |
{ |
| 132 |
JoinPathExtraData extra; |
| 133 |
bool mergejoin_allowed = true; |
| 134 |
ListCell *lc; |
| 135 |
Relids joinrelids; |
| 136 |
|
| 137 |
/* |
| 138 |
* PlannerInfo doesn't contain the SpecialJoinInfos created for joins |
| 139 |
* between child relations, even if there is a SpecialJoinInfo node for |
| 140 |
* the join between the topmost parents. So, while calculating Relids set |
| 141 |
* representing the restriction, consider relids of topmost parent of |
| 142 |
* partitions. |
| 143 |
*/ |
| 144 |
if (joinrel->reloptkind == RELOPT_OTHER_JOINREL) |
| 145 |
joinrelids = joinrel->top_parent_relids; |
| 146 |
else |
| 147 |
joinrelids = joinrel->relids; |
| 148 |
|
| 149 |
extra.restrictlist = restrictlist; |
| 150 |
extra.mergeclause_list = NIL; |
| 151 |
extra.sjinfo = sjinfo; |
| 152 |
extra.param_source_rels = NULL; |
| 153 |
|
| 154 |
/* |
| 155 |
* See if the inner relation is provably unique for this outer rel. |
| 156 |
* |
| 157 |
* We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't |
| 158 |
* matter since the executor can make the equivalent optimization anyway; |
| 159 |
* we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we |
| 160 |
* must be considering a semijoin whose inner side is not provably unique |
| 161 |
* (else reduce_unique_semijoins would've simplified it), so there's no |
| 162 |
* point in calling innerrel_is_unique. However, if the LHS covers all of |
| 163 |
* the semijoin's min_lefthand, then it's appropriate to set inner_unique |
| 164 |
* because the path produced by create_unique_path will be unique relative |
| 165 |
* to the LHS. (If we have an LHS that's only part of the min_lefthand, |
| 166 |
* that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid |
| 167 |
* letting that value escape this module. |
| 168 |
*/ |
| 169 |
switch (jointype) |
| 170 |
{ |
| 171 |
case JOIN_SEMI: |
| 172 |
case JOIN_ANTI: |
| 173 |
|
| 174 |
/* |
| 175 |
* XXX it may be worth proving this to allow a Memoize to be |
| 176 |
* considered for Nested Loop Semi/Anti Joins. |
| 177 |
*/ |
| 178 |
extra.inner_unique = false; /* well, unproven */ |
| 179 |
break; |
| 180 |
case JOIN_UNIQUE_INNER: |
| 181 |
extra.inner_unique = bms_is_subset(sjinfo->min_lefthand, |
| 182 |
outerrel->relids); |
| 183 |
break; |
| 184 |
case JOIN_UNIQUE_OUTER: |
| 185 |
extra.inner_unique = innerrel_is_unique(root, |
| 186 |
joinrel->relids, |
| 187 |
outerrel->relids, |
| 188 |
innerrel, |
| 189 |
JOIN_INNER, |
| 190 |
restrictlist, |
| 191 |
false); |
| 192 |
break; |
| 193 |
default: |
| 194 |
extra.inner_unique = innerrel_is_unique(root, |
| 195 |
joinrel->relids, |
| 196 |
outerrel->relids, |
| 197 |
innerrel, |
| 198 |
jointype, |
| 199 |
restrictlist, |
| 200 |
false); |
| 201 |
break; |
| 202 |
} |
| 203 |
|
| 204 |
/* |
| 205 |
* Find potential mergejoin clauses. We can skip this if we are not |
| 206 |
* interested in doing a mergejoin. However, mergejoin may be our only |
| 207 |
* way of implementing a full outer join, so override enable_mergejoin if |
| 208 |
* it's a full join. |
| 209 |
*/ |
| 210 |
if (enable_mergejoin || jointype == JOIN_FULL) |
| 211 |
extra.mergeclause_list = select_mergejoin_clauses(root, |
| 212 |
joinrel, |
| 213 |
outerrel, |
| 214 |
innerrel, |
| 215 |
restrictlist, |
| 216 |
jointype, |
| 217 |
&mergejoin_allowed); |
| 218 |
|
| 219 |
/* |
| 220 |
* If it's SEMI, ANTI, or inner_unique join, compute correction factors |
| 221 |
* for cost estimation. These will be the same for all paths. |
| 222 |
*/ |
| 223 |
if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique) |
| 224 |
compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel, |
| 225 |
jointype, sjinfo, restrictlist, |
| 226 |
&extra.semifactors); |
| 227 |
|
| 228 |
/* |
| 229 |
* Decide whether it's sensible to generate parameterized paths for this |
| 230 |
* joinrel, and if so, which relations such paths should require. There |
| 231 |
* is usually no need to create a parameterized result path unless there |
| 232 |
* is a join order restriction that prevents joining one of our input rels |
| 233 |
* directly to the parameter source rel instead of joining to the other |
| 234 |
* input rel. (But see allow_star_schema_join().) This restriction |
| 235 |
* reduces the number of parameterized paths we have to deal with at |
| 236 |
* higher join levels, without compromising the quality of the resulting |
| 237 |
* plan. We express the restriction as a Relids set that must overlap the |
| 238 |
* parameterization of any proposed join path. Note: param_source_rels |
| 239 |
* should contain only baserels, not OJ relids, so starting from |
| 240 |
* all_baserels not all_query_rels is correct. |
| 241 |
*/ |
| 242 |
foreach(lc, root->join_info_list) |
| 243 |
{ |
| 244 |
SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc); |
| 245 |
|
| 246 |
/* |
| 247 |
* SJ is relevant to this join if we have some part of its RHS |
| 248 |
* (possibly not all of it), and haven't yet joined to its LHS. (This |
| 249 |
* test is pretty simplistic, but should be sufficient considering the |
| 250 |
* join has already been proven legal.) If the SJ is relevant, it |
| 251 |
* presents constraints for joining to anything not in its RHS. |
| 252 |
*/ |
| 253 |
if (bms_overlap(joinrelids, sjinfo2->min_righthand) && |
| 254 |
!bms_overlap(joinrelids, sjinfo2->min_lefthand)) |
| 255 |
extra.param_source_rels = bms_join(extra.param_source_rels, |
| 256 |
bms_difference(root->all_baserels, |
| 257 |
sjinfo2->min_righthand)); |
| 258 |
|
| 259 |
/* full joins constrain both sides symmetrically */ |
| 260 |
if (sjinfo2->jointype == JOIN_FULL && |
| 261 |
bms_overlap(joinrelids, sjinfo2->min_lefthand) && |
| 262 |
!bms_overlap(joinrelids, sjinfo2->min_righthand)) |
| 263 |
extra.param_source_rels = bms_join(extra.param_source_rels, |
| 264 |
bms_difference(root->all_baserels, |
| 265 |
sjinfo2->min_lefthand)); |
| 266 |
} |
| 267 |
|
| 268 |
/* |
| 269 |
* However, when a LATERAL subquery is involved, there will simply not be |
| 270 |
* any paths for the joinrel that aren't parameterized by whatever the |
| 271 |
* subquery is parameterized by, unless its parameterization is resolved |
| 272 |
* within the joinrel. So we might as well allow additional dependencies |
| 273 |
* on whatever residual lateral dependencies the joinrel will have. |
| 274 |
*/ |
| 275 |
extra.param_source_rels = bms_add_members(extra.param_source_rels, |
| 276 |
joinrel->lateral_relids); |
| 277 |
|
| 278 |
/* |
| 279 |
* 1. Consider mergejoin paths where both relations must be explicitly |
| 280 |
* sorted. Skip this if we can't mergejoin. |
| 281 |
*/ |
| 282 |
if (mergejoin_allowed) |
| 283 |
sort_inner_and_outer(root, joinrel, outerrel, innerrel, |
| 284 |
jointype, &extra); |
| 285 |
|
| 286 |
/* |
| 287 |
* 2. Consider paths where the outer relation need not be explicitly |
| 288 |
* sorted. This includes both nestloops and mergejoins where the outer |
| 289 |
* path is already ordered. Again, skip this if we can't mergejoin. |
| 290 |
* (That's okay because we know that nestloop can't handle |
| 291 |
* right/right-anti/right-semi/full joins at all, so it wouldn't work in |
| 292 |
* the prohibited cases either.) |
| 293 |
*/ |
| 294 |
if (mergejoin_allowed) |
| 295 |
match_unsorted_outer(root, joinrel, outerrel, innerrel, |
| 296 |
jointype, &extra); |
| 297 |
|
| 298 |
#ifdef NOT_USED |
| 299 |
|
| 300 |
/* |
| 301 |
* 3. Consider paths where the inner relation need not be explicitly |
| 302 |
* sorted. This includes mergejoins only (nestloops were already built in |
| 303 |
* match_unsorted_outer). |
| 304 |
* |
| 305 |
* Diked out as redundant 2/13/2000 -- tgl. There isn't any really |
| 306 |
* significant difference between the inner and outer side of a mergejoin, |
| 307 |
* so match_unsorted_inner creates no paths that aren't equivalent to |
| 308 |
* those made by match_unsorted_outer when add_paths_to_joinrel() is |
| 309 |
* invoked with the two rels given in the other order. |
| 310 |
*/ |
| 311 |
if (mergejoin_allowed) |
| 312 |
match_unsorted_inner(root, joinrel, outerrel, innerrel, |
| 313 |
jointype, &extra); |
| 314 |
#endif |
| 315 |
|
| 316 |
/* |
| 317 |
* 4. Consider paths where both outer and inner relations must be hashed |
| 318 |
* before being joined. As above, disregard enable_hashjoin for full |
| 319 |
* joins, because there may be no other alternative. |
| 320 |
*/ |
| 321 |
if (enable_hashjoin || jointype == JOIN_FULL) |
| 322 |
hash_inner_and_outer(root, joinrel, outerrel, innerrel, |
| 323 |
jointype, &extra); |
| 324 |
|
| 325 |
/* |
| 326 |
* 5. If inner and outer relations are foreign tables (or joins) belonging |
| 327 |
* to the same server and assigned to the same user to check access |
| 328 |
* permissions as, give the FDW a chance to push down joins. |
| 329 |
*/ |
| 330 |
if (joinrel->fdwroutine && |
| 331 |
joinrel->fdwroutine->GetForeignJoinPaths) |
| 332 |
joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel, |
| 333 |
outerrel, innerrel, |
| 334 |
jointype, &extra); |
| 335 |
|
| 336 |
/* |
| 337 |
* 6. Finally, give extensions a chance to manipulate the path list. They |
| 338 |
* could add new paths (such as CustomPaths) by calling add_path(), or |
| 339 |
* add_partial_path() if parallel aware. They could also delete or modify |
| 340 |
* paths added by the core code. |
| 341 |
*/ |
| 342 |
if (set_join_pathlist_hook) |
| 343 |
set_join_pathlist_hook(root, joinrel, outerrel, innerrel, |
| 344 |
jointype, &extra); |
| 345 |
} |
| 346 |
|
| 347 |
/* |
| 348 |
* We override the param_source_rels heuristic to accept nestloop paths in |
| 349 |
* which the outer rel satisfies some but not all of the inner path's |
| 350 |
* parameterization. This is necessary to get good plans for star-schema |
| 351 |
* scenarios, in which a parameterized path for a large table may require |
| 352 |
* parameters from multiple small tables that will not get joined directly to |
| 353 |
* each other. We can handle that by stacking nestloops that have the small |
| 354 |
* tables on the outside; but this breaks the rule the param_source_rels |
| 355 |
* heuristic is based on, namely that parameters should not be passed down |
| 356 |
* across joins unless there's a join-order-constraint-based reason to do so. |
| 357 |
* So we ignore the param_source_rels restriction when this case applies. |
| 358 |
* |
| 359 |
* allow_star_schema_join() returns true if the param_source_rels restriction |
| 360 |
* should be overridden, ie, it's okay to perform this join. |
| 361 |
*/ |
| 362 |
static inline bool |
| 363 |
allow_star_schema_join(PlannerInfo *root, |
| 364 |
Relids outerrelids, |
| 365 |
Relids inner_paramrels) |
| 366 |
{ |
| 367 |
/* |
| 368 |
* It's a star-schema case if the outer rel provides some but not all of |
| 369 |
* the inner rel's parameterization. |
| 370 |
*/ |
| 371 |
return (bms_overlap(inner_paramrels, outerrelids) && |
| 372 |
bms_nonempty_difference(inner_paramrels, outerrelids)); |
| 373 |
} |
| 374 |
|
| 375 |
/* |
| 376 |
* If the parameterization is only partly satisfied by the outer rel, |
| 377 |
* the unsatisfied part can't include any outer-join relids that could |
| 378 |
* null rels of the satisfied part. That would imply that we're trying |
| 379 |
* to use a clause involving a Var with nonempty varnullingrels at |
| 380 |
* a join level where that value isn't yet computable. |
| 381 |
* |
| 382 |
* In practice, this test never finds a problem because earlier join order |
| 383 |
* restrictions prevent us from attempting a join that would cause a problem. |
| 384 |
* (That's unsurprising, because the code worked before we ever added |
| 385 |
* outer-join relids to expression relids.) It still seems worth checking |
| 386 |
* as a backstop, but we only do so in assert-enabled builds. |
| 387 |
*/ |
| 388 |
#ifdef USE_ASSERT_CHECKING |
| 389 |
static inline bool |
| 390 |
have_unsafe_outer_join_ref(PlannerInfo *root, |
| 391 |
Relids outerrelids, |
| 392 |
Relids inner_paramrels) |
| 393 |
{ |
| 394 |
bool result = false; |
| 395 |
Relids unsatisfied = bms_difference(inner_paramrels, outerrelids); |
| 396 |
Relids satisfied = bms_intersect(inner_paramrels, outerrelids); |
| 397 |
|
| 398 |
if (bms_overlap(unsatisfied, root->outer_join_rels)) |
| 399 |
{ |
| 400 |
ListCell *lc; |
| 401 |
|
| 402 |
foreach(lc, root->join_info_list) |
| 403 |
{ |
| 404 |
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); |
| 405 |
|
| 406 |
if (!bms_is_member(sjinfo->ojrelid, unsatisfied)) |
| 407 |
continue; /* not relevant */ |
| 408 |
if (bms_overlap(satisfied, sjinfo->min_righthand) || |
| 409 |
(sjinfo->jointype == JOIN_FULL && |
| 410 |
bms_overlap(satisfied, sjinfo->min_lefthand))) |
| 411 |
{ |
| 412 |
result = true; /* doesn't work */ |
| 413 |
break; |
| 414 |
} |
| 415 |
} |
| 416 |
} |
| 417 |
|
| 418 |
/* Waste no memory when we reject a path here */ |
| 419 |
bms_free(unsatisfied); |
| 420 |
bms_free(satisfied); |
| 421 |
|
| 422 |
return result; |
| 423 |
} |
| 424 |
#endif /* USE_ASSERT_CHECKING */ |
| 425 |
|
| 426 |
/* |
| 427 |
* paraminfo_get_equal_hashops |
| 428 |
* Determine if the clauses in param_info and innerrel's lateral vars |
| 429 |
* can be hashed. |
| 430 |
* Returns true if hashing is possible, otherwise false. |
| 431 |
* |
| 432 |
* Additionally, on success we collect the outer expressions and the |
| 433 |
* appropriate equality operators for each hashable parameter to innerrel. |
| 434 |
* These are returned in parallel lists in *param_exprs and *operators. |
| 435 |
* We also set *binary_mode to indicate whether strict binary matching is |
| 436 |
* required. |
| 437 |
*/ |
| 438 |
static bool |
| 439 |
paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, |
| 440 |
RelOptInfo *outerrel, RelOptInfo *innerrel, |
| 441 |
List *ph_lateral_vars, List **param_exprs, |
| 442 |
List **operators, bool *binary_mode) |
| 443 |
|
| 444 |
{ |
| 445 |
List *lateral_vars; |
| 446 |
ListCell *lc; |
| 447 |
|
| 448 |
*param_exprs = NIL; |
| 449 |
*operators = NIL; |
| 450 |
*binary_mode = false; |
| 451 |
|
| 452 |
/* Add join clauses from param_info to the hash key */ |
| 453 |
if (param_info != NULL) |
| 454 |
{ |
| 455 |
List *clauses = param_info->ppi_clauses; |
| 456 |
|
| 457 |
foreach(lc, clauses) |
| 458 |
{ |
| 459 |
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); |
| 460 |
OpExpr *opexpr; |
| 461 |
Node *expr; |
| 462 |
Oid hasheqoperator; |
| 463 |
|
| 464 |
opexpr = (OpExpr *) rinfo->clause; |
| 465 |
|
| 466 |
/* |
| 467 |
* Bail if the rinfo is not compatible. We need a join OpExpr |
| 468 |
* with 2 args. |
| 469 |
*/ |
| 470 |
if (!IsA(opexpr, OpExpr) || list_length(opexpr->args) != 2 || |
| 471 |
!clause_sides_match_join(rinfo, outerrel->relids, |
| 472 |
innerrel->relids)) |
| 473 |
{ |
| 474 |
list_free(*operators); |
| 475 |
list_free(*param_exprs); |
| 476 |
return false; |
| 477 |
} |
| 478 |
|
| 479 |
if (rinfo->outer_is_left) |
| 480 |
{ |
| 481 |
expr = (Node *) linitial(opexpr->args); |
| 482 |
hasheqoperator = rinfo->left_hasheqoperator; |
| 483 |
} |
| 484 |
else |
| 485 |
{ |
| 486 |
expr = (Node *) lsecond(opexpr->args); |
| 487 |
hasheqoperator = rinfo->right_hasheqoperator; |
| 488 |
} |
| 489 |
|
| 490 |
/* can't do memoize if we can't hash the outer type */ |
| 491 |
if (!OidIsValid(hasheqoperator)) |
| 492 |
{ |
| 493 |
list_free(*operators); |
| 494 |
list_free(*param_exprs); |
| 495 |
return false; |
| 496 |
} |
| 497 |
|
| 498 |
/* |
| 499 |
* 'expr' may already exist as a parameter from a previous item in |
| 500 |
* ppi_clauses. No need to include it again, however we'd better |
| 501 |
* ensure we do switch into binary mode if required. See below. |
| 502 |
*/ |
| 503 |
if (!list_member(*param_exprs, expr)) |
| 504 |
{ |
| 505 |
*operators = lappend_oid(*operators, hasheqoperator); |
| 506 |
*param_exprs = lappend(*param_exprs, expr); |
| 507 |
} |
| 508 |
|
| 509 |
/* |
| 510 |
* When the join operator is not hashable then it's possible that |
| 511 |
* the operator will be able to distinguish something that the |
| 512 |
* hash equality operator could not. For example with floating |
| 513 |
* point types -0.0 and +0.0 are classed as equal by the hash |
| 514 |
* function and equality function, but some other operator may be |
| 515 |
* able to tell those values apart. This means that we must put |
| 516 |
* memoize into binary comparison mode so that it does bit-by-bit |
| 517 |
* comparisons rather than a "logical" comparison as it would |
| 518 |
* using the hash equality operator. |
| 519 |
*/ |
| 520 |
if (!OidIsValid(rinfo->hashjoinoperator)) |
| 521 |
*binary_mode = true; |
| 522 |
} |
| 523 |
} |
| 524 |
|
| 525 |
/* Now add any lateral vars to the cache key too */ |
| 526 |
lateral_vars = list_concat(ph_lateral_vars, innerrel->lateral_vars); |
| 527 |
foreach(lc, lateral_vars) |
| 528 |
{ |
| 529 |
Node *expr = (Node *) lfirst(lc); |
| 530 |
TypeCacheEntry *typentry; |
| 531 |
|
| 532 |
/* Reject if there are any volatile functions in lateral vars */ |
| 533 |
if (contain_volatile_functions(expr)) |
| 534 |
{ |
| 535 |
list_free(*operators); |
| 536 |
list_free(*param_exprs); |
| 537 |
return false; |
| 538 |
} |
| 539 |
|
| 540 |
typentry = lookup_type_cache(exprType(expr), |
| 541 |
TYPECACHE_HASH_PROC | TYPECACHE_EQ_OPR); |
| 542 |
|
| 543 |
/* can't use memoize without a valid hash proc and equals operator */ |
| 544 |
if (!OidIsValid(typentry->hash_proc) || !OidIsValid(typentry->eq_opr)) |
| 545 |
{ |
| 546 |
list_free(*operators); |
| 547 |
list_free(*param_exprs); |
| 548 |
return false; |
| 549 |
} |
| 550 |
|
| 551 |
/* |
| 552 |
* 'expr' may already exist as a parameter from the ppi_clauses. No |
| 553 |
* need to include it again, however we'd better ensure we do switch |
| 554 |
* into binary mode. |
| 555 |
*/ |
| 556 |
if (!list_member(*param_exprs, expr)) |
| 557 |
{ |
| 558 |
*operators = lappend_oid(*operators, typentry->eq_opr); |
| 559 |
*param_exprs = lappend(*param_exprs, expr); |
| 560 |
} |
| 561 |
|
| 562 |
/* |
| 563 |
* We must go into binary mode as we don't have too much of an idea of |
| 564 |
* how these lateral Vars are being used. See comment above when we |
| 565 |
* set *binary_mode for the non-lateral Var case. This could be |
| 566 |
* relaxed a bit if we had the RestrictInfos and knew the operators |
| 567 |
* being used, however for cases like Vars that are arguments to |
| 568 |
* functions we must operate in binary mode as we don't have |
| 569 |
* visibility into what the function is doing with the Vars. |
| 570 |
*/ |
| 571 |
*binary_mode = true; |
| 572 |
} |
| 573 |
|
| 574 |
/* We're okay to use memoize */ |
| 575 |
return true; |
| 576 |
} |
| 577 |
|
| 578 |
/* |
| 579 |
* extract_lateral_vars_from_PHVs |
| 580 |
* Extract lateral references within PlaceHolderVars that are due to be |
| 581 |
* evaluated at 'innerrelids'. |
| 582 |
*/ |
| 583 |
static List * |
| 584 |
extract_lateral_vars_from_PHVs(PlannerInfo *root, Relids innerrelids) |
| 585 |
{ |
| 586 |
List *ph_lateral_vars = NIL; |
| 587 |
ListCell *lc; |
| 588 |
|
| 589 |
/* Nothing would be found if the query contains no LATERAL RTEs */ |
| 590 |
if (!root->hasLateralRTEs) |
| 591 |
return NIL; |
| 592 |
|
| 593 |
/* |
| 594 |
* No need to consider PHVs that are due to be evaluated at joinrels, |
| 595 |
* since we do not add Memoize nodes on top of joinrel paths. |
| 596 |
*/ |
| 597 |
if (bms_membership(innerrelids) == BMS_MULTIPLE) |
| 598 |
return NIL; |
| 599 |
|
| 600 |
foreach(lc, root->placeholder_list) |
| 601 |
{ |
| 602 |
PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc); |
| 603 |
List *vars; |
| 604 |
ListCell *cell; |
| 605 |
|
| 606 |
/* PHV is uninteresting if no lateral refs */ |
| 607 |
if (phinfo->ph_lateral == NULL) |
| 608 |
continue; |
| 609 |
|
| 610 |
/* PHV is uninteresting if not due to be evaluated at innerrelids */ |
| 611 |
if (!bms_equal(phinfo->ph_eval_at, innerrelids)) |
| 612 |
continue; |
| 613 |
|
| 614 |
/* |
| 615 |
* If the PHV does not reference any rels in innerrelids, use its |
| 616 |
* contained expression as a cache key rather than extracting the |
| 617 |
* Vars/PHVs from it and using those. This can be beneficial in cases |
| 618 |
* where the expression results in fewer distinct values to cache |
| 619 |
* tuples for. |
| 620 |
*/ |
| 621 |
if (!bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr), |
| 622 |
innerrelids)) |
| 623 |
{ |
| 624 |
ph_lateral_vars = lappend(ph_lateral_vars, phinfo->ph_var->phexpr); |
| 625 |
continue; |
| 626 |
} |
| 627 |
|
| 628 |
/* Fetch Vars and PHVs of lateral references within PlaceHolderVars */ |
| 629 |
vars = pull_vars_of_level((Node *) phinfo->ph_var->phexpr, 0); |
| 630 |
foreach(cell, vars) |
| 631 |
{ |
| 632 |
Node *node = (Node *) lfirst(cell); |
| 633 |
|
| 634 |
if (IsA(node, Var)) |
| 635 |
{ |
| 636 |
Var *var = (Var *) node; |
| 637 |
|
| 638 |
Assert(var->varlevelsup == 0); |
| 639 |
|
| 640 |
if (bms_is_member(var->varno, phinfo->ph_lateral)) |
| 641 |
ph_lateral_vars = lappend(ph_lateral_vars, node); |
| 642 |
} |
| 643 |
else if (IsA(node, PlaceHolderVar)) |
| 644 |
{ |
| 645 |
PlaceHolderVar *phv = (PlaceHolderVar *) node; |
| 646 |
|
| 647 |
Assert(phv->phlevelsup == 0); |
| 648 |
|
| 649 |
if (bms_is_subset(find_placeholder_info(root, phv)->ph_eval_at, |
| 650 |
phinfo->ph_lateral)) |
| 651 |
ph_lateral_vars = lappend(ph_lateral_vars, node); |
| 652 |
} |
| 653 |
else |
| 654 |
Assert(false); |
| 655 |
} |
| 656 |
|
| 657 |
list_free(vars); |
| 658 |
} |
| 659 |
|
| 660 |
return ph_lateral_vars; |
| 661 |
} |
| 662 |
|
| 663 |
/* |
| 664 |
* get_memoize_path |
| 665 |
* If possible, make and return a Memoize path atop of 'inner_path'. |
| 666 |
* Otherwise return NULL. |
| 667 |
* |
| 668 |
* Note that currently we do not add Memoize nodes on top of join relation |
| 669 |
* paths. This is because the ParamPathInfos for join relation paths do not |
| 670 |
* maintain ppi_clauses, as the set of relevant clauses varies depending on how |
| 671 |
* the join is formed. In addition, joinrels do not maintain lateral_vars. So |
| 672 |
* we do not have a way to extract cache keys from joinrels. |
| 673 |
*/ |
| 674 |
static Path * |
| 675 |
get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, |
| 676 |
RelOptInfo *outerrel, Path *inner_path, |
| 677 |
Path *outer_path, JoinType jointype, |
| 678 |
JoinPathExtraData *extra) |
| 679 |
{ |
| 680 |
List *param_exprs; |
| 681 |
List *hash_operators; |
| 682 |
ListCell *lc; |
| 683 |
bool binary_mode; |
| 684 |
List *ph_lateral_vars; |
| 685 |
|
| 686 |
/* Obviously not if it's disabled */ |
| 687 |
if (!enable_memoize) |
| 688 |
return NULL; |
| 689 |
|
| 690 |
/* |
| 691 |
* We can safely not bother with all this unless we expect to perform more |
| 692 |
* than one inner scan. The first scan is always going to be a cache |
| 693 |
* miss. This would likely fail later anyway based on costs, so this is |
| 694 |
* really just to save some wasted effort. |
| 695 |
*/ |
| 696 |
if (outer_path->parent->rows < 2) |
| 697 |
return NULL; |
| 698 |
|
| 699 |
/* |
| 700 |
* Extract lateral Vars/PHVs within PlaceHolderVars that are due to be |
| 701 |
* evaluated at innerrel. These lateral Vars/PHVs could be used as |
| 702 |
* memoize cache keys. |
| 703 |
*/ |
| 704 |
ph_lateral_vars = extract_lateral_vars_from_PHVs(root, innerrel->relids); |
| 705 |
|
| 706 |
/* |
| 707 |
* We can only have a memoize node when there's some kind of cache key, |
| 708 |
* either parameterized path clauses or lateral Vars. No cache key sounds |
| 709 |
* more like something a Materialize node might be more useful for. |
| 710 |
*/ |
| 711 |
if ((inner_path->param_info == NULL || |
| 712 |
inner_path->param_info->ppi_clauses == NIL) && |
| 713 |
innerrel->lateral_vars == NIL && |
| 714 |
ph_lateral_vars == NIL) |
| 715 |
return NULL; |
| 716 |
|
| 717 |
/* |
| 718 |
* Currently we don't do this for SEMI and ANTI joins unless they're |
| 719 |
* marked as inner_unique. This is because nested loop SEMI/ANTI joins |
| 720 |
* don't scan the inner node to completion, which will mean memoize cannot |
| 721 |
* mark the cache entry as complete. |
| 722 |
* |
| 723 |
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique |
| 724 |
* = true. Should we? See add_paths_to_joinrel() |
| 725 |
*/ |
| 726 |
if (!extra->inner_unique && (jointype == JOIN_SEMI || |
| 727 |
jointype == JOIN_ANTI)) |
| 728 |
return NULL; |
| 729 |
|
| 730 |
/* |
| 731 |
* Memoize normally marks cache entries as complete when it runs out of |
| 732 |
* tuples to read from its subplan. However, with unique joins, Nested |
| 733 |
* Loop will skip to the next outer tuple after finding the first matching |
| 734 |
* inner tuple. This means that we may not read the inner side of the |
| 735 |
* join to completion which leaves no opportunity to mark the cache entry |
| 736 |
* as complete. To work around that, when the join is unique we |
| 737 |
* automatically mark cache entries as complete after fetching the first |
| 738 |
* tuple. This works when the entire join condition is parameterized. |
| 739 |
* Otherwise, when the parameterization is only a subset of the join |
| 740 |
* condition, we can't be sure which part of it causes the join to be |
| 741 |
* unique. This means there are no guarantees that only 1 tuple will be |
| 742 |
* read. We cannot mark the cache entry as complete after reading the |
| 743 |
* first tuple without that guarantee. This means the scope of Memoize |
| 744 |
* node's usefulness is limited to only outer rows that have no join |
| 745 |
* partner as this is the only case where Nested Loop would exhaust the |
| 746 |
* inner scan of a unique join. Since the scope is limited to that, we |
| 747 |
* just don't bother making a memoize path in this case. |
| 748 |
* |
| 749 |
* Lateral vars needn't be considered here as they're not considered when |
| 750 |
* determining if the join is unique. |
| 751 |
*/ |
| 752 |
if (extra->inner_unique) |
| 753 |
{ |
| 754 |
Bitmapset *ppi_serials; |
| 755 |
|
| 756 |
if (inner_path->param_info == NULL) |
| 757 |
return NULL; |
| 758 |
|
| 759 |
ppi_serials = inner_path->param_info->ppi_serials; |
| 760 |
|
| 761 |
foreach_node(RestrictInfo, rinfo, extra->restrictlist) |
| 762 |
{ |
| 763 |
if (!bms_is_member(rinfo->rinfo_serial, ppi_serials)) |
| 764 |
return NULL; |
| 765 |
} |
| 766 |
} |
| 767 |
|
| 768 |
/* |
| 769 |
* We can't use a memoize node if there are volatile functions in the |
| 770 |
* inner rel's target list or restrict list. A cache hit could reduce the |
| 771 |
* number of calls to these functions. |
| 772 |
*/ |
| 773 |
if (contain_volatile_functions((Node *) innerrel->reltarget)) |
| 774 |
return NULL; |
| 775 |
|
| 776 |
foreach(lc, innerrel->baserestrictinfo) |
| 777 |
{ |
| 778 |
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); |
| 779 |
|
| 780 |
if (contain_volatile_functions((Node *) rinfo)) |
| 781 |
return NULL; |
| 782 |
} |
| 783 |
|
| 784 |
/* |
| 785 |
* Also check the parameterized path restrictinfos for volatile functions. |
| 786 |
* Indexed functions must be immutable so shouldn't have any volatile |
| 787 |
* functions, however, with a lateral join the inner scan may not be an |
| 788 |
* index scan. |
| 789 |
*/ |
| 790 |
if (inner_path->param_info != NULL) |
| 791 |
{ |
| 792 |
foreach(lc, inner_path->param_info->ppi_clauses) |
| 793 |
{ |
| 794 |
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); |
| 795 |
|
| 796 |
if (contain_volatile_functions((Node *) rinfo)) |
| 797 |
return NULL; |
| 798 |
} |
| 799 |
} |
| 800 |
|
| 801 |
/* Check if we have hash ops for each parameter to the path */ |
| 802 |
if (paraminfo_get_equal_hashops(root, |
| 803 |
inner_path->param_info, |
| 804 |
outerrel->top_parent ? |
| 805 |
outerrel->top_parent : outerrel, |
| 806 |
innerrel, |
| 807 |
ph_lateral_vars, |
| 808 |
¶m_exprs, |
| 809 |
&hash_operators, |
| 810 |
&binary_mode)) |
| 811 |
{ |
| 812 |
return (Path *) create_memoize_path(root, |
| 813 |
innerrel, |
| 814 |
inner_path, |
| 815 |
param_exprs, |
| 816 |
hash_operators, |
| 817 |
extra->inner_unique, |
| 818 |
binary_mode, |
| 819 |
outer_path->rows); |
| 820 |
} |
| 821 |
|
| 822 |
return NULL; |
| 823 |
} |
| 824 |
|
| 825 |
/* |
| 826 |
* try_nestloop_path |
| 827 |
* Consider a nestloop join path; if it appears useful, push it into |
| 828 |
* the joinrel's pathlist via add_path(). |
| 829 |
*/ |
| 830 |
static void |
| 831 |
try_nestloop_path(PlannerInfo *root, |
| 832 |
RelOptInfo *joinrel, |
| 833 |
Path *outer_path, |
| 834 |
Path *inner_path, |
| 835 |
List *pathkeys, |
| 836 |
JoinType jointype, |
| 837 |
JoinPathExtraData *extra) |
| 838 |
{ |
| 839 |
Relids required_outer; |
| 840 |
JoinCostWorkspace workspace; |
| 841 |
RelOptInfo *innerrel = inner_path->parent; |
| 842 |
RelOptInfo *outerrel = outer_path->parent; |
| 843 |
Relids innerrelids; |
| 844 |
Relids outerrelids; |
| 845 |
Relids inner_paramrels = PATH_REQ_OUTER(inner_path); |
| 846 |
Relids outer_paramrels = PATH_REQ_OUTER(outer_path); |
| 847 |
|
| 848 |
/* |
| 849 |
* If we are forming an outer join at this join, it's nonsensical to use |
| 850 |
* an input path that uses the outer join as part of its parameterization. |
| 851 |
* (This can happen despite our join order restrictions, since those apply |
| 852 |
* to what is in an input relation not what its parameters are.) |
| 853 |
*/ |
| 854 |
if (extra->sjinfo->ojrelid != 0 && |
| 855 |
(bms_is_member(extra->sjinfo->ojrelid, inner_paramrels) || |
| 856 |
bms_is_member(extra->sjinfo->ojrelid, outer_paramrels))) |
| 857 |
return; |
| 858 |
|
| 859 |
/* |
| 860 |
* Any parameterization of the input paths refers to topmost parents of |
| 861 |
* the relevant relations, because reparameterize_path_by_child() hasn't |
| 862 |
* been called yet. So we must consider topmost parents of the relations |
| 863 |
* being joined, too, while determining parameterization of the result and |
| 864 |
* checking for disallowed parameterization cases. |
| 865 |
*/ |
| 866 |
if (innerrel->top_parent_relids) |
| 867 |
innerrelids = innerrel->top_parent_relids; |
| 868 |
else |
| 869 |
innerrelids = innerrel->relids; |
| 870 |
|
| 871 |
if (outerrel->top_parent_relids) |
| 872 |
outerrelids = outerrel->top_parent_relids; |
| 873 |
else |
| 874 |
outerrelids = outerrel->relids; |
| 875 |
|
| 876 |
/* |
| 877 |
* Check to see if proposed path is still parameterized, and reject if the |
| 878 |
* parameterization wouldn't be sensible --- unless allow_star_schema_join |
| 879 |
* says to allow it anyway. |
| 880 |
*/ |
| 881 |
required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels, |
| 882 |
innerrelids, inner_paramrels); |
| 883 |
if (required_outer && |
| 884 |
!bms_overlap(required_outer, extra->param_source_rels) && |
| 885 |
!allow_star_schema_join(root, outerrelids, inner_paramrels)) |
| 886 |
{ |
| 887 |
/* Waste no memory when we reject a path here */ |
| 888 |
bms_free(required_outer); |
| 889 |
return; |
| 890 |
} |
| 891 |
|
| 892 |
/* If we got past that, we shouldn't have any unsafe outer-join refs */ |
| 893 |
Assert(!have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels)); |
| 894 |
|
| 895 |
/* |
| 896 |
* If the inner path is parameterized, it is parameterized by the topmost |
| 897 |
* parent of the outer rel, not the outer rel itself. We will need to |
| 898 |
* translate the parameterization, if this path is chosen, during |
| 899 |
* create_plan(). Here we just check whether we will be able to perform |
| 900 |
* the translation, and if not avoid creating a nestloop path. |
| 901 |
*/ |
| 902 |
if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) && |
| 903 |
!path_is_reparameterizable_by_child(inner_path, outer_path->parent)) |
| 904 |
{ |
| 905 |
bms_free(required_outer); |
| 906 |
return; |
| 907 |
} |
| 908 |
|
| 909 |
/* |
| 910 |
* Do a precheck to quickly eliminate obviously-inferior paths. We |
| 911 |
* calculate a cheap lower bound on the path's cost and then use |
| 912 |
* add_path_precheck() to see if the path is clearly going to be dominated |
| 913 |
* by some existing path for the joinrel. If not, do the full pushup with |
| 914 |
* creating a fully valid path structure and submitting it to add_path(). |
| 915 |
* The latter two steps are expensive enough to make this two-phase |
| 916 |
* methodology worthwhile. |
| 917 |
*/ |
| 918 |
initial_cost_nestloop(root, &workspace, jointype, |
| 919 |
outer_path, inner_path, extra); |
| 920 |
|
| 921 |
if (add_path_precheck(joinrel, workspace.disabled_nodes, |
| 922 |
workspace.startup_cost, workspace.total_cost, |
| 923 |
pathkeys, required_outer)) |
| 924 |
{ |
| 925 |
add_path(joinrel, (Path *) |
| 926 |
create_nestloop_path(root, |
| 927 |
joinrel, |
| 928 |
jointype, |
| 929 |
&workspace, |
| 930 |
extra, |
| 931 |
outer_path, |
| 932 |
inner_path, |
| 933 |
extra->restrictlist, |
| 934 |
pathkeys, |
| 935 |
required_outer)); |
| 936 |
} |
| 937 |
else |
| 938 |
{ |
| 939 |
/* Waste no memory when we reject a path here */ |
| 940 |
bms_free(required_outer); |
| 941 |
} |
| 942 |
} |
| 943 |
|
| 944 |
/* |
| 945 |
* try_partial_nestloop_path |
| 946 |
* Consider a partial nestloop join path; if it appears useful, push it into |
| 947 |
* the joinrel's partial_pathlist via add_partial_path(). |
| 948 |
*/ |
| 949 |
static void |
| 950 |
try_partial_nestloop_path(PlannerInfo *root, |
| 951 |
RelOptInfo *joinrel, |
| 952 |
Path *outer_path, |
| 953 |
Path *inner_path, |
| 954 |
List *pathkeys, |
| 955 |
JoinType jointype, |
| 956 |
JoinPathExtraData *extra) |
| 957 |
{ |
| 958 |
JoinCostWorkspace workspace; |
| 959 |
|
| 960 |
/* |
| 961 |
* If the inner path is parameterized, the parameterization must be fully |
| 962 |
* satisfied by the proposed outer path. Parameterized partial paths are |
| 963 |
* not supported. The caller should already have verified that no lateral |
| 964 |
* rels are required here. |
| 965 |
*/ |
| 966 |
Assert(bms_is_empty(joinrel->lateral_relids)); |
| 967 |
Assert(bms_is_empty(PATH_REQ_OUTER(outer_path))); |
| 968 |
if (inner_path->param_info != NULL) |
| 969 |
{ |
| 970 |
Relids inner_paramrels = inner_path->param_info->ppi_req_outer; |
| 971 |
RelOptInfo *outerrel = outer_path->parent; |
| 972 |
Relids outerrelids; |
| 973 |
|
| 974 |
/* |
| 975 |
* The inner and outer paths are parameterized, if at all, by the top |
| 976 |
* level parents, not the child relations, so we must use those relids |
| 977 |
* for our parameterization tests. |
| 978 |
*/ |
| 979 |
if (outerrel->top_parent_relids) |
| 980 |
outerrelids = outerrel->top_parent_relids; |
| 981 |
else |
| 982 |
outerrelids = outerrel->relids; |
| 983 |
|
| 984 |
if (!bms_is_subset(inner_paramrels, outerrelids)) |
| 985 |
return; |
| 986 |
} |
| 987 |
|
| 988 |
/* |
| 989 |
* If the inner path is parameterized, it is parameterized by the topmost |
| 990 |
* parent of the outer rel, not the outer rel itself. We will need to |
| 991 |
* translate the parameterization, if this path is chosen, during |
| 992 |
* create_plan(). Here we just check whether we will be able to perform |
| 993 |
* the translation, and if not avoid creating a nestloop path. |
| 994 |
*/ |
| 995 |
if (PATH_PARAM_BY_PARENT(inner_path, outer_path->parent) && |
| 996 |
!path_is_reparameterizable_by_child(inner_path, outer_path->parent)) |
| 997 |
return; |
| 998 |
|
| 999 |
/* |
| 1000 |
* Before creating a path, get a quick lower bound on what it is likely to |
| 1001 |
* cost. Bail out right away if it looks terrible. |
| 1002 |
*/ |
| 1003 |
initial_cost_nestloop(root, &workspace, jointype, |
| 1004 |
outer_path, inner_path, extra); |
| 1005 |
if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes, |
| 1006 |
workspace.total_cost, pathkeys)) |
| 1007 |
return; |
| 1008 |
|
| 1009 |
/* Might be good enough to be worth trying, so let's try it. */ |
| 1010 |
add_partial_path(joinrel, (Path *) |
| 1011 |
create_nestloop_path(root, |
| 1012 |
joinrel, |
| 1013 |
jointype, |
| 1014 |
&workspace, |
| 1015 |
extra, |
| 1016 |
outer_path, |
| 1017 |
inner_path, |
| 1018 |
extra->restrictlist, |
| 1019 |
pathkeys, |
| 1020 |
NULL)); |
| 1021 |
} |
| 1022 |
|
| 1023 |
/* |
| 1024 |
* try_mergejoin_path |
| 1025 |
* Consider a merge join path; if it appears useful, push it into |
| 1026 |
* the joinrel's pathlist via add_path(). |
| 1027 |
*/ |
| 1028 |
static void |
| 1029 |
try_mergejoin_path(PlannerInfo *root, |
| 1030 |
RelOptInfo *joinrel, |
| 1031 |
Path *outer_path, |
| 1032 |
Path *inner_path, |
| 1033 |
List *pathkeys, |
| 1034 |
List *mergeclauses, |
| 1035 |
List *outersortkeys, |
| 1036 |
List *innersortkeys, |
| 1037 |
JoinType jointype, |
| 1038 |
JoinPathExtraData *extra, |
| 1039 |
bool is_partial) |
| 1040 |
{ |
| 1041 |
Relids required_outer; |
| 1042 |
int outer_presorted_keys = 0; |
| 1043 |
JoinCostWorkspace workspace; |
| 1044 |
|
| 1045 |
if (is_partial) |
| 1046 |
{ |
| 1047 |
try_partial_mergejoin_path(root, |
| 1048 |
joinrel, |
| 1049 |
outer_path, |
| 1050 |
inner_path, |
| 1051 |
pathkeys, |
| 1052 |
mergeclauses, |
| 1053 |
outersortkeys, |
| 1054 |
innersortkeys, |
| 1055 |
jointype, |
| 1056 |
extra); |
| 1057 |
return; |
| 1058 |
} |
| 1059 |
|
| 1060 |
/* |
| 1061 |
* If we are forming an outer join at this join, it's nonsensical to use |
| 1062 |
* an input path that uses the outer join as part of its parameterization. |
| 1063 |
* (This can happen despite our join order restrictions, since those apply |
| 1064 |
* to what is in an input relation not what its parameters are.) |
| 1065 |
*/ |
| 1066 |
if (extra->sjinfo->ojrelid != 0 && |
| 1067 |
(bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) || |
| 1068 |
bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path)))) |
| 1069 |
return; |
| 1070 |
|
| 1071 |
/* |
| 1072 |
* Check to see if proposed path is still parameterized, and reject if the |
| 1073 |
* parameterization wouldn't be sensible. |
| 1074 |
*/ |
| 1075 |
required_outer = calc_non_nestloop_required_outer(outer_path, |
| 1076 |
inner_path); |
| 1077 |
if (required_outer && |
| 1078 |
!bms_overlap(required_outer, extra->param_source_rels)) |
| 1079 |
{ |
| 1080 |
/* Waste no memory when we reject a path here */ |
| 1081 |
bms_free(required_outer); |
| 1082 |
return; |
| 1083 |
} |
| 1084 |
|
| 1085 |
/* |
| 1086 |
* If the given paths are already well enough ordered, we can skip doing |
| 1087 |
* an explicit sort. |
| 1088 |
* |
| 1089 |
* We need to determine the number of presorted keys of the outer path to |
| 1090 |
* decide whether explicit incremental sort can be applied when |
| 1091 |
* outersortkeys is not NIL. We do not need to do the same for the inner |
| 1092 |
* path though, as incremental sort currently does not support |
| 1093 |
* mark/restore. |
| 1094 |
*/ |
| 1095 |
if (outersortkeys && |
| 1096 |
pathkeys_count_contained_in(outersortkeys, outer_path->pathkeys, |
| 1097 |
&outer_presorted_keys)) |
| 1098 |
outersortkeys = NIL; |
| 1099 |
if (innersortkeys && |
| 1100 |
pathkeys_contained_in(innersortkeys, inner_path->pathkeys)) |
| 1101 |
innersortkeys = NIL; |
| 1102 |
|
| 1103 |
/* |
| 1104 |
* See comments in try_nestloop_path(). |
| 1105 |
*/ |
| 1106 |
initial_cost_mergejoin(root, &workspace, jointype, mergeclauses, |
| 1107 |
outer_path, inner_path, |
| 1108 |
outersortkeys, innersortkeys, |
| 1109 |
outer_presorted_keys, |
| 1110 |
extra); |
| 1111 |
|
| 1112 |
if (add_path_precheck(joinrel, workspace.disabled_nodes, |
| 1113 |
workspace.startup_cost, workspace.total_cost, |
| 1114 |
pathkeys, required_outer)) |
| 1115 |
{ |
| 1116 |
add_path(joinrel, (Path *) |
| 1117 |
create_mergejoin_path(root, |
| 1118 |
joinrel, |
| 1119 |
jointype, |
| 1120 |
&workspace, |
| 1121 |
extra, |
| 1122 |
outer_path, |
| 1123 |
inner_path, |
| 1124 |
extra->restrictlist, |
| 1125 |
pathkeys, |
| 1126 |
required_outer, |
| 1127 |
mergeclauses, |
| 1128 |
outersortkeys, |
| 1129 |
innersortkeys, |
| 1130 |
outer_presorted_keys)); |
| 1131 |
} |
| 1132 |
else |
| 1133 |
{ |
| 1134 |
/* Waste no memory when we reject a path here */ |
| 1135 |
bms_free(required_outer); |
| 1136 |
} |
| 1137 |
} |
| 1138 |
|
| 1139 |
/* |
| 1140 |
* try_partial_mergejoin_path |
| 1141 |
* Consider a partial merge join path; if it appears useful, push it into |
| 1142 |
* the joinrel's pathlist via add_partial_path(). |
| 1143 |
*/ |
| 1144 |
static void |
| 1145 |
try_partial_mergejoin_path(PlannerInfo *root, |
| 1146 |
RelOptInfo *joinrel, |
| 1147 |
Path *outer_path, |
| 1148 |
Path *inner_path, |
| 1149 |
List *pathkeys, |
| 1150 |
List *mergeclauses, |
| 1151 |
List *outersortkeys, |
| 1152 |
List *innersortkeys, |
| 1153 |
JoinType jointype, |
| 1154 |
JoinPathExtraData *extra) |
| 1155 |
{ |
| 1156 |
int outer_presorted_keys = 0; |
| 1157 |
JoinCostWorkspace workspace; |
| 1158 |
|
| 1159 |
/* |
| 1160 |
* See comments in try_partial_hashjoin_path(). |
| 1161 |
*/ |
| 1162 |
Assert(bms_is_empty(joinrel->lateral_relids)); |
| 1163 |
Assert(bms_is_empty(PATH_REQ_OUTER(outer_path))); |
| 1164 |
if (!bms_is_empty(PATH_REQ_OUTER(inner_path))) |
| 1165 |
return; |
| 1166 |
|
| 1167 |
/* |
| 1168 |
* If the given paths are already well enough ordered, we can skip doing |
| 1169 |
* an explicit sort. |
| 1170 |
* |
| 1171 |
* We need to determine the number of presorted keys of the outer path to |
| 1172 |
* decide whether explicit incremental sort can be applied when |
| 1173 |
* outersortkeys is not NIL. We do not need to do the same for the inner |
| 1174 |
* path though, as incremental sort currently does not support |
| 1175 |
* mark/restore. |
| 1176 |
*/ |
| 1177 |
if (outersortkeys && |
| 1178 |
pathkeys_count_contained_in(outersortkeys, outer_path->pathkeys, |
| 1179 |
&outer_presorted_keys)) |
| 1180 |
outersortkeys = NIL; |
| 1181 |
if (innersortkeys && |
| 1182 |
pathkeys_contained_in(innersortkeys, inner_path->pathkeys)) |
| 1183 |
innersortkeys = NIL; |
| 1184 |
|
| 1185 |
/* |
| 1186 |
* See comments in try_partial_nestloop_path(). |
| 1187 |
*/ |
| 1188 |
initial_cost_mergejoin(root, &workspace, jointype, mergeclauses, |
| 1189 |
outer_path, inner_path, |
| 1190 |
outersortkeys, innersortkeys, |
| 1191 |
outer_presorted_keys, |
| 1192 |
extra); |
| 1193 |
|
| 1194 |
if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes, |
| 1195 |
workspace.total_cost, pathkeys)) |
| 1196 |
return; |
| 1197 |
|
| 1198 |
/* Might be good enough to be worth trying, so let's try it. */ |
| 1199 |
add_partial_path(joinrel, (Path *) |
| 1200 |
create_mergejoin_path(root, |
| 1201 |
joinrel, |
| 1202 |
jointype, |
| 1203 |
&workspace, |
| 1204 |
extra, |
| 1205 |
outer_path, |
| 1206 |
inner_path, |
| 1207 |
extra->restrictlist, |
| 1208 |
pathkeys, |
| 1209 |
NULL, |
| 1210 |
mergeclauses, |
| 1211 |
outersortkeys, |
| 1212 |
innersortkeys, |
| 1213 |
outer_presorted_keys)); |
| 1214 |
} |
| 1215 |
|
| 1216 |
/* |
| 1217 |
* try_hashjoin_path |
| 1218 |
* Consider a hash join path; if it appears useful, push it into |
| 1219 |
* the joinrel's pathlist via add_path(). |
| 1220 |
*/ |
| 1221 |
static void |
| 1222 |
try_hashjoin_path(PlannerInfo *root, |
| 1223 |
RelOptInfo *joinrel, |
| 1224 |
Path *outer_path, |
| 1225 |
Path *inner_path, |
| 1226 |
List *hashclauses, |
| 1227 |
JoinType jointype, |
| 1228 |
JoinPathExtraData *extra) |
| 1229 |
{ |
| 1230 |
Relids required_outer; |
| 1231 |
JoinCostWorkspace workspace; |
| 1232 |
|
| 1233 |
/* |
| 1234 |
* If we are forming an outer join at this join, it's nonsensical to use |
| 1235 |
* an input path that uses the outer join as part of its parameterization. |
| 1236 |
* (This can happen despite our join order restrictions, since those apply |
| 1237 |
* to what is in an input relation not what its parameters are.) |
| 1238 |
*/ |
| 1239 |
if (extra->sjinfo->ojrelid != 0 && |
| 1240 |
(bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(inner_path)) || |
| 1241 |
bms_is_member(extra->sjinfo->ojrelid, PATH_REQ_OUTER(outer_path)))) |
| 1242 |
return; |
| 1243 |
|
| 1244 |
/* |
| 1245 |
* Check to see if proposed path is still parameterized, and reject if the |
| 1246 |
* parameterization wouldn't be sensible. |
| 1247 |
*/ |
| 1248 |
required_outer = calc_non_nestloop_required_outer(outer_path, |
| 1249 |
inner_path); |
| 1250 |
if (required_outer && |
| 1251 |
!bms_overlap(required_outer, extra->param_source_rels)) |
| 1252 |
{ |
| 1253 |
/* Waste no memory when we reject a path here */ |
| 1254 |
bms_free(required_outer); |
| 1255 |
return; |
| 1256 |
} |
| 1257 |
|
| 1258 |
/* |
| 1259 |
* See comments in try_nestloop_path(). Also note that hashjoin paths |
| 1260 |
* never have any output pathkeys, per comments in create_hashjoin_path. |
| 1261 |
*/ |
| 1262 |
initial_cost_hashjoin(root, &workspace, jointype, hashclauses, |
| 1263 |
outer_path, inner_path, extra, false); |
| 1264 |
|
| 1265 |
if (add_path_precheck(joinrel, workspace.disabled_nodes, |
| 1266 |
workspace.startup_cost, workspace.total_cost, |
| 1267 |
NIL, required_outer)) |
| 1268 |
{ |
| 1269 |
add_path(joinrel, (Path *) |
| 1270 |
create_hashjoin_path(root, |
| 1271 |
joinrel, |
| 1272 |
jointype, |
| 1273 |
&workspace, |
| 1274 |
extra, |
| 1275 |
outer_path, |
| 1276 |
inner_path, |
| 1277 |
false, /* parallel_hash */ |
| 1278 |
extra->restrictlist, |
| 1279 |
required_outer, |
| 1280 |
hashclauses)); |
| 1281 |
} |
| 1282 |
else |
| 1283 |
{ |
| 1284 |
/* Waste no memory when we reject a path here */ |
| 1285 |
bms_free(required_outer); |
| 1286 |
} |
| 1287 |
} |
| 1288 |
|
| 1289 |
/* |
| 1290 |
* try_partial_hashjoin_path |
| 1291 |
* Consider a partial hashjoin join path; if it appears useful, push it into |
| 1292 |
* the joinrel's partial_pathlist via add_partial_path(). |
| 1293 |
* The outer side is partial. If parallel_hash is true, then the inner path |
| 1294 |
* must be partial and will be run in parallel to create one or more shared |
| 1295 |
* hash tables; otherwise the inner path must be complete and a copy of it |
| 1296 |
* is run in every process to create separate identical private hash tables. |
| 1297 |
*/ |
| 1298 |
static void |
| 1299 |
try_partial_hashjoin_path(PlannerInfo *root, |
| 1300 |
RelOptInfo *joinrel, |
| 1301 |
Path *outer_path, |
| 1302 |
Path *inner_path, |
| 1303 |
List *hashclauses, |
| 1304 |
JoinType jointype, |
| 1305 |
JoinPathExtraData *extra, |
| 1306 |
bool parallel_hash) |
| 1307 |
{ |
| 1308 |
JoinCostWorkspace workspace; |
| 1309 |
|
| 1310 |
/* |
| 1311 |
* If the inner path is parameterized, we can't use a partial hashjoin. |
| 1312 |
* Parameterized partial paths are not supported. The caller should |
| 1313 |
* already have verified that no lateral rels are required here. |
| 1314 |
*/ |
| 1315 |
Assert(bms_is_empty(joinrel->lateral_relids)); |
| 1316 |
Assert(bms_is_empty(PATH_REQ_OUTER(outer_path))); |
| 1317 |
if (!bms_is_empty(PATH_REQ_OUTER(inner_path))) |
| 1318 |
return; |
| 1319 |
|
| 1320 |
/* |
| 1321 |
* Before creating a path, get a quick lower bound on what it is likely to |
| 1322 |
* cost. Bail out right away if it looks terrible. |
| 1323 |
*/ |
| 1324 |
initial_cost_hashjoin(root, &workspace, jointype, hashclauses, |
| 1325 |
outer_path, inner_path, extra, parallel_hash); |
| 1326 |
if (!add_partial_path_precheck(joinrel, workspace.disabled_nodes, |
| 1327 |
workspace.total_cost, NIL)) |
| 1328 |
return; |
| 1329 |
|
| 1330 |
/* Might be good enough to be worth trying, so let's try it. */ |
| 1331 |
add_partial_path(joinrel, (Path *) |
| 1332 |
create_hashjoin_path(root, |
| 1333 |
joinrel, |
| 1334 |
jointype, |
| 1335 |
&workspace, |
| 1336 |
extra, |
| 1337 |
outer_path, |
| 1338 |
inner_path, |
| 1339 |
parallel_hash, |
| 1340 |
extra->restrictlist, |
| 1341 |
NULL, |
| 1342 |
hashclauses)); |
| 1343 |
} |
| 1344 |
|
| 1345 |
/* |
| 1346 |
* sort_inner_and_outer |
| 1347 |
* Create mergejoin join paths by explicitly sorting both the outer and |
| 1348 |
* inner join relations on each available merge ordering. |
| 1349 |
* |
| 1350 |
* 'joinrel' is the join relation |
| 1351 |
* 'outerrel' is the outer join relation |
| 1352 |
* 'innerrel' is the inner join relation |
| 1353 |
* 'jointype' is the type of join to do |
| 1354 |
* 'extra' contains additional input values |
| 1355 |
*/ |
| 1356 |
static void |
| 1357 |
sort_inner_and_outer(PlannerInfo *root, |
| 1358 |
RelOptInfo *joinrel, |
| 1359 |
RelOptInfo *outerrel, |
| 1360 |
RelOptInfo *innerrel, |
| 1361 |
JoinType jointype, |
| 1362 |
JoinPathExtraData *extra) |
| 1363 |
{ |
| 1364 |
JoinType save_jointype = jointype; |
| 1365 |
Path *outer_path; |
| 1366 |
Path *inner_path; |
| 1367 |
Path *cheapest_partial_outer = NULL; |
| 1368 |
Path *cheapest_safe_inner = NULL; |
| 1369 |
List *all_pathkeys; |
| 1370 |
ListCell *l; |
| 1371 |
|
| 1372 |
/* Nothing to do if there are no available mergejoin clauses */ |
| 1373 |
if (extra->mergeclause_list == NIL) |
| 1374 |
return; |
| 1375 |
|
| 1376 |
/* |
| 1377 |
* We only consider the cheapest-total-cost input paths, since we are |
| 1378 |
* assuming here that a sort is required. We will consider |
| 1379 |
* cheapest-startup-cost input paths later, and only if they don't need a |
| 1380 |
* sort. |
| 1381 |
* |
| 1382 |
* This function intentionally does not consider parameterized input |
| 1383 |
* paths, except when the cheapest-total is parameterized. If we did so, |
| 1384 |
* we'd have a combinatorial explosion of mergejoin paths of dubious |
| 1385 |
* value. This interacts with decisions elsewhere that also discriminate |
| 1386 |
* against mergejoins with parameterized inputs; see comments in |
| 1387 |
* src/backend/optimizer/README. |
| 1388 |
*/ |
| 1389 |
outer_path = outerrel->cheapest_total_path; |
| 1390 |
inner_path = innerrel->cheapest_total_path; |
| 1391 |
|
| 1392 |
/* |
| 1393 |
* If either cheapest-total path is parameterized by the other rel, we |
| 1394 |
* can't use a mergejoin. (There's no use looking for alternative input |
| 1395 |
* paths, since these should already be the least-parameterized available |
| 1396 |
* paths.) |
| 1397 |
*/ |
| 1398 |
if (PATH_PARAM_BY_REL(outer_path, innerrel) || |
| 1399 |
PATH_PARAM_BY_REL(inner_path, outerrel)) |
| 1400 |
return; |
| 1401 |
|
| 1402 |
/* |
| 1403 |
* If unique-ification is requested, do it and then handle as a plain |
| 1404 |
* inner join. |
| 1405 |
*/ |
| 1406 |
if (jointype == JOIN_UNIQUE_OUTER) |
| 1407 |
{ |
| 1408 |
outer_path = (Path *) create_unique_path(root, outerrel, |
| 1409 |
outer_path, extra->sjinfo); |
| 1410 |
Assert(outer_path); |
| 1411 |
jointype = JOIN_INNER; |
| 1412 |
} |
| 1413 |
else if (jointype == JOIN_UNIQUE_INNER) |
| 1414 |
{ |
| 1415 |
inner_path = (Path *) create_unique_path(root, innerrel, |
| 1416 |
inner_path, extra->sjinfo); |
| 1417 |
Assert(inner_path); |
| 1418 |
jointype = JOIN_INNER; |
| 1419 |
} |
| 1420 |
|
| 1421 |
/* |
| 1422 |
* If the joinrel is parallel-safe, we may be able to consider a partial |
| 1423 |
* merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the |
| 1424 |
* outer path will be partial, and therefore we won't be able to properly |
| 1425 |
* guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT |
| 1426 |
* and JOIN_RIGHT_ANTI, because they can produce false null extended rows. |
| 1427 |
* Also, the resulting path must not be parameterized. |
| 1428 |
*/ |
| 1429 |
if (joinrel->consider_parallel && |
| 1430 |
save_jointype != JOIN_UNIQUE_OUTER && |
| 1431 |
save_jointype != JOIN_FULL && |
| 1432 |
save_jointype != JOIN_RIGHT && |
| 1433 |
save_jointype != JOIN_RIGHT_ANTI && |
| 1434 |
outerrel->partial_pathlist != NIL && |
| 1435 |
bms_is_empty(joinrel->lateral_relids)) |
| 1436 |
{ |
| 1437 |
cheapest_partial_outer = (Path *) linitial(outerrel->partial_pathlist); |
| 1438 |
|
| 1439 |
if (inner_path->parallel_safe) |
| 1440 |
cheapest_safe_inner = inner_path; |
| 1441 |
else if (save_jointype != JOIN_UNIQUE_INNER) |
| 1442 |
cheapest_safe_inner = |
| 1443 |
get_cheapest_parallel_safe_total_inner(innerrel->pathlist); |
| 1444 |
} |
| 1445 |
|
| 1446 |
/* |
| 1447 |
* Each possible ordering of the available mergejoin clauses will generate |
| 1448 |
* a differently-sorted result path at essentially the same cost. We have |
| 1449 |
* no basis for choosing one over another at this level of joining, but |
| 1450 |
* some sort orders may be more useful than others for higher-level |
| 1451 |
* mergejoins, so it's worth considering multiple orderings. |
| 1452 |
* |
| 1453 |
* Actually, it's not quite true that every mergeclause ordering will |
| 1454 |
* generate a different path order, because some of the clauses may be |
| 1455 |
* partially redundant (refer to the same EquivalenceClasses). Therefore, |
| 1456 |
* what we do is convert the mergeclause list to a list of canonical |
| 1457 |
* pathkeys, and then consider different orderings of the pathkeys. |
| 1458 |
* |
| 1459 |
* Generating a path for *every* permutation of the pathkeys doesn't seem |
| 1460 |
* like a winning strategy; the cost in planning time is too high. For |
| 1461 |
* now, we generate one path for each pathkey, listing that pathkey first |
| 1462 |
* and the rest in random order. This should allow at least a one-clause |
| 1463 |
* mergejoin without re-sorting against any other possible mergejoin |
| 1464 |
* partner path. But if we've not guessed the right ordering of secondary |
| 1465 |
* keys, we may end up evaluating clauses as qpquals when they could have |
| 1466 |
* been done as mergeclauses. (In practice, it's rare that there's more |
| 1467 |
* than two or three mergeclauses, so expending a huge amount of thought |
| 1468 |
* on that is probably not worth it.) |
| 1469 |
* |
| 1470 |
* The pathkey order returned by select_outer_pathkeys_for_merge() has |
| 1471 |
* some heuristics behind it (see that function), so be sure to try it |
| 1472 |
* exactly as-is as well as making variants. |
| 1473 |
*/ |
| 1474 |
all_pathkeys = select_outer_pathkeys_for_merge(root, |
| 1475 |
extra->mergeclause_list, |
| 1476 |
joinrel); |
| 1477 |
|
| 1478 |
foreach(l, all_pathkeys) |
| 1479 |
{ |
| 1480 |
PathKey *front_pathkey = (PathKey *) lfirst(l); |
| 1481 |
List *cur_mergeclauses; |
| 1482 |
List *outerkeys; |
| 1483 |
List *innerkeys; |
| 1484 |
List *merge_pathkeys; |
| 1485 |
|
| 1486 |
/* Make a pathkey list with this guy first */ |
| 1487 |
if (l != list_head(all_pathkeys)) |
| 1488 |
outerkeys = lcons(front_pathkey, |
| 1489 |
list_delete_nth_cell(list_copy(all_pathkeys), |
| 1490 |
foreach_current_index(l))); |
| 1491 |
else |
| 1492 |
outerkeys = all_pathkeys; /* no work at first one... */ |
| 1493 |
|
| 1494 |
/* Sort the mergeclauses into the corresponding ordering */ |
| 1495 |
cur_mergeclauses = |
| 1496 |
find_mergeclauses_for_outer_pathkeys(root, |
| 1497 |
outerkeys, |
| 1498 |
extra->mergeclause_list); |
| 1499 |
|
| 1500 |
/* Should have used them all... */ |
| 1501 |
Assert(list_length(cur_mergeclauses) == list_length(extra->mergeclause_list)); |
| 1502 |
|
| 1503 |
/* Build sort pathkeys for the inner side */ |
| 1504 |
innerkeys = make_inner_pathkeys_for_merge(root, |
| 1505 |
cur_mergeclauses, |
| 1506 |
outerkeys); |
| 1507 |
|
| 1508 |
/* Build pathkeys representing output sort order */ |
| 1509 |
merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, |
| 1510 |
outerkeys); |
| 1511 |
|
| 1512 |
/* |
| 1513 |
* And now we can make the path. |
| 1514 |
* |
| 1515 |
* Note: it's possible that the cheapest paths will already be sorted |
| 1516 |
* properly. try_mergejoin_path will detect that case and suppress an |
| 1517 |
* explicit sort step, so we needn't do so here. |
| 1518 |
*/ |
| 1519 |
try_mergejoin_path(root, |
| 1520 |
joinrel, |
| 1521 |
outer_path, |
| 1522 |
inner_path, |
| 1523 |
merge_pathkeys, |
| 1524 |
cur_mergeclauses, |
| 1525 |
outerkeys, |
| 1526 |
innerkeys, |
| 1527 |
jointype, |
| 1528 |
extra, |
| 1529 |
false); |
| 1530 |
|
| 1531 |
/* |
| 1532 |
* If we have partial outer and parallel safe inner path then try |
| 1533 |
* partial mergejoin path. |
| 1534 |
*/ |
| 1535 |
if (cheapest_partial_outer && cheapest_safe_inner) |
| 1536 |
try_partial_mergejoin_path(root, |
| 1537 |
joinrel, |
| 1538 |
cheapest_partial_outer, |
| 1539 |
cheapest_safe_inner, |
| 1540 |
merge_pathkeys, |
| 1541 |
cur_mergeclauses, |
| 1542 |
outerkeys, |
| 1543 |
innerkeys, |
| 1544 |
jointype, |
| 1545 |
extra); |
| 1546 |
} |
| 1547 |
} |
| 1548 |
|
| 1549 |
/* |
| 1550 |
* generate_mergejoin_paths |
| 1551 |
* Creates possible mergejoin paths for input outerpath. |
| 1552 |
* |
| 1553 |
* We generate mergejoins if mergejoin clauses are available. We have |
| 1554 |
* two ways to generate the inner path for a mergejoin: sort the cheapest |
| 1555 |
* inner path, or use an inner path that is already suitably ordered for the |
| 1556 |
* merge. If we have several mergeclauses, it could be that there is no inner |
| 1557 |
* path (or only a very expensive one) for the full list of mergeclauses, but |
| 1558 |
* better paths exist if we truncate the mergeclause list (thereby discarding |
| 1559 |
* some sort key requirements). So, we consider truncations of the |
| 1560 |
* mergeclause list as well as the full list. (Ideally we'd consider all |
| 1561 |
* subsets of the mergeclause list, but that seems way too expensive.) |
| 1562 |
*/ |
| 1563 |
static void |
| 1564 |
generate_mergejoin_paths(PlannerInfo *root, |
| 1565 |
RelOptInfo *joinrel, |
| 1566 |
RelOptInfo *innerrel, |
| 1567 |
Path *outerpath, |
| 1568 |
JoinType jointype, |
| 1569 |
JoinPathExtraData *extra, |
| 1570 |
bool useallclauses, |
| 1571 |
Path *inner_cheapest_total, |
| 1572 |
List *merge_pathkeys, |
| 1573 |
bool is_partial) |
| 1574 |
{ |
| 1575 |
List *mergeclauses; |
| 1576 |
List *innersortkeys; |
| 1577 |
List *trialsortkeys; |
| 1578 |
Path *cheapest_startup_inner; |
| 1579 |
Path *cheapest_total_inner; |
| 1580 |
JoinType save_jointype = jointype; |
| 1581 |
int num_sortkeys; |
| 1582 |
int sortkeycnt; |
| 1583 |
|
| 1584 |
if (jointype == JOIN_UNIQUE_OUTER || jointype == JOIN_UNIQUE_INNER) |
| 1585 |
jointype = JOIN_INNER; |
| 1586 |
|
| 1587 |
/* Look for useful mergeclauses (if any) */ |
| 1588 |
mergeclauses = |
| 1589 |
find_mergeclauses_for_outer_pathkeys(root, |
| 1590 |
outerpath->pathkeys, |
| 1591 |
extra->mergeclause_list); |
| 1592 |
|
| 1593 |
/* |
| 1594 |
* Done with this outer path if no chance for a mergejoin. |
| 1595 |
* |
| 1596 |
* Special corner case: for "x FULL JOIN y ON true", there will be no join |
| 1597 |
* clauses at all. Ordinarily we'd generate a clauseless nestloop path, |
| 1598 |
* but since mergejoin is our only join type that supports FULL JOIN |
| 1599 |
* without any join clauses, it's necessary to generate a clauseless |
| 1600 |
* mergejoin path instead. |
| 1601 |
*/ |
| 1602 |
if (mergeclauses == NIL) |
| 1603 |
{ |
| 1604 |
if (jointype == JOIN_FULL) |
| 1605 |
/* okay to try for mergejoin */ ; |
| 1606 |
else |
| 1607 |
return; |
| 1608 |
} |
| 1609 |
if (useallclauses && |
| 1610 |
list_length(mergeclauses) != list_length(extra->mergeclause_list)) |
| 1611 |
return; |
| 1612 |
|
| 1613 |
/* Compute the required ordering of the inner path */ |
| 1614 |
innersortkeys = make_inner_pathkeys_for_merge(root, |
| 1615 |
mergeclauses, |
| 1616 |
outerpath->pathkeys); |
| 1617 |
|
| 1618 |
/* |
| 1619 |
* Generate a mergejoin on the basis of sorting the cheapest inner. Since |
| 1620 |
* a sort will be needed, only cheapest total cost matters. (But |
| 1621 |
* try_mergejoin_path will do the right thing if inner_cheapest_total is |
| 1622 |
* already correctly sorted.) |
| 1623 |
*/ |
| 1624 |
try_mergejoin_path(root, |
| 1625 |
joinrel, |
| 1626 |
outerpath, |
| 1627 |
inner_cheapest_total, |
| 1628 |
merge_pathkeys, |
| 1629 |
mergeclauses, |
| 1630 |
NIL, |
| 1631 |
innersortkeys, |
| 1632 |
jointype, |
| 1633 |
extra, |
| 1634 |
is_partial); |
| 1635 |
|
| 1636 |
/* Can't do anything else if inner path needs to be unique'd */ |
| 1637 |
if (save_jointype == JOIN_UNIQUE_INNER) |
| 1638 |
return; |
| 1639 |
|
| 1640 |
/* |
| 1641 |
* Look for presorted inner paths that satisfy the innersortkey list --- |
| 1642 |
* or any truncation thereof, if we are allowed to build a mergejoin using |
| 1643 |
* a subset of the merge clauses. Here, we consider both cheap startup |
| 1644 |
* cost and cheap total cost. |
| 1645 |
* |
| 1646 |
* Currently we do not consider parameterized inner paths here. This |
| 1647 |
* interacts with decisions elsewhere that also discriminate against |
| 1648 |
* mergejoins with parameterized inputs; see comments in |
| 1649 |
* src/backend/optimizer/README. |
| 1650 |
* |
| 1651 |
* As we shorten the sortkey list, we should consider only paths that are |
| 1652 |
* strictly cheaper than (in particular, not the same as) any path found |
| 1653 |
* in an earlier iteration. Otherwise we'd be intentionally using fewer |
| 1654 |
* merge keys than a given path allows (treating the rest as plain |
| 1655 |
* joinquals), which is unlikely to be a good idea. Also, eliminating |
| 1656 |
* paths here on the basis of compare_path_costs is a lot cheaper than |
| 1657 |
* building the mergejoin path only to throw it away. |
| 1658 |
* |
| 1659 |
* If inner_cheapest_total is well enough sorted to have not required a |
| 1660 |
* sort in the path made above, we shouldn't make a duplicate path with |
| 1661 |
* it, either. We handle that case with the same logic that handles the |
| 1662 |
* previous consideration, by initializing the variables that track |
| 1663 |
* cheapest-so-far properly. Note that we do NOT reject |
| 1664 |
* inner_cheapest_total if we find it matches some shorter set of |
| 1665 |
* pathkeys. That case corresponds to using fewer mergekeys to avoid |
| 1666 |
* sorting inner_cheapest_total, whereas we did sort it above, so the |
| 1667 |
* plans being considered are different. |
| 1668 |
*/ |
| 1669 |
if (pathkeys_contained_in(innersortkeys, |
| 1670 |
inner_cheapest_total->pathkeys)) |
| 1671 |
{ |
| 1672 |
/* inner_cheapest_total didn't require a sort */ |
| 1673 |
cheapest_startup_inner = inner_cheapest_total; |
| 1674 |
cheapest_total_inner = inner_cheapest_total; |
| 1675 |
} |
| 1676 |
else |
| 1677 |
{ |
| 1678 |
/* it did require a sort, at least for the full set of keys */ |
| 1679 |
cheapest_startup_inner = NULL; |
| 1680 |
cheapest_total_inner = NULL; |
| 1681 |
} |
| 1682 |
num_sortkeys = list_length(innersortkeys); |
| 1683 |
if (num_sortkeys > 1 && !useallclauses) |
| 1684 |
trialsortkeys = list_copy(innersortkeys); /* need modifiable copy */ |
| 1685 |
else |
| 1686 |
trialsortkeys = innersortkeys; /* won't really truncate */ |
| 1687 |
|
| 1688 |
for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--) |
| 1689 |
{ |
| 1690 |
Path *innerpath; |
| 1691 |
List *newclauses = NIL; |
| 1692 |
|
| 1693 |
/* |
| 1694 |
* Look for an inner path ordered well enough for the first |
| 1695 |
* 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified |
| 1696 |
* destructively, which is why we made a copy... |
| 1697 |
*/ |
| 1698 |
trialsortkeys = list_truncate(trialsortkeys, sortkeycnt); |
| 1699 |
innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist, |
| 1700 |
trialsortkeys, |
| 1701 |
NULL, |
| 1702 |
TOTAL_COST, |
| 1703 |
is_partial); |
| 1704 |
if (innerpath != NULL && |
| 1705 |
(cheapest_total_inner == NULL || |
| 1706 |
compare_path_costs(innerpath, cheapest_total_inner, |
| 1707 |
TOTAL_COST) < 0)) |
| 1708 |
{ |
| 1709 |
/* Found a cheap (or even-cheaper) sorted path */ |
| 1710 |
/* Select the right mergeclauses, if we didn't already */ |
| 1711 |
if (sortkeycnt < num_sortkeys) |
| 1712 |
{ |
| 1713 |
newclauses = |
| 1714 |
trim_mergeclauses_for_inner_pathkeys(root, |
| 1715 |
mergeclauses, |
| 1716 |
trialsortkeys); |
| 1717 |
Assert(newclauses != NIL); |
| 1718 |
} |
| 1719 |
else |
| 1720 |
newclauses = mergeclauses; |
| 1721 |
try_mergejoin_path(root, |
| 1722 |
joinrel, |
| 1723 |
outerpath, |
| 1724 |
innerpath, |
| 1725 |
merge_pathkeys, |
| 1726 |
newclauses, |
| 1727 |
NIL, |
| 1728 |
NIL, |
| 1729 |
jointype, |
| 1730 |
extra, |
| 1731 |
is_partial); |
| 1732 |
cheapest_total_inner = innerpath; |
| 1733 |
} |
| 1734 |
/* Same on the basis of cheapest startup cost ... */ |
| 1735 |
innerpath = get_cheapest_path_for_pathkeys(innerrel->pathlist, |
| 1736 |
trialsortkeys, |
| 1737 |
NULL, |
| 1738 |
STARTUP_COST, |
| 1739 |
is_partial); |
| 1740 |
if (innerpath != NULL && |
| 1741 |
(cheapest_startup_inner == NULL || |
| 1742 |
compare_path_costs(innerpath, cheapest_startup_inner, |
| 1743 |
STARTUP_COST) < 0)) |
| 1744 |
{ |
| 1745 |
/* Found a cheap (or even-cheaper) sorted path */ |
| 1746 |
if (innerpath != cheapest_total_inner) |
| 1747 |
{ |
| 1748 |
/* |
| 1749 |
* Avoid rebuilding clause list if we already made one; saves |
| 1750 |
* memory in big join trees... |
| 1751 |
*/ |
| 1752 |
if (newclauses == NIL) |
| 1753 |
{ |
| 1754 |
if (sortkeycnt < num_sortkeys) |
| 1755 |
{ |
| 1756 |
newclauses = |
| 1757 |
trim_mergeclauses_for_inner_pathkeys(root, |
| 1758 |
mergeclauses, |
| 1759 |
trialsortkeys); |
| 1760 |
Assert(newclauses != NIL); |
| 1761 |
} |
| 1762 |
else |
| 1763 |
newclauses = mergeclauses; |
| 1764 |
} |
| 1765 |
try_mergejoin_path(root, |
| 1766 |
joinrel, |
| 1767 |
outerpath, |
| 1768 |
innerpath, |
| 1769 |
merge_pathkeys, |
| 1770 |
newclauses, |
| 1771 |
NIL, |
| 1772 |
NIL, |
| 1773 |
jointype, |
| 1774 |
extra, |
| 1775 |
is_partial); |
| 1776 |
} |
| 1777 |
cheapest_startup_inner = innerpath; |
| 1778 |
} |
| 1779 |
|
| 1780 |
/* |
| 1781 |
* Don't consider truncated sortkeys if we need all clauses. |
| 1782 |
*/ |
| 1783 |
if (useallclauses) |
| 1784 |
break; |
| 1785 |
} |
| 1786 |
} |
| 1787 |
|
| 1788 |
/* |
| 1789 |
* match_unsorted_outer |
| 1790 |
* Creates possible join paths for processing a single join relation |
| 1791 |
* 'joinrel' by employing either iterative substitution or |
| 1792 |
* mergejoining on each of its possible outer paths (considering |
| 1793 |
* only outer paths that are already ordered well enough for merging). |
| 1794 |
* |
| 1795 |
* We always generate a nestloop path for each available outer path. |
| 1796 |
* In fact we may generate as many as five: one on the cheapest-total-cost |
| 1797 |
* inner path, one on the same with materialization, one on the |
| 1798 |
* cheapest-startup-cost inner path (if different), one on the |
| 1799 |
* cheapest-total inner-indexscan path (if any), and one on the |
| 1800 |
* cheapest-startup inner-indexscan path (if different). |
| 1801 |
* |
| 1802 |
* We also consider mergejoins if mergejoin clauses are available. See |
| 1803 |
* detailed comments in generate_mergejoin_paths. |
| 1804 |
* |
| 1805 |
* 'joinrel' is the join relation |
| 1806 |
* 'outerrel' is the outer join relation |
| 1807 |
* 'innerrel' is the inner join relation |
| 1808 |
* 'jointype' is the type of join to do |
| 1809 |
* 'extra' contains additional input values |
| 1810 |
*/ |
| 1811 |
static void |
| 1812 |
match_unsorted_outer(PlannerInfo *root, |
| 1813 |
RelOptInfo *joinrel, |
| 1814 |
RelOptInfo *outerrel, |
| 1815 |
RelOptInfo *innerrel, |
| 1816 |
JoinType jointype, |
| 1817 |
JoinPathExtraData *extra) |
| 1818 |
{ |
| 1819 |
JoinType save_jointype = jointype; |
| 1820 |
bool nestjoinOK; |
| 1821 |
bool useallclauses; |
| 1822 |
Path *inner_cheapest_total = innerrel->cheapest_total_path; |
| 1823 |
Path *matpath = NULL; |
| 1824 |
ListCell *lc1; |
| 1825 |
|
| 1826 |
/* |
| 1827 |
* For now we do not support RIGHT_SEMI join in mergejoin or nestloop |
| 1828 |
* join. |
| 1829 |
*/ |
| 1830 |
if (jointype == JOIN_RIGHT_SEMI) |
| 1831 |
return; |
| 1832 |
|
| 1833 |
/* |
| 1834 |
* Nestloop only supports inner, left, semi, and anti joins. Also, if we |
| 1835 |
* are doing a right, right-anti or full mergejoin, we must use *all* the |
| 1836 |
* mergeclauses as join clauses, else we will not have a valid plan. |
| 1837 |
* (Although these two flags are currently inverses, keep them separate |
| 1838 |
* for clarity and possible future changes.) |
| 1839 |
*/ |
| 1840 |
switch (jointype) |
| 1841 |
{ |
| 1842 |
case JOIN_INNER: |
| 1843 |
case JOIN_LEFT: |
| 1844 |
case JOIN_SEMI: |
| 1845 |
case JOIN_ANTI: |
| 1846 |
nestjoinOK = true; |
| 1847 |
useallclauses = false; |
| 1848 |
break; |
| 1849 |
case JOIN_RIGHT: |
| 1850 |
case JOIN_RIGHT_ANTI: |
| 1851 |
case JOIN_FULL: |
| 1852 |
nestjoinOK = false; |
| 1853 |
useallclauses = true; |
| 1854 |
break; |
| 1855 |
case JOIN_UNIQUE_OUTER: |
| 1856 |
case JOIN_UNIQUE_INNER: |
| 1857 |
jointype = JOIN_INNER; |
| 1858 |
nestjoinOK = true; |
| 1859 |
useallclauses = false; |
| 1860 |
break; |
| 1861 |
default: |
| 1862 |
elog(ERROR, "unrecognized join type: %d", |
| 1863 |
(int) jointype); |
| 1864 |
nestjoinOK = false; /* keep compiler quiet */ |
| 1865 |
useallclauses = false; |
| 1866 |
break; |
| 1867 |
} |
| 1868 |
|
| 1869 |
/* |
| 1870 |
* If inner_cheapest_total is parameterized by the outer rel, ignore it; |
| 1871 |
* we will consider it below as a member of cheapest_parameterized_paths, |
| 1872 |
* but the other possibilities considered in this routine aren't usable. |
| 1873 |
*/ |
| 1874 |
if (PATH_PARAM_BY_REL(inner_cheapest_total, outerrel)) |
| 1875 |
inner_cheapest_total = NULL; |
| 1876 |
|
| 1877 |
/* |
| 1878 |
* If we need to unique-ify the inner path, we will consider only the |
| 1879 |
* cheapest-total inner. |
| 1880 |
*/ |
| 1881 |
if (save_jointype == JOIN_UNIQUE_INNER) |
| 1882 |
{ |
| 1883 |
/* No way to do this with an inner path parameterized by outer rel */ |
| 1884 |
if (inner_cheapest_total == NULL) |
| 1885 |
return; |
| 1886 |
inner_cheapest_total = (Path *) |
| 1887 |
create_unique_path(root, innerrel, inner_cheapest_total, extra->sjinfo); |
| 1888 |
Assert(inner_cheapest_total); |
| 1889 |
} |
| 1890 |
else if (nestjoinOK) |
| 1891 |
{ |
| 1892 |
/* |
| 1893 |
* Consider materializing the cheapest inner path, unless |
| 1894 |
* enable_material is off or the path in question materializes its |
| 1895 |
* output anyway. |
| 1896 |
*/ |
| 1897 |
if (enable_material && inner_cheapest_total != NULL && |
| 1898 |
!ExecMaterializesOutput(inner_cheapest_total->pathtype)) |
| 1899 |
matpath = (Path *) |
| 1900 |
create_material_path(innerrel, inner_cheapest_total); |
| 1901 |
} |
| 1902 |
|
| 1903 |
foreach(lc1, outerrel->pathlist) |
| 1904 |
{ |
| 1905 |
Path *outerpath = (Path *) lfirst(lc1); |
| 1906 |
List *merge_pathkeys; |
| 1907 |
|
| 1908 |
/* |
| 1909 |
* We cannot use an outer path that is parameterized by the inner rel. |
| 1910 |
*/ |
| 1911 |
if (PATH_PARAM_BY_REL(outerpath, innerrel)) |
| 1912 |
continue; |
| 1913 |
|
| 1914 |
/* |
| 1915 |
* If we need to unique-ify the outer path, it's pointless to consider |
| 1916 |
* any but the cheapest outer. (XXX we don't consider parameterized |
| 1917 |
* outers, nor inners, for unique-ified cases. Should we?) |
| 1918 |
*/ |
| 1919 |
if (save_jointype == JOIN_UNIQUE_OUTER) |
| 1920 |
{ |
| 1921 |
if (outerpath != outerrel->cheapest_total_path) |
| 1922 |
continue; |
| 1923 |
outerpath = (Path *) create_unique_path(root, outerrel, |
| 1924 |
outerpath, extra->sjinfo); |
| 1925 |
Assert(outerpath); |
| 1926 |
} |
| 1927 |
|
| 1928 |
/* |
| 1929 |
* The result will have this sort order (even if it is implemented as |
| 1930 |
* a nestloop, and even if some of the mergeclauses are implemented by |
| 1931 |
* qpquals rather than as true mergeclauses): |
| 1932 |
*/ |
| 1933 |
merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, |
| 1934 |
outerpath->pathkeys); |
| 1935 |
|
| 1936 |
if (save_jointype == JOIN_UNIQUE_INNER) |
| 1937 |
{ |
| 1938 |
/* |
| 1939 |
* Consider nestloop join, but only with the unique-ified cheapest |
| 1940 |
* inner path |
| 1941 |
*/ |
| 1942 |
try_nestloop_path(root, |
| 1943 |
joinrel, |
| 1944 |
outerpath, |
| 1945 |
inner_cheapest_total, |
| 1946 |
merge_pathkeys, |
| 1947 |
jointype, |
| 1948 |
extra); |
| 1949 |
} |
| 1950 |
else if (nestjoinOK) |
| 1951 |
{ |
| 1952 |
/* |
| 1953 |
* Consider nestloop joins using this outer path and various |
| 1954 |
* available paths for the inner relation. We consider the |
| 1955 |
* cheapest-total paths for each available parameterization of the |
| 1956 |
* inner relation, including the unparameterized case. |
| 1957 |
*/ |
| 1958 |
ListCell *lc2; |
| 1959 |
|
| 1960 |
foreach(lc2, innerrel->cheapest_parameterized_paths) |
| 1961 |
{ |
| 1962 |
Path *innerpath = (Path *) lfirst(lc2); |
| 1963 |
Path *mpath; |
| 1964 |
|
| 1965 |
try_nestloop_path(root, |
| 1966 |
joinrel, |
| 1967 |
outerpath, |
| 1968 |
innerpath, |
| 1969 |
merge_pathkeys, |
| 1970 |
jointype, |
| 1971 |
extra); |
| 1972 |
|
| 1973 |
/* |
| 1974 |
* Try generating a memoize path and see if that makes the |
| 1975 |
* nested loop any cheaper. |
| 1976 |
*/ |
| 1977 |
mpath = get_memoize_path(root, innerrel, outerrel, |
| 1978 |
innerpath, outerpath, jointype, |
| 1979 |
extra); |
| 1980 |
if (mpath != NULL) |
| 1981 |
try_nestloop_path(root, |
| 1982 |
joinrel, |
| 1983 |
outerpath, |
| 1984 |
mpath, |
| 1985 |
merge_pathkeys, |
| 1986 |
jointype, |
| 1987 |
extra); |
| 1988 |
} |
| 1989 |
|
| 1990 |
/* Also consider materialized form of the cheapest inner path */ |
| 1991 |
if (matpath != NULL) |
| 1992 |
try_nestloop_path(root, |
| 1993 |
joinrel, |
| 1994 |
outerpath, |
| 1995 |
matpath, |
| 1996 |
merge_pathkeys, |
| 1997 |
jointype, |
| 1998 |
extra); |
| 1999 |
} |
| 2000 |
|
| 2001 |
/* Can't do anything else if outer path needs to be unique'd */ |
| 2002 |
if (save_jointype == JOIN_UNIQUE_OUTER) |
| 2003 |
continue; |
| 2004 |
|
| 2005 |
/* Can't do anything else if inner rel is parameterized by outer */ |
| 2006 |
if (inner_cheapest_total == NULL) |
| 2007 |
continue; |
| 2008 |
|
| 2009 |
/* Generate merge join paths */ |
| 2010 |
generate_mergejoin_paths(root, joinrel, innerrel, outerpath, |
| 2011 |
save_jointype, extra, useallclauses, |
| 2012 |
inner_cheapest_total, merge_pathkeys, |
| 2013 |
false); |
| 2014 |
} |
| 2015 |
|
| 2016 |
/* |
| 2017 |
* Consider partial nestloop and mergejoin plan if outerrel has any |
| 2018 |
* partial path and the joinrel is parallel-safe. However, we can't |
| 2019 |
* handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and |
| 2020 |
* therefore we won't be able to properly guarantee uniqueness. Nor can |
| 2021 |
* we handle joins needing lateral rels, since partial paths must not be |
| 2022 |
* parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and |
| 2023 |
* JOIN_RIGHT_ANTI, because they can produce false null extended rows. |
| 2024 |
*/ |
| 2025 |
if (joinrel->consider_parallel && |
| 2026 |
save_jointype != JOIN_UNIQUE_OUTER && |
| 2027 |
save_jointype != JOIN_FULL && |
| 2028 |
save_jointype != JOIN_RIGHT && |
| 2029 |
save_jointype != JOIN_RIGHT_ANTI && |
| 2030 |
outerrel->partial_pathlist != NIL && |
| 2031 |
bms_is_empty(joinrel->lateral_relids)) |
| 2032 |
{ |
| 2033 |
if (nestjoinOK) |
| 2034 |
consider_parallel_nestloop(root, joinrel, outerrel, innerrel, |
| 2035 |
save_jointype, extra); |
| 2036 |
|
| 2037 |
/* |
| 2038 |
* If inner_cheapest_total is NULL or non parallel-safe then find the |
| 2039 |
* cheapest total parallel safe path. If doing JOIN_UNIQUE_INNER, we |
| 2040 |
* can't use any alternative inner path. |
| 2041 |
*/ |
| 2042 |
if (inner_cheapest_total == NULL || |
| 2043 |
!inner_cheapest_total->parallel_safe) |
| 2044 |
{ |
| 2045 |
if (save_jointype == JOIN_UNIQUE_INNER) |
| 2046 |
return; |
| 2047 |
|
| 2048 |
inner_cheapest_total = get_cheapest_parallel_safe_total_inner(innerrel->pathlist); |
| 2049 |
} |
| 2050 |
|
| 2051 |
if (inner_cheapest_total) |
| 2052 |
consider_parallel_mergejoin(root, joinrel, outerrel, innerrel, |
| 2053 |
save_jointype, extra, |
| 2054 |
inner_cheapest_total); |
| 2055 |
} |
| 2056 |
} |
| 2057 |
|
| 2058 |
/* |
| 2059 |
* consider_parallel_mergejoin |
| 2060 |
* Try to build partial paths for a joinrel by joining a partial path |
| 2061 |
* for the outer relation to a complete path for the inner relation. |
| 2062 |
* |
| 2063 |
* 'joinrel' is the join relation |
| 2064 |
* 'outerrel' is the outer join relation |
| 2065 |
* 'innerrel' is the inner join relation |
| 2066 |
* 'jointype' is the type of join to do |
| 2067 |
* 'extra' contains additional input values |
| 2068 |
* 'inner_cheapest_total' cheapest total path for innerrel |
| 2069 |
*/ |
| 2070 |
static void |
| 2071 |
consider_parallel_mergejoin(PlannerInfo *root, |
| 2072 |
RelOptInfo *joinrel, |
| 2073 |
RelOptInfo *outerrel, |
| 2074 |
RelOptInfo *innerrel, |
| 2075 |
JoinType jointype, |
| 2076 |
JoinPathExtraData *extra, |
| 2077 |
Path *inner_cheapest_total) |
| 2078 |
{ |
| 2079 |
ListCell *lc1; |
| 2080 |
|
| 2081 |
/* generate merge join path for each partial outer path */ |
| 2082 |
foreach(lc1, outerrel->partial_pathlist) |
| 2083 |
{ |
| 2084 |
Path *outerpath = (Path *) lfirst(lc1); |
| 2085 |
List *merge_pathkeys; |
| 2086 |
|
| 2087 |
/* |
| 2088 |
* Figure out what useful ordering any paths we create will have. |
| 2089 |
*/ |
| 2090 |
merge_pathkeys = build_join_pathkeys(root, joinrel, jointype, |
| 2091 |
outerpath->pathkeys); |
| 2092 |
|
| 2093 |
generate_mergejoin_paths(root, joinrel, innerrel, outerpath, jointype, |
| 2094 |
extra, false, inner_cheapest_total, |
| 2095 |
merge_pathkeys, true); |
| 2096 |
} |
| 2097 |
} |
| 2098 |
|
| 2099 |
/* |
| 2100 |
* consider_parallel_nestloop |
| 2101 |
* Try to build partial paths for a joinrel by joining a partial path for the |
| 2102 |
* outer relation to a complete path for the inner relation. |
| 2103 |
* |
| 2104 |
* 'joinrel' is the join relation |
| 2105 |
* 'outerrel' is the outer join relation |
| 2106 |
* 'innerrel' is the inner join relation |
| 2107 |
* 'jointype' is the type of join to do |
| 2108 |
* 'extra' contains additional input values |
| 2109 |
*/ |
| 2110 |
static void |
| 2111 |
consider_parallel_nestloop(PlannerInfo *root, |
| 2112 |
RelOptInfo *joinrel, |
| 2113 |
RelOptInfo *outerrel, |
| 2114 |
RelOptInfo *innerrel, |
| 2115 |
JoinType jointype, |
| 2116 |
JoinPathExtraData *extra) |
| 2117 |
{ |
| 2118 |
JoinType save_jointype = jointype; |
| 2119 |
Path *inner_cheapest_total = innerrel->cheapest_total_path; |
| 2120 |
Path *matpath = NULL; |
| 2121 |
ListCell *lc1; |
| 2122 |
|
| 2123 |
if (jointype == JOIN_UNIQUE_INNER) |
| 2124 |
jointype = JOIN_INNER; |
| 2125 |
|
| 2126 |
/* |
| 2127 |
* Consider materializing the cheapest inner path, unless: 1) we're doing |
| 2128 |
* JOIN_UNIQUE_INNER, because in this case we have to unique-ify the |
| 2129 |
* cheapest inner path, 2) enable_material is off, 3) the cheapest inner |
| 2130 |
* path is not parallel-safe, 4) the cheapest inner path is parameterized |
| 2131 |
* by the outer rel, or 5) the cheapest inner path materializes its output |
| 2132 |
* anyway. |
| 2133 |
*/ |
| 2134 |
if (save_jointype != JOIN_UNIQUE_INNER && |
| 2135 |
enable_material && inner_cheapest_total->parallel_safe && |
| 2136 |
!PATH_PARAM_BY_REL(inner_cheapest_total, outerrel) && |
| 2137 |
!ExecMaterializesOutput(inner_cheapest_total->pathtype)) |
| 2138 |
{ |
| 2139 |
matpath = (Path *) |
| 2140 |
create_material_path(innerrel, inner_cheapest_total); |
| 2141 |
Assert(matpath->parallel_safe); |
| 2142 |
} |
| 2143 |
|
| 2144 |
foreach(lc1, outerrel->partial_pathlist) |
| 2145 |
{ |
| 2146 |
Path *outerpath = (Path *) lfirst(lc1); |
| 2147 |
List *pathkeys; |
| 2148 |
ListCell *lc2; |
| 2149 |
|
| 2150 |
/* Figure out what useful ordering any paths we create will have. */ |
| 2151 |
pathkeys = build_join_pathkeys(root, joinrel, jointype, |
| 2152 |
outerpath->pathkeys); |
| 2153 |
|
| 2154 |
/* |
| 2155 |
* Try the cheapest parameterized paths; only those which will produce |
| 2156 |
* an unparameterized path when joined to this outerrel will survive |
| 2157 |
* try_partial_nestloop_path. The cheapest unparameterized path is |
| 2158 |
* also in this list. |
| 2159 |
*/ |
| 2160 |
foreach(lc2, innerrel->cheapest_parameterized_paths) |
| 2161 |
{ |
| 2162 |
Path *innerpath = (Path *) lfirst(lc2); |
| 2163 |
Path *mpath; |
| 2164 |
|
| 2165 |
/* Can't join to an inner path that is not parallel-safe */ |
| 2166 |
if (!innerpath->parallel_safe) |
| 2167 |
continue; |
| 2168 |
|
| 2169 |
/* |
| 2170 |
* If we're doing JOIN_UNIQUE_INNER, we can only use the inner's |
| 2171 |
* cheapest_total_path, and we have to unique-ify it. (We might |
| 2172 |
* be able to relax this to allow other safe, unparameterized |
| 2173 |
* inner paths, but right now create_unique_path is not on board |
| 2174 |
* with that.) |
| 2175 |
*/ |
| 2176 |
if (save_jointype == JOIN_UNIQUE_INNER) |
| 2177 |
{ |
| 2178 |
if (innerpath != innerrel->cheapest_total_path) |
| 2179 |
continue; |
| 2180 |
innerpath = (Path *) create_unique_path(root, innerrel, |
| 2181 |
innerpath, |
| 2182 |
extra->sjinfo); |
| 2183 |
Assert(innerpath); |
| 2184 |
} |
| 2185 |
|
| 2186 |
try_partial_nestloop_path(root, joinrel, outerpath, innerpath, |
| 2187 |
pathkeys, jointype, extra); |
| 2188 |
|
| 2189 |
/* |
| 2190 |
* Try generating a memoize path and see if that makes the nested |
| 2191 |
* loop any cheaper. |
| 2192 |
*/ |
| 2193 |
mpath = get_memoize_path(root, innerrel, outerrel, |
| 2194 |
innerpath, outerpath, jointype, |
| 2195 |
extra); |
| 2196 |
if (mpath != NULL) |
| 2197 |
try_partial_nestloop_path(root, joinrel, outerpath, mpath, |
| 2198 |
pathkeys, jointype, extra); |
| 2199 |
} |
| 2200 |
|
| 2201 |
/* Also consider materialized form of the cheapest inner path */ |
| 2202 |
if (matpath != NULL) |
| 2203 |
try_partial_nestloop_path(root, joinrel, outerpath, matpath, |
| 2204 |
pathkeys, jointype, extra); |
| 2205 |
} |
| 2206 |
} |
| 2207 |
|
| 2208 |
/* |
| 2209 |
* hash_inner_and_outer |
| 2210 |
* Create hashjoin join paths by explicitly hashing both the outer and |
| 2211 |
* inner keys of each available hash clause. |
| 2212 |
* |
| 2213 |
* 'joinrel' is the join relation |
| 2214 |
* 'outerrel' is the outer join relation |
| 2215 |
* 'innerrel' is the inner join relation |
| 2216 |
* 'jointype' is the type of join to do |
| 2217 |
* 'extra' contains additional input values |
| 2218 |
*/ |
| 2219 |
static void |
| 2220 |
hash_inner_and_outer(PlannerInfo *root, |
| 2221 |
RelOptInfo *joinrel, |
| 2222 |
RelOptInfo *outerrel, |
| 2223 |
RelOptInfo *innerrel, |
| 2224 |
JoinType jointype, |
| 2225 |
JoinPathExtraData *extra) |
| 2226 |
{ |
| 2227 |
JoinType save_jointype = jointype; |
| 2228 |
bool isouterjoin = IS_OUTER_JOIN(jointype); |
| 2229 |
List *hashclauses; |
| 2230 |
ListCell *l; |
| 2231 |
|
| 2232 |
/* |
| 2233 |
* We need to build only one hashclauses list for any given pair of outer |
| 2234 |
* and inner relations; all of the hashable clauses will be used as keys. |
| 2235 |
* |
| 2236 |
* Scan the join's restrictinfo list to find hashjoinable clauses that are |
| 2237 |
* usable with this pair of sub-relations. |
| 2238 |
*/ |
| 2239 |
hashclauses = NIL; |
| 2240 |
foreach(l, extra->restrictlist) |
| 2241 |
{ |
| 2242 |
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); |
| 2243 |
|
| 2244 |
/* |
| 2245 |
* If processing an outer join, only use its own join clauses for |
| 2246 |
* hashing. For inner joins we need not be so picky. |
| 2247 |
*/ |
| 2248 |
if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids)) |
| 2249 |
continue; |
| 2250 |
|
| 2251 |
if (!restrictinfo->can_join || |
| 2252 |
restrictinfo->hashjoinoperator == InvalidOid) |
| 2253 |
continue; /* not hashjoinable */ |
| 2254 |
|
| 2255 |
/* |
| 2256 |
* Check if clause has the form "outer op inner" or "inner op outer". |
| 2257 |
*/ |
| 2258 |
if (!clause_sides_match_join(restrictinfo, outerrel->relids, |
| 2259 |
innerrel->relids)) |
| 2260 |
continue; /* no good for these input relations */ |
| 2261 |
|
| 2262 |
/* |
| 2263 |
* If clause has the form "inner op outer", check if its operator has |
| 2264 |
* valid commutator. This is necessary because hashclauses in this |
| 2265 |
* form will get commuted in createplan.c to put the outer var on the |
| 2266 |
* left (see get_switched_clauses). This probably shouldn't ever |
| 2267 |
* fail, since hashable operators ought to have commutators, but be |
| 2268 |
* paranoid. |
| 2269 |
* |
| 2270 |
* The clause being hashjoinable indicates that it's an OpExpr. |
| 2271 |
*/ |
| 2272 |
if (!restrictinfo->outer_is_left && |
| 2273 |
!OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno))) |
| 2274 |
continue; |
| 2275 |
|
| 2276 |
hashclauses = lappend(hashclauses, restrictinfo); |
| 2277 |
} |
| 2278 |
|
| 2279 |
/* If we found any usable hashclauses, make paths */ |
| 2280 |
if (hashclauses) |
| 2281 |
{ |
| 2282 |
/* |
| 2283 |
* We consider both the cheapest-total-cost and cheapest-startup-cost |
| 2284 |
* outer paths. There's no need to consider any but the |
| 2285 |
* cheapest-total-cost inner path, however. |
| 2286 |
*/ |
| 2287 |
Path *cheapest_startup_outer = outerrel->cheapest_startup_path; |
| 2288 |
Path *cheapest_total_outer = outerrel->cheapest_total_path; |
| 2289 |
Path *cheapest_total_inner = innerrel->cheapest_total_path; |
| 2290 |
|
| 2291 |
/* |
| 2292 |
* If either cheapest-total path is parameterized by the other rel, we |
| 2293 |
* can't use a hashjoin. (There's no use looking for alternative |
| 2294 |
* input paths, since these should already be the least-parameterized |
| 2295 |
* available paths.) |
| 2296 |
*/ |
| 2297 |
if (PATH_PARAM_BY_REL(cheapest_total_outer, innerrel) || |
| 2298 |
PATH_PARAM_BY_REL(cheapest_total_inner, outerrel)) |
| 2299 |
return; |
| 2300 |
|
| 2301 |
/* Unique-ify if need be; we ignore parameterized possibilities */ |
| 2302 |
if (jointype == JOIN_UNIQUE_OUTER) |
| 2303 |
{ |
| 2304 |
cheapest_total_outer = (Path *) |
| 2305 |
create_unique_path(root, outerrel, |
| 2306 |
cheapest_total_outer, extra->sjinfo); |
| 2307 |
Assert(cheapest_total_outer); |
| 2308 |
jointype = JOIN_INNER; |
| 2309 |
try_hashjoin_path(root, |
| 2310 |
joinrel, |
| 2311 |
cheapest_total_outer, |
| 2312 |
cheapest_total_inner, |
| 2313 |
hashclauses, |
| 2314 |
jointype, |
| 2315 |
extra); |
| 2316 |
/* no possibility of cheap startup here */ |
| 2317 |
} |
| 2318 |
else if (jointype == JOIN_UNIQUE_INNER) |
| 2319 |
{ |
| 2320 |
cheapest_total_inner = (Path *) |
| 2321 |
create_unique_path(root, innerrel, |
| 2322 |
cheapest_total_inner, extra->sjinfo); |
| 2323 |
Assert(cheapest_total_inner); |
| 2324 |
jointype = JOIN_INNER; |
| 2325 |
try_hashjoin_path(root, |
| 2326 |
joinrel, |
| 2327 |
cheapest_total_outer, |
| 2328 |
cheapest_total_inner, |
| 2329 |
hashclauses, |
| 2330 |
jointype, |
| 2331 |
extra); |
| 2332 |
if (cheapest_startup_outer != NULL && |
| 2333 |
cheapest_startup_outer != cheapest_total_outer) |
| 2334 |
try_hashjoin_path(root, |
| 2335 |
joinrel, |
| 2336 |
cheapest_startup_outer, |
| 2337 |
cheapest_total_inner, |
| 2338 |
hashclauses, |
| 2339 |
jointype, |
| 2340 |
extra); |
| 2341 |
} |
| 2342 |
else |
| 2343 |
{ |
| 2344 |
/* |
| 2345 |
* For other jointypes, we consider the cheapest startup outer |
| 2346 |
* together with the cheapest total inner, and then consider |
| 2347 |
* pairings of cheapest-total paths including parameterized ones. |
| 2348 |
* There is no use in generating parameterized paths on the basis |
| 2349 |
* of possibly cheap startup cost, so this is sufficient. |
| 2350 |
*/ |
| 2351 |
ListCell *lc1; |
| 2352 |
ListCell *lc2; |
| 2353 |
|
| 2354 |
if (cheapest_startup_outer != NULL) |
| 2355 |
try_hashjoin_path(root, |
| 2356 |
joinrel, |
| 2357 |
cheapest_startup_outer, |
| 2358 |
cheapest_total_inner, |
| 2359 |
hashclauses, |
| 2360 |
jointype, |
| 2361 |
extra); |
| 2362 |
|
| 2363 |
foreach(lc1, outerrel->cheapest_parameterized_paths) |
| 2364 |
{ |
| 2365 |
Path *outerpath = (Path *) lfirst(lc1); |
| 2366 |
|
| 2367 |
/* |
| 2368 |
* We cannot use an outer path that is parameterized by the |
| 2369 |
* inner rel. |
| 2370 |
*/ |
| 2371 |
if (PATH_PARAM_BY_REL(outerpath, innerrel)) |
| 2372 |
continue; |
| 2373 |
|
| 2374 |
foreach(lc2, innerrel->cheapest_parameterized_paths) |
| 2375 |
{ |
| 2376 |
Path *innerpath = (Path *) lfirst(lc2); |
| 2377 |
|
| 2378 |
/* |
| 2379 |
* We cannot use an inner path that is parameterized by |
| 2380 |
* the outer rel, either. |
| 2381 |
*/ |
| 2382 |
if (PATH_PARAM_BY_REL(innerpath, outerrel)) |
| 2383 |
continue; |
| 2384 |
|
| 2385 |
if (outerpath == cheapest_startup_outer && |
| 2386 |
innerpath == cheapest_total_inner) |
| 2387 |
continue; /* already tried it */ |
| 2388 |
|
| 2389 |
try_hashjoin_path(root, |
| 2390 |
joinrel, |
| 2391 |
outerpath, |
| 2392 |
innerpath, |
| 2393 |
hashclauses, |
| 2394 |
jointype, |
| 2395 |
extra); |
| 2396 |
} |
| 2397 |
} |
| 2398 |
} |
| 2399 |
|
| 2400 |
/* |
| 2401 |
* If the joinrel is parallel-safe, we may be able to consider a |
| 2402 |
* partial hash join. |
| 2403 |
* |
| 2404 |
* However, we can't handle JOIN_UNIQUE_OUTER, because the outer path |
| 2405 |
* will be partial, and therefore we won't be able to properly |
| 2406 |
* guarantee uniqueness. |
| 2407 |
* |
| 2408 |
* Similarly, we can't handle JOIN_RIGHT_SEMI, because the hash table |
| 2409 |
* is either a shared hash table or a private hash table per backend. |
| 2410 |
* In the shared case, there is no concurrency protection for the |
| 2411 |
* match flags, so multiple workers could inspect and set the flags |
| 2412 |
* concurrently, potentially producing incorrect results. In the |
| 2413 |
* private case, each worker has its own copy of the hash table, so no |
| 2414 |
* single process has all the match flags. |
| 2415 |
* |
| 2416 |
* Also, the resulting path must not be parameterized. |
| 2417 |
*/ |
| 2418 |
if (joinrel->consider_parallel && |
| 2419 |
save_jointype != JOIN_UNIQUE_OUTER && |
| 2420 |
save_jointype != JOIN_RIGHT_SEMI && |
| 2421 |
outerrel->partial_pathlist != NIL && |
| 2422 |
bms_is_empty(joinrel->lateral_relids)) |
| 2423 |
{ |
| 2424 |
Path *cheapest_partial_outer; |
| 2425 |
Path *cheapest_partial_inner = NULL; |
| 2426 |
Path *cheapest_safe_inner = NULL; |
| 2427 |
|
| 2428 |
cheapest_partial_outer = |
| 2429 |
(Path *) linitial(outerrel->partial_pathlist); |
| 2430 |
|
| 2431 |
/* |
| 2432 |
* Can we use a partial inner plan too, so that we can build a |
| 2433 |
* shared hash table in parallel? We can't handle |
| 2434 |
* JOIN_UNIQUE_INNER because we can't guarantee uniqueness. |
| 2435 |
*/ |
| 2436 |
if (innerrel->partial_pathlist != NIL && |
| 2437 |
save_jointype != JOIN_UNIQUE_INNER && |
| 2438 |
enable_parallel_hash) |
| 2439 |
{ |
| 2440 |
cheapest_partial_inner = |
| 2441 |
(Path *) linitial(innerrel->partial_pathlist); |
| 2442 |
try_partial_hashjoin_path(root, joinrel, |
| 2443 |
cheapest_partial_outer, |
| 2444 |
cheapest_partial_inner, |
| 2445 |
hashclauses, jointype, extra, |
| 2446 |
true /* parallel_hash */ ); |
| 2447 |
} |
| 2448 |
|
| 2449 |
/* |
| 2450 |
* Normally, given that the joinrel is parallel-safe, the cheapest |
| 2451 |
* total inner path will also be parallel-safe, but if not, we'll |
| 2452 |
* have to search for the cheapest safe, unparameterized inner |
| 2453 |
* path. If doing JOIN_UNIQUE_INNER, we can't use any alternative |
| 2454 |
* inner path. If full, right, or right-anti join, we can't use |
| 2455 |
* parallelism (building the hash table in each backend) because |
| 2456 |
* no one process has all the match bits. |
| 2457 |
*/ |
| 2458 |
if (save_jointype == JOIN_FULL || |
| 2459 |
save_jointype == JOIN_RIGHT || |
| 2460 |
save_jointype == JOIN_RIGHT_ANTI) |
| 2461 |
cheapest_safe_inner = NULL; |
| 2462 |
else if (cheapest_total_inner->parallel_safe) |
| 2463 |
cheapest_safe_inner = cheapest_total_inner; |
| 2464 |
else if (save_jointype != JOIN_UNIQUE_INNER) |
| 2465 |
cheapest_safe_inner = |
| 2466 |
get_cheapest_parallel_safe_total_inner(innerrel->pathlist); |
| 2467 |
|
| 2468 |
if (cheapest_safe_inner != NULL) |
| 2469 |
try_partial_hashjoin_path(root, joinrel, |
| 2470 |
cheapest_partial_outer, |
| 2471 |
cheapest_safe_inner, |
| 2472 |
hashclauses, jointype, extra, |
| 2473 |
false /* parallel_hash */ ); |
| 2474 |
} |
| 2475 |
} |
| 2476 |
} |
| 2477 |
|
| 2478 |
/* |
| 2479 |
* select_mergejoin_clauses |
| 2480 |
* Select mergejoin clauses that are usable for a particular join. |
| 2481 |
* Returns a list of RestrictInfo nodes for those clauses. |
| 2482 |
* |
| 2483 |
* *mergejoin_allowed is normally set to true, but it is set to false if |
| 2484 |
* this is a right-semi join, or this is a right/right-anti/full join and |
| 2485 |
* there are nonmergejoinable join clauses. The executor's mergejoin |
| 2486 |
* machinery cannot handle such cases, so we have to avoid generating a |
| 2487 |
* mergejoin plan. (Note that this flag does NOT consider whether there are |
| 2488 |
* actually any mergejoinable clauses. This is correct because in some |
| 2489 |
* cases we need to build a clauseless mergejoin. Simply returning NIL is |
| 2490 |
* therefore not enough to distinguish safe from unsafe cases.) |
| 2491 |
* |
| 2492 |
* We also mark each selected RestrictInfo to show which side is currently |
| 2493 |
* being considered as outer. These are transient markings that are only |
| 2494 |
* good for the duration of the current add_paths_to_joinrel() call! |
| 2495 |
* |
| 2496 |
* We examine each restrictinfo clause known for the join to see |
| 2497 |
* if it is mergejoinable and involves vars from the two sub-relations |
| 2498 |
* currently of interest. |
| 2499 |
*/ |
| 2500 |
static List * |
| 2501 |
select_mergejoin_clauses(PlannerInfo *root, |
| 2502 |
RelOptInfo *joinrel, |
| 2503 |
RelOptInfo *outerrel, |
| 2504 |
RelOptInfo *innerrel, |
| 2505 |
List *restrictlist, |
| 2506 |
JoinType jointype, |
| 2507 |
bool *mergejoin_allowed) |
| 2508 |
{ |
| 2509 |
List *result_list = NIL; |
| 2510 |
bool isouterjoin = IS_OUTER_JOIN(jointype); |
| 2511 |
bool have_nonmergeable_joinclause = false; |
| 2512 |
ListCell *l; |
| 2513 |
|
| 2514 |
/* |
| 2515 |
* For now we do not support RIGHT_SEMI join in mergejoin: the benefit of |
| 2516 |
* swapping inputs tends to be small here. |
| 2517 |
*/ |
| 2518 |
if (jointype == JOIN_RIGHT_SEMI) |
| 2519 |
{ |
| 2520 |
*mergejoin_allowed = false; |
| 2521 |
return NIL; |
| 2522 |
} |
| 2523 |
|
| 2524 |
foreach(l, restrictlist) |
| 2525 |
{ |
| 2526 |
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); |
| 2527 |
|
| 2528 |
/* |
| 2529 |
* If processing an outer join, only use its own join clauses in the |
| 2530 |
* merge. For inner joins we can use pushed-down clauses too. (Note: |
| 2531 |
* we don't set have_nonmergeable_joinclause here because pushed-down |
| 2532 |
* clauses will become otherquals not joinquals.) |
| 2533 |
*/ |
| 2534 |
if (isouterjoin && RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids)) |
| 2535 |
continue; |
| 2536 |
|
| 2537 |
/* Check that clause is a mergeable operator clause */ |
| 2538 |
if (!restrictinfo->can_join || |
| 2539 |
restrictinfo->mergeopfamilies == NIL) |
| 2540 |
{ |
| 2541 |
/* |
| 2542 |
* The executor can handle extra joinquals that are constants, but |
| 2543 |
* not anything else, when doing right/right-anti/full merge join. |
| 2544 |
* (The reason to support constants is so we can do FULL JOIN ON |
| 2545 |
* FALSE.) |
| 2546 |
*/ |
| 2547 |
if (!restrictinfo->clause || !IsA(restrictinfo->clause, Const)) |
| 2548 |
have_nonmergeable_joinclause = true; |
| 2549 |
continue; /* not mergejoinable */ |
| 2550 |
} |
| 2551 |
|
| 2552 |
/* |
| 2553 |
* Check if clause has the form "outer op inner" or "inner op outer". |
| 2554 |
*/ |
| 2555 |
if (!clause_sides_match_join(restrictinfo, outerrel->relids, |
| 2556 |
innerrel->relids)) |
| 2557 |
{ |
| 2558 |
have_nonmergeable_joinclause = true; |
| 2559 |
continue; /* no good for these input relations */ |
| 2560 |
} |
| 2561 |
|
| 2562 |
/* |
| 2563 |
* If clause has the form "inner op outer", check if its operator has |
| 2564 |
* valid commutator. This is necessary because mergejoin clauses in |
| 2565 |
* this form will get commuted in createplan.c to put the outer var on |
| 2566 |
* the left (see get_switched_clauses). This probably shouldn't ever |
| 2567 |
* fail, since mergejoinable operators ought to have commutators, but |
| 2568 |
* be paranoid. |
| 2569 |
* |
| 2570 |
* The clause being mergejoinable indicates that it's an OpExpr. |
| 2571 |
*/ |
| 2572 |
if (!restrictinfo->outer_is_left && |
| 2573 |
!OidIsValid(get_commutator(castNode(OpExpr, restrictinfo->clause)->opno))) |
| 2574 |
{ |
| 2575 |
have_nonmergeable_joinclause = true; |
| 2576 |
continue; |
| 2577 |
} |
| 2578 |
|
| 2579 |
/* |
| 2580 |
* Insist that each side have a non-redundant eclass. This |
| 2581 |
* restriction is needed because various bits of the planner expect |
| 2582 |
* that each clause in a merge be associable with some pathkey in a |
| 2583 |
* canonical pathkey list, but redundant eclasses can't appear in |
| 2584 |
* canonical sort orderings. (XXX it might be worth relaxing this, |
| 2585 |
* but not enough time to address it for 8.3.) |
| 2586 |
*/ |
| 2587 |
update_mergeclause_eclasses(root, restrictinfo); |
| 2588 |
|
| 2589 |
if (EC_MUST_BE_REDUNDANT(restrictinfo->left_ec) || |
| 2590 |
EC_MUST_BE_REDUNDANT(restrictinfo->right_ec)) |
| 2591 |
{ |
| 2592 |
have_nonmergeable_joinclause = true; |
| 2593 |
continue; /* can't handle redundant eclasses */ |
| 2594 |
} |
| 2595 |
|
| 2596 |
result_list = lappend(result_list, restrictinfo); |
| 2597 |
} |
| 2598 |
|
| 2599 |
/* |
| 2600 |
* Report whether mergejoin is allowed (see comment at top of function). |
| 2601 |
*/ |
| 2602 |
switch (jointype) |
| 2603 |
{ |
| 2604 |
case JOIN_RIGHT: |
| 2605 |
case JOIN_RIGHT_ANTI: |
| 2606 |
case JOIN_FULL: |
| 2607 |
*mergejoin_allowed = !have_nonmergeable_joinclause; |
| 2608 |
break; |
| 2609 |
default: |
| 2610 |
*mergejoin_allowed = true; |
| 2611 |
break; |
| 2612 |
} |
| 2613 |
|
| 2614 |
return result_list; |
| 2615 |
} |