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