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