Loading...
Searching...
No Matches
#include "postgres.h"#include "executor/executor.h"#include "foreign/fdwapi.h"#include "nodes/nodeFuncs.h"#include "optimizer/cost.h"#include "optimizer/optimizer.h"#include "optimizer/pathnode.h"#include "optimizer/paths.h"#include "optimizer/placeholder.h"#include "optimizer/planmain.h"#include "optimizer/restrictinfo.h"#include "utils/lsyscache.h"#include "utils/typcache.h"
Include dependency graph for joinpath.c:
Go to the source code of this file.
Macros | |
| #define | PATH_PARAM_BY_PARENT(path, rel) |
| #define | PATH_PARAM_BY_REL_SELF(path, rel) ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids)) |
| #define | PATH_PARAM_BY_REL(path, rel) (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel)) |
Variables | |
| set_join_pathlist_hook_type | set_join_pathlist_hook = NULL |
| join_path_setup_hook_type | join_path_setup_hook = NULL |
Macro Definition Documentation
◆ PATH_PARAM_BY_PARENT
| #define PATH_PARAM_BY_PARENT | ( | path, | |
| rel | |||
| ) |
Value:
(rel)->top_parent_relids))
Definition at line 39 of file joinpath.c.
130{
132 JoinPathExtraData extra;
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 */
145 joinrelids = joinrel->top_parent_relids;
146 else
147 joinrelids = joinrel->relids;
148
149 extra.restrictlist = restrictlist;
151 extra.sjinfo = sjinfo;
153 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 */
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 */
200 switch (jointype)
201 {
204 break;
207 outerrel->relids);
208 break;
211 joinrel->relids,
212 outerrel->relids,
213 innerrel,
214 JOIN_INNER,
215 restrictlist,
216 false);
217 break;
218 default:
220 joinrel->relids,
221 outerrel->relids,
222 innerrel,
223 jointype,
224 restrictlist,
225 false);
226 break;
227 }
228
229 /*
230 * If the outer or inner relation has been unique-ified, handle as a plain
231 * inner join.
232 */
234 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 */
244 joinrel,
245 outerrel,
246 innerrel,
247 restrictlist,
248 jointype,
249 &mergejoin_allowed);
250
251 /*
252 * If it's SEMI, ANTI, or inner_unique join, compute correction factors
253 * for cost estimation. These will be the same for all paths.
254 */
257 jointype, sjinfo, restrictlist,
258 &extra.semifactors);
259
260 /*
261 * Decide whether it's sensible to generate parameterized paths for this
262 * joinrel, and if so, which relations such paths should require. There
263 * is usually no need to create a parameterized result path unless there
264 * is a join order restriction that prevents joining one of our input rels
265 * directly to the parameter source rel instead of joining to the other
266 * input rel. (But see allow_star_schema_join().) This restriction
267 * reduces the number of parameterized paths we have to deal with at
268 * higher join levels, without compromising the quality of the resulting
269 * plan. We express the restriction as a Relids set that must overlap the
270 * parameterization of any proposed join path. Note: param_source_rels
271 * should contain only baserels, not OJ relids, so starting from
272 * all_baserels not all_query_rels is correct.
273 */
275 {
277
278 /*
279 * SJ is relevant to this join if we have some part of its RHS
280 * (possibly not all of it), and haven't yet joined to its LHS. (This
281 * test is pretty simplistic, but should be sufficient considering the
282 * join has already been proven legal.) If the SJ is relevant, it
283 * presents constraints for joining to anything not in its RHS.
284 */
289 sjinfo2->min_righthand));
290
291 /* full joins constrain both sides symmetrically */
297 sjinfo2->min_lefthand));
298 }
299
300 /*
301 * However, when a LATERAL subquery is involved, there will simply not be
302 * any paths for the joinrel that aren't parameterized by whatever the
303 * subquery is parameterized by, unless its parameterization is resolved
304 * within the joinrel. So we might as well allow additional dependencies
305 * on whatever residual lateral dependencies the joinrel will have.
306 */
308 joinrel->lateral_relids);
309
310 /*
311 * 1. Consider mergejoin paths where both relations must be explicitly
312 * sorted. Skip this if we can't mergejoin.
313 */
316 jointype, &extra);
317
318 /*
319 * 2. Consider paths where the outer relation need not be explicitly
320 * sorted. This includes both nestloops and mergejoins where the outer
321 * path is already ordered. Again, skip this if we can't mergejoin.
322 * (That's okay because we know that nestloop can't handle
323 * right/right-anti/right-semi/full joins at all, so it wouldn't work in
324 * the prohibited cases either.)
325 */
328 jointype, &extra);
329
330#ifdef NOT_USED
331
332 /*
333 * 3. Consider paths where the inner relation need not be explicitly
334 * sorted. This includes mergejoins only (nestloops were already built in
335 * match_unsorted_outer).
336 *
337 * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
338 * significant difference between the inner and outer side of a mergejoin,
339 * so match_unsorted_inner creates no paths that aren't equivalent to
340 * those made by match_unsorted_outer when add_paths_to_joinrel() is
341 * invoked with the two rels given in the other order.
342 */
345 jointype, &extra);
346#endif
347
348 /*
349 * 4. Consider paths where both outer and inner relations must be hashed
350 * before being joined. As above, when it's a full join, we must try this
351 * even when the path type is disabled, because it may be our only option.
352 */
355 jointype, &extra);
356
357 /*
358 * 5. If inner and outer relations are foreign tables (or joins) belonging
359 * to the same server and assigned to the same user to check access
360 * permissions as, give the FDW a chance to push down joins.
361 */
363 joinrel->fdwroutine->GetForeignJoinPaths)
364 joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
365 outerrel, innerrel,
366 save_jointype, &extra);
367
368 /*
369 * 6. Finally, give extensions a chance to manipulate the path list. They
370 * could add new paths (such as CustomPaths) by calling add_path(), or
371 * add_partial_path() if parallel aware.
372 *
373 * In theory, extensions could also use this hook to delete or modify
374 * paths added by the core code, but in practice this is difficult to make
375 * work, since it's too late to get back any paths that have already been
376 * discarded by add_path() or add_partial_path(). If you're trying to
377 * suppress paths, consider using join_path_setup_hook instead.
378 */
381 save_jointype, &extra);
382}
383
384/*
385 * We override the param_source_rels heuristic to accept nestloop paths in
386 * which the outer rel satisfies some but not all of the inner path's
387 * parameterization. This is necessary to get good plans for star-schema
388 * scenarios, in which a parameterized path for a large table may require
389 * parameters from multiple small tables that will not get joined directly to
390 * each other. We can handle that by stacking nestloops that have the small
391 * tables on the outside; but this breaks the rule the param_source_rels
392 * heuristic is based on, namely that parameters should not be passed down
393 * across joins unless there's a join-order-constraint-based reason to do so.
394 * So we ignore the param_source_rels restriction when this case applies.
395 *
396 * allow_star_schema_join() returns true if the param_source_rels restriction
397 * should be overridden, ie, it's okay to perform this join.
398 */
399static inline bool
401 Relids outerrelids,
403{
404 /*
405 * It's a star-schema case if the outer rel provides some but not all of
406 * the inner rel's parameterization.
407 */
410}
411
412/*
413 * If the parameterization is only partly satisfied by the outer rel,
414 * the unsatisfied part can't include any outer-join relids that could
415 * null rels of the satisfied part. That would imply that we're trying
416 * to use a clause involving a Var with nonempty varnullingrels at
417 * a join level where that value isn't yet computable.
418 *
419 * In practice, this test never finds a problem because earlier join order
420 * restrictions prevent us from attempting a join that would cause a problem.
421 * (That's unsurprising, because the code worked before we ever added
422 * outer-join relids to expression relids.) It still seems worth checking
423 * as a backstop, but we only do so in assert-enabled builds.
424 */
425#ifdef USE_ASSERT_CHECKING
426static inline bool
428 Relids outerrelids,
430{
431 bool result = false;
434
436 {
438
440 {
442
444 continue; /* not relevant */
448 {
449 result = true; /* doesn't work */
450 break;
451 }
452 }
453 }
454
455 /* Waste no memory when we reject a path here */
458
459 return result;
460}
461#endif /* USE_ASSERT_CHECKING */
462
463/*
464 * paraminfo_get_equal_hashops
465 * Determine if the clauses in param_info and innerrel's lateral vars
466 * can be hashed.
467 * Returns true if hashing is possible, otherwise false.
468 *
469 * Additionally, on success we collect the outer expressions and the
470 * appropriate equality operators for each hashable parameter to innerrel.
471 * These are returned in parallel lists in *param_exprs and *operators.
472 * We also set *binary_mode to indicate whether strict binary matching is
473 * required.
474 */
475static bool
480
481{
482 List *lateral_vars;
484
485 *param_exprs = NIL;
486 *operators = NIL;
487 *binary_mode = false;
488
489 /* Add join clauses from param_info to the hash key */
491 {
493
495 {
497 OpExpr *opexpr;
498 Node *expr;
500
502
503 /*
504 * Bail if the rinfo is not compatible. We need a join OpExpr
505 * with 2 args.
506 */
509 innerrel->relids))
510 {
511 list_free(*operators);
512 list_free(*param_exprs);
513 return false;
514 }
515
516 if (rinfo->outer_is_left)
517 {
519 hasheqoperator = rinfo->left_hasheqoperator;
520 }
521 else
522 {
524 hasheqoperator = rinfo->right_hasheqoperator;
525 }
526
527 /* can't do memoize if we can't hash the outer type */
529 {
530 list_free(*operators);
531 list_free(*param_exprs);
532 return false;
533 }
534
535 /*
536 * 'expr' may already exist as a parameter from a previous item in
537 * ppi_clauses. No need to include it again, however we'd better
538 * ensure we do switch into binary mode if required. See below.
539 */
541 {
543 *param_exprs = lappend(*param_exprs, expr);
544 }
545
546 /*
547 * When the join operator is not hashable then it's possible that
548 * the operator will be able to distinguish something that the
549 * hash equality operator could not. For example with floating
550 * point types -0.0 and +0.0 are classed as equal by the hash
551 * function and equality function, but some other operator may be
552 * able to tell those values apart. This means that we must put
553 * memoize into binary comparison mode so that it does bit-by-bit
554 * comparisons rather than a "logical" comparison as it would
555 * using the hash equality operator.
556 */
558 *binary_mode = true;
559 }
560 }
561
562 /* Now add any lateral vars to the cache key too */
565 {
567 TypeCacheEntry *typentry;
568
569 /* Reject if there are any volatile functions in lateral vars */
571 {
572 list_free(*operators);
573 list_free(*param_exprs);
574 return false;
575 }
576
579
580 /* can't use memoize without a valid hash proc and equals operator */
582 {
583 list_free(*operators);
584 list_free(*param_exprs);
585 return false;
586 }
587
588 /*
589 * 'expr' may already exist as a parameter from the ppi_clauses. No
590 * need to include it again, however we'd better ensure we do switch
591 * into binary mode.
592 */
594 {
596 *param_exprs = lappend(*param_exprs, expr);
597 }
598
599 /*
600 * We must go into binary mode as we don't have too much of an idea of
601 * how these lateral Vars are being used. See comment above when we
602 * set *binary_mode for the non-lateral Var case. This could be
603 * relaxed a bit if we had the RestrictInfos and knew the operators
604 * being used, however for cases like Vars that are arguments to
605 * functions we must operate in binary mode as we don't have
606 * visibility into what the function is doing with the Vars.
607 */
608 *binary_mode = true;
609 }
610
611 /* We're okay to use memoize */
612 return true;
613}
614
615/*
616 * extract_lateral_vars_from_PHVs
617 * Extract lateral references within PlaceHolderVars that are due to be
618 * evaluated at 'innerrelids'.
619 */
622{
625
626 /* Nothing would be found if the query contains no LATERAL RTEs */
629
630 /*
631 * No need to consider PHVs that are due to be evaluated at joinrels,
632 * since we do not add Memoize nodes on top of joinrel paths.
633 */
636
638 {
641 ListCell *cell;
642
643 /* PHV is uninteresting if no lateral refs */
645 continue;
646
647 /* PHV is uninteresting if not due to be evaluated at innerrelids */
649 continue;
650
651 /*
652 * If the PHV does not reference any rels in innerrelids, use its
653 * contained expression as a cache key rather than extracting the
654 * Vars/PHVs from it and using those. This can be beneficial in cases
655 * where the expression results in fewer distinct values to cache
656 * tuples for.
657 */
659 innerrelids))
660 {
662 continue;
663 }
664
665 /* Fetch Vars and PHVs of lateral references within PlaceHolderVars */
668 {
670
672 {
674
676
679 }
681 {
683
685
689 }
690 else
692 }
693
695 }
696
698}
699
700/*
701 * get_memoize_path
702 * If possible, make and return a Memoize path atop of 'inner_path'.
703 * Otherwise return NULL.
704 *
705 * Note that currently we do not add Memoize nodes on top of join relation
706 * paths. This is because the ParamPathInfos for join relation paths do not
707 * maintain ppi_clauses, as the set of relevant clauses varies depending on how
708 * the join is formed. In addition, joinrels do not maintain lateral_vars. So
709 * we do not have a way to extract cache keys from joinrels.
710 */
715 JoinPathExtraData *extra)
716{
717 List *param_exprs;
718 List *hash_operators;
720 bool binary_mode;
722
723 /* Obviously not if it's disabled */
726
727 /*
728 * We can safely not bother with all this unless we expect to perform more
729 * than one inner scan. The first scan is always going to be a cache
730 * miss. This would likely fail later anyway based on costs, so this is
731 * really just to save some wasted effort.
732 */
735
736 /*
737 * Extract lateral Vars/PHVs within PlaceHolderVars that are due to be
738 * evaluated at innerrel. These lateral Vars/PHVs could be used as
739 * memoize cache keys.
740 */
742
743 /*
744 * We can only have a memoize node when there's some kind of cache key,
745 * either parameterized path clauses or lateral Vars. No cache key sounds
746 * more like something a Materialize node might be more useful for.
747 */
753
754 /*
755 * Currently we don't do this for SEMI and ANTI joins, because nested loop
756 * SEMI/ANTI joins don't scan the inner node to completion, which means
757 * memoize cannot mark the cache entry as complete. Nor can we mark the
758 * cache entry as complete after fetching the first inner tuple, because
759 * if that tuple and the current outer tuple don't satisfy the join
760 * clauses, a second inner tuple that satisfies the parameters would find
761 * the cache entry already marked as complete. The only exception is when
762 * the inner relation is provably unique, as in that case, there won't be
763 * a second matching tuple and we can safely mark the cache entry as
764 * complete after fetching the first inner tuple. Note that in such
765 * cases, the SEMI join should have been reduced to an inner join by
766 * reduce_unique_semijoins.
767 */
769 !extra->inner_unique)
771
772 /*
773 * Memoize normally marks cache entries as complete when it runs out of
774 * tuples to read from its subplan. However, with unique joins, Nested
775 * Loop will skip to the next outer tuple after finding the first matching
776 * inner tuple. This means that we may not read the inner side of the
777 * join to completion which leaves no opportunity to mark the cache entry
778 * as complete. To work around that, when the join is unique we
779 * automatically mark cache entries as complete after fetching the first
780 * tuple. This works when the entire join condition is parameterized.
781 * Otherwise, when the parameterization is only a subset of the join
782 * condition, we can't be sure which part of it causes the join to be
783 * unique. This means there are no guarantees that only 1 tuple will be
784 * read. We cannot mark the cache entry as complete after reading the
785 * first tuple without that guarantee. This means the scope of Memoize
786 * node's usefulness is limited to only outer rows that have no join
787 * partner as this is the only case where Nested Loop would exhaust the
788 * inner scan of a unique join. Since the scope is limited to that, we
789 * just don't bother making a memoize path in this case.
790 *
791 * Lateral vars needn't be considered here as they're not considered when
792 * determining if the join is unique.
793 */
795 {
796 Bitmapset *ppi_serials;
797
800
801 ppi_serials = inner_path->param_info->ppi_serials;
802
804 {
807 }
808 }
809
810 /*
811 * We can't use a memoize node if there are volatile functions in the
812 * inner rel's target list or restrict list. A cache hit could reduce the
813 * number of calls to these functions.
814 */
817
819 {
821
824 }
825
826 /*
827 * Also check the parameterized path restrictinfos for volatile functions.
828 * Indexed functions must be immutable so shouldn't have any volatile
829 * functions, however, with a lateral join the inner scan may not be an
830 * index scan.
831 */
833 {
835 {
837
840 }
841 }
842
843 /* Check if we have hash ops for each parameter to the path */
845 inner_path->param_info,
846 outerrel->top_parent ?
847 outerrel->top_parent : outerrel,
848 innerrel,
849 ph_lateral_vars,
850 ¶m_exprs,
851 &hash_operators,
852 &binary_mode))
853 {
855 innerrel,
856 inner_path,
857 param_exprs,
858 hash_operators,
859 extra->inner_unique,
860 binary_mode,
861 outer_path->rows);
862 }
863
865}
866
867/*
868 * try_nestloop_path
869 * Consider a nestloop join path; if it appears useful, push it into
870 * the joinrel's pathlist via add_path().
871 */
872static void
874 RelOptInfo *joinrel,
877 List *pathkeys,
878 JoinType jointype,
880 JoinPathExtraData *extra)
881{
883 JoinCostWorkspace workspace;
887 Relids outerrelids;
890
891 /*
892 * If we are forming an outer join at this join, it's nonsensical to use
893 * an input path that uses the outer join as part of its parameterization.
894 * (This can happen despite our join order restrictions, since those apply
895 * to what is in an input relation not what its parameters are.)
896 */
900 return;
901
902 /*
903 * Any parameterization of the input paths refers to topmost parents of
904 * the relevant relations, because reparameterize_path_by_child() hasn't
905 * been called yet. So we must consider topmost parents of the relations
906 * being joined, too, while determining parameterization of the result and
907 * checking for disallowed parameterization cases.
908 */
911 else
913
915 outerrelids = outerrel->top_parent_relids;
916 else
917 outerrelids = outerrel->relids;
918
919 /*
920 * Check to see if proposed path is still parameterized, and reject if the
921 * parameterization wouldn't be sensible --- unless allow_star_schema_join
922 * says to allow it anyway.
923 */
929 {
930 /* Waste no memory when we reject a path here */
932 return;
933 }
934
935 /* If we got past that, we shouldn't have any unsafe outer-join refs */
937
938 /*
939 * If the inner path is parameterized, it is parameterized by the topmost
940 * parent of the outer rel, not the outer rel itself. We will need to
941 * translate the parameterization, if this path is chosen, during
942 * create_plan(). Here we just check whether we will be able to perform
943 * the translation, and if not avoid creating a nestloop path.
944 */
947 {
949 return;
950 }
951
952 /*
953 * Do a precheck to quickly eliminate obviously-inferior paths. We
954 * calculate a cheap lower bound on the path's cost and then use
955 * add_path_precheck() to see if the path is clearly going to be dominated
956 * by some existing path for the joinrel. If not, do the full pushup with
957 * creating a fully valid path structure and submitting it to add_path().
958 * The latter two steps are expensive enough to make this two-phase
959 * methodology worthwhile.
960 */
964
967 pathkeys, required_outer))
968 {
971 joinrel,
972 jointype,
973 &workspace,
974 extra,
975 outer_path,
976 inner_path,
977 extra->restrictlist,
978 pathkeys,
979 required_outer));
980 }
981 else
982 {
983 /* Waste no memory when we reject a path here */
985 }
986}
987
988/*
989 * try_partial_nestloop_path
990 * Consider a partial nestloop join path; if it appears useful, push it into
991 * the joinrel's partial_pathlist via add_partial_path().
992 */
993static void
995 RelOptInfo *joinrel,
998 List *pathkeys,
999 JoinType jointype,
1001 JoinPathExtraData *extra)
1002{
1003 JoinCostWorkspace workspace;
1004
1005 /*
1006 * If the inner path is parameterized, the parameterization must be fully
1007 * satisfied by the proposed outer path. Parameterized partial paths are
1008 * not supported. The caller should already have verified that no lateral
1009 * rels are required here.
1010 */
1014 {
1017 Relids outerrelids;
1018
1019 /*
1020 * The inner and outer paths are parameterized, if at all, by the top
1021 * level parents, not the child relations, so we must use those relids
1022 * for our parameterization tests.
1023 */
1025 outerrelids = outerrel->top_parent_relids;
1026 else
1027 outerrelids = outerrel->relids;
1028
1030 return;
1031 }
1032
1033 /*
1034 * If the inner path is parameterized, it is parameterized by the topmost
1035 * parent of the outer rel, not the outer rel itself. We will need to
1036 * translate the parameterization, if this path is chosen, during
1037 * create_plan(). Here we just check whether we will be able to perform
1038 * the translation, and if not avoid creating a nestloop path.
1039 */
1042 return;
1043
1044 /*
1045 * Before creating a path, get a quick lower bound on what it is likely to
1046 * cost. Bail out right away if it looks terrible.
1047 */
1051 workspace.total_cost, pathkeys))
1052 return;
1053
1054 /* Might be good enough to be worth trying, so let's try it. */
1057 joinrel,
1058 jointype,
1059 &workspace,
1060 extra,
1061 outer_path,
1062 inner_path,
1063 extra->restrictlist,
1064 pathkeys,
1065 NULL));
1066}
1067
1068/*
1069 * try_mergejoin_path
1070 * Consider a merge join path; if it appears useful, push it into
1071 * the joinrel's pathlist via add_path().
1072 */
1073static void
1075 RelOptInfo *joinrel,
1078 List *pathkeys,
1079 List *mergeclauses,
1080 List *outersortkeys,
1081 List *innersortkeys,
1082 JoinType jointype,
1083 JoinPathExtraData *extra,
1085{
1087 int outer_presorted_keys = 0;
1088 JoinCostWorkspace workspace;
1089
1091 {
1093 joinrel,
1094 outer_path,
1095 inner_path,
1096 pathkeys,
1097 mergeclauses,
1098 outersortkeys,
1099 innersortkeys,
1100 jointype,
1101 extra);
1102 return;
1103 }
1104
1105 /*
1106 * If we are forming an outer join at this join, it's nonsensical to use
1107 * an input path that uses the outer join as part of its parameterization.
1108 * (This can happen despite our join order restrictions, since those apply
1109 * to what is in an input relation not what its parameters are.)
1110 */
1114 return;
1115
1116 /*
1117 * Check to see if proposed path is still parameterized, and reject if the
1118 * parameterization wouldn't be sensible.
1119 */
1121 inner_path);
1124 {
1125 /* Waste no memory when we reject a path here */
1127 return;
1128 }
1129
1130 /*
1131 * If the given paths are already well enough ordered, we can skip doing
1132 * an explicit sort.
1133 *
1134 * We need to determine the number of presorted keys of the outer path to
1135 * decide whether explicit incremental sort can be applied when
1136 * outersortkeys is not NIL. We do not need to do the same for the inner
1137 * path though, as incremental sort currently does not support
1138 * mark/restore.
1139 */
1140 if (outersortkeys &&
1142 &outer_presorted_keys))
1143 outersortkeys = NIL;
1144 if (innersortkeys &&
1146 innersortkeys = NIL;
1147
1148 /*
1149 * See comments in try_nestloop_path().
1150 */
1153 outersortkeys, innersortkeys,
1154 outer_presorted_keys,
1155 extra);
1156
1159 pathkeys, required_outer))
1160 {
1163 joinrel,
1164 jointype,
1165 &workspace,
1166 extra,
1167 outer_path,
1168 inner_path,
1169 extra->restrictlist,
1170 pathkeys,
1171 required_outer,
1172 mergeclauses,
1173 outersortkeys,
1174 innersortkeys,
1175 outer_presorted_keys));
1176 }
1177 else
1178 {
1179 /* Waste no memory when we reject a path here */
1181 }
1182}
1183
1184/*
1185 * try_partial_mergejoin_path
1186 * Consider a partial merge join path; if it appears useful, push it into
1187 * the joinrel's pathlist via add_partial_path().
1188 */
1189static void
1191 RelOptInfo *joinrel,
1194 List *pathkeys,
1195 List *mergeclauses,
1196 List *outersortkeys,
1197 List *innersortkeys,
1198 JoinType jointype,
1199 JoinPathExtraData *extra)
1200{
1201 int outer_presorted_keys = 0;
1202 JoinCostWorkspace workspace;
1203
1204 /*
1205 * See comments in try_partial_hashjoin_path().
1206 */
1210 return;
1211
1212 /*
1213 * If the given paths are already well enough ordered, we can skip doing
1214 * an explicit sort.
1215 *
1216 * We need to determine the number of presorted keys of the outer path to
1217 * decide whether explicit incremental sort can be applied when
1218 * outersortkeys is not NIL. We do not need to do the same for the inner
1219 * path though, as incremental sort currently does not support
1220 * mark/restore.
1221 */
1222 if (outersortkeys &&
1224 &outer_presorted_keys))
1225 outersortkeys = NIL;
1226 if (innersortkeys &&
1228 innersortkeys = NIL;
1229
1230 /*
1231 * See comments in try_partial_nestloop_path().
1232 */
1235 outersortkeys, innersortkeys,
1236 outer_presorted_keys,
1237 extra);
1238
1240 workspace.total_cost, pathkeys))
1241 return;
1242
1243 /* Might be good enough to be worth trying, so let's try it. */
1246 joinrel,
1247 jointype,
1248 &workspace,
1249 extra,
1250 outer_path,
1251 inner_path,
1252 extra->restrictlist,
1253 pathkeys,
1254 NULL,
1255 mergeclauses,
1256 outersortkeys,
1257 innersortkeys,
1258 outer_presorted_keys));
1259}
1260
1261/*
1262 * try_hashjoin_path
1263 * Consider a hash join path; if it appears useful, push it into
1264 * the joinrel's pathlist via add_path().
1265 */
1266static void
1268 RelOptInfo *joinrel,
1271 List *hashclauses,
1272 JoinType jointype,
1273 JoinPathExtraData *extra)
1274{
1276 JoinCostWorkspace workspace;
1277
1278 /*
1279 * If we are forming an outer join at this join, it's nonsensical to use
1280 * an input path that uses the outer join as part of its parameterization.
1281 * (This can happen despite our join order restrictions, since those apply
1282 * to what is in an input relation not what its parameters are.)
1283 */
1287 return;
1288
1289 /*
1290 * Check to see if proposed path is still parameterized, and reject if the
1291 * parameterization wouldn't be sensible.
1292 */
1294 inner_path);
1297 {
1298 /* Waste no memory when we reject a path here */
1300 return;
1301 }
1302
1303 /*
1304 * See comments in try_nestloop_path(). Also note that hashjoin paths
1305 * never have any output pathkeys, per comments in create_hashjoin_path.
1306 */
1309
1313 {
1316 joinrel,
1317 jointype,
1318 &workspace,
1319 extra,
1320 outer_path,
1321 inner_path,
1322 false, /* parallel_hash */
1323 extra->restrictlist,
1324 required_outer,
1325 hashclauses));
1326 }
1327 else
1328 {
1329 /* Waste no memory when we reject a path here */
1331 }
1332}
1333
1334/*
1335 * try_partial_hashjoin_path
1336 * Consider a partial hashjoin join path; if it appears useful, push it into
1337 * the joinrel's partial_pathlist via add_partial_path().
1338 * The outer side is partial. If parallel_hash is true, then the inner path
1339 * must be partial and will be run in parallel to create one or more shared
1340 * hash tables; otherwise the inner path must be complete and a copy of it
1341 * is run in every process to create separate identical private hash tables.
1342 */
1343static void
1345 RelOptInfo *joinrel,
1348 List *hashclauses,
1349 JoinType jointype,
1350 JoinPathExtraData *extra,
1352{
1353 JoinCostWorkspace workspace;
1354
1355 /*
1356 * If the inner path is parameterized, we can't use a partial hashjoin.
1357 * Parameterized partial paths are not supported. The caller should
1358 * already have verified that no lateral rels are required here.
1359 */
1363 return;
1364
1365 /*
1366 * Before creating a path, get a quick lower bound on what it is likely to
1367 * cost. Bail out right away if it looks terrible.
1368 */
1373 return;
1374
1375 /* Might be good enough to be worth trying, so let's try it. */
1378 joinrel,
1379 jointype,
1380 &workspace,
1381 extra,
1382 outer_path,
1383 inner_path,
1384 parallel_hash,
1385 extra->restrictlist,
1386 NULL,
1387 hashclauses));
1388}
1389
1390/*
1391 * sort_inner_and_outer
1392 * Create mergejoin join paths by explicitly sorting both the outer and
1393 * inner join relations on each available merge ordering.
1394 *
1395 * 'joinrel' is the join relation
1396 * 'outerrel' is the outer join relation
1397 * 'innerrel' is the inner join relation
1398 * 'jointype' is the type of join to do
1399 * 'extra' contains additional input values
1400 */
1401static void
1403 RelOptInfo *joinrel,
1404 RelOptInfo *outerrel,
1405 RelOptInfo *innerrel,
1406 JoinType jointype,
1407 JoinPathExtraData *extra)
1408{
1414 ListCell *l;
1415
1416 /* Nothing to do if there are no available mergejoin clauses */
1418 return;
1419
1420 /*
1421 * We only consider the cheapest-total-cost input paths, since we are
1422 * assuming here that a sort is required. We will consider
1423 * cheapest-startup-cost input paths later, and only if they don't need a
1424 * sort.
1425 *
1426 * This function intentionally does not consider parameterized input
1427 * paths, except when the cheapest-total is parameterized. If we did so,
1428 * we'd have a combinatorial explosion of mergejoin paths of dubious
1429 * value. This interacts with decisions elsewhere that also discriminate
1430 * against mergejoins with parameterized inputs; see comments in
1431 * src/backend/optimizer/README.
1432 */
1435
1436 /*
1437 * If either cheapest-total path is parameterized by the other rel, we
1438 * can't use a mergejoin. (There's no use looking for alternative input
1439 * paths, since these should already be the least-parameterized available
1440 * paths.)
1441 */
1444 return;
1445
1446 /*
1447 * If the joinrel is parallel-safe, we may be able to consider a partial
1448 * merge join. However, we can't handle JOIN_FULL, JOIN_RIGHT and
1449 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1450 * Also, the resulting path must not be parameterized.
1451 */
1453 jointype != JOIN_FULL &&
1454 jointype != JOIN_RIGHT &&
1455 jointype != JOIN_RIGHT_ANTI &&
1458 {
1460
1463 else
1464 cheapest_safe_inner =
1466 }
1467
1468 /*
1469 * Each possible ordering of the available mergejoin clauses will generate
1470 * a differently-sorted result path at essentially the same cost. We have
1471 * no basis for choosing one over another at this level of joining, but
1472 * some sort orders may be more useful than others for higher-level
1473 * mergejoins, so it's worth considering multiple orderings.
1474 *
1475 * Actually, it's not quite true that every mergeclause ordering will
1476 * generate a different path order, because some of the clauses may be
1477 * partially redundant (refer to the same EquivalenceClasses). Therefore,
1478 * what we do is convert the mergeclause list to a list of canonical
1479 * pathkeys, and then consider different orderings of the pathkeys.
1480 *
1481 * Generating a path for *every* permutation of the pathkeys doesn't seem
1482 * like a winning strategy; the cost in planning time is too high. For
1483 * now, we generate one path for each pathkey, listing that pathkey first
1484 * and the rest in random order. This should allow at least a one-clause
1485 * mergejoin without re-sorting against any other possible mergejoin
1486 * partner path. But if we've not guessed the right ordering of secondary
1487 * keys, we may end up evaluating clauses as qpquals when they could have
1488 * been done as mergeclauses. (In practice, it's rare that there's more
1489 * than two or three mergeclauses, so expending a huge amount of thought
1490 * on that is probably not worth it.)
1491 *
1492 * The pathkey order returned by select_outer_pathkeys_for_merge() has
1493 * some heuristics behind it (see that function), so be sure to try it
1494 * exactly as-is as well as making variants.
1495 */
1497 extra->mergeclause_list,
1498 joinrel);
1499
1501 {
1507
1508 /* Make a pathkey list with this guy first */
1512 foreach_current_index(l)));
1513 else
1515
1516 /* Sort the mergeclauses into the corresponding ordering */
1517 cur_mergeclauses =
1519 outerkeys,
1520 extra->mergeclause_list);
1521
1522 /* Should have used them all... */
1524
1525 /* Build sort pathkeys for the inner side */
1527 cur_mergeclauses,
1528 outerkeys);
1529
1530 /* Build pathkeys representing output sort order */
1532 outerkeys);
1533
1534 /*
1535 * And now we can make the path.
1536 *
1537 * Note: it's possible that the cheapest paths will already be sorted
1538 * properly. try_mergejoin_path will detect that case and suppress an
1539 * explicit sort step, so we needn't do so here.
1540 */
1542 joinrel,
1543 outer_path,
1544 inner_path,
1545 merge_pathkeys,
1546 cur_mergeclauses,
1547 outerkeys,
1548 innerkeys,
1549 jointype,
1550 extra,
1551 false);
1552
1553 /*
1554 * If we have partial outer and parallel safe inner path then try
1555 * partial mergejoin path.
1556 */
1559 joinrel,
1560 cheapest_partial_outer,
1561 cheapest_safe_inner,
1562 merge_pathkeys,
1563 cur_mergeclauses,
1564 outerkeys,
1565 innerkeys,
1566 jointype,
1567 extra);
1568 }
1569}
1570
1571/*
1572 * generate_mergejoin_paths
1573 * Creates possible mergejoin paths for input outerpath.
1574 *
1575 * We generate mergejoins if mergejoin clauses are available. We have
1576 * two ways to generate the inner path for a mergejoin: sort the cheapest
1577 * inner path, or use an inner path that is already suitably ordered for the
1578 * merge. If we have several mergeclauses, it could be that there is no inner
1579 * path (or only a very expensive one) for the full list of mergeclauses, but
1580 * better paths exist if we truncate the mergeclause list (thereby discarding
1581 * some sort key requirements). So, we consider truncations of the
1582 * mergeclause list as well as the full list. (Ideally we'd consider all
1583 * subsets of the mergeclause list, but that seems way too expensive.)
1584 */
1585static void
1587 RelOptInfo *joinrel,
1588 RelOptInfo *innerrel,
1590 JoinType jointype,
1591 JoinPathExtraData *extra,
1596{
1597 List *mergeclauses;
1598 List *innersortkeys;
1604
1605 /* Look for useful mergeclauses (if any) */
1606 mergeclauses =
1608 outerpath->pathkeys,
1609 extra->mergeclause_list);
1610
1611 /*
1612 * Done with this outer path if no chance for a mergejoin.
1613 *
1614 * Special corner case: for "x FULL JOIN y ON true", there will be no join
1615 * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1616 * but since mergejoin is our only join type that supports FULL JOIN
1617 * without any join clauses, it's necessary to generate a clauseless
1618 * mergejoin path instead.
1619 */
1621 {
1623 /* okay to try for mergejoin */ ;
1624 else
1625 return;
1626 }
1629 return;
1630
1631 /* Compute the required ordering of the inner path */
1633 mergeclauses,
1634 outerpath->pathkeys);
1635
1636 /*
1637 * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1638 * a sort will be needed, only cheapest total cost matters. (But
1639 * try_mergejoin_path will do the right thing if inner_cheapest_total is
1640 * already correctly sorted.)
1641 */
1643 joinrel,
1644 outerpath,
1645 inner_cheapest_total,
1646 merge_pathkeys,
1647 mergeclauses,
1648 NIL,
1649 innersortkeys,
1650 jointype,
1651 extra,
1652 is_partial);
1653
1654 /*
1655 * Look for presorted inner paths that satisfy the innersortkey list ---
1656 * or any truncation thereof, if we are allowed to build a mergejoin using
1657 * a subset of the merge clauses. Here, we consider both cheap startup
1658 * cost and cheap total cost.
1659 *
1660 * Currently we do not consider parameterized inner paths here. This
1661 * interacts with decisions elsewhere that also discriminate against
1662 * mergejoins with parameterized inputs; see comments in
1663 * src/backend/optimizer/README.
1664 *
1665 * As we shorten the sortkey list, we should consider only paths that are
1666 * strictly cheaper than (in particular, not the same as) any path found
1667 * in an earlier iteration. Otherwise we'd be intentionally using fewer
1668 * merge keys than a given path allows (treating the rest as plain
1669 * joinquals), which is unlikely to be a good idea. Also, eliminating
1670 * paths here on the basis of compare_path_costs is a lot cheaper than
1671 * building the mergejoin path only to throw it away.
1672 *
1673 * If inner_cheapest_total is well enough sorted to have not required a
1674 * sort in the path made above, we shouldn't make a duplicate path with
1675 * it, either. We handle that case with the same logic that handles the
1676 * previous consideration, by initializing the variables that track
1677 * cheapest-so-far properly. Note that we do NOT reject
1678 * inner_cheapest_total if we find it matches some shorter set of
1679 * pathkeys. That case corresponds to using fewer mergekeys to avoid
1680 * sorting inner_cheapest_total, whereas we did sort it above, so the
1681 * plans being considered are different.
1682 */
1684 inner_cheapest_total->pathkeys))
1685 {
1686 /* inner_cheapest_total didn't require a sort */
1689 }
1690 else
1691 {
1692 /* it did require a sort, at least for the full set of keys */
1695 }
1699 else
1701
1703 {
1706
1707 /*
1708 * Look for an inner path ordered well enough for the first
1709 * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1710 * destructively, which is why we made a copy...
1711 */
1714 trialsortkeys,
1715 NULL,
1716 TOTAL_COST,
1717 is_partial);
1721 TOTAL_COST) < 0))
1722 {
1723 /* Found a cheap (or even-cheaper) sorted path */
1724 /* Select the right mergeclauses, if we didn't already */
1726 {
1727 newclauses =
1729 mergeclauses,
1730 trialsortkeys);
1732 }
1733 else
1734 newclauses = mergeclauses;
1736 joinrel,
1737 outerpath,
1738 innerpath,
1739 merge_pathkeys,
1740 newclauses,
1741 NIL,
1742 NIL,
1743 jointype,
1744 extra,
1745 is_partial);
1747 }
1748 /* Same on the basis of cheapest startup cost ... */
1750 trialsortkeys,
1751 NULL,
1752 STARTUP_COST,
1753 is_partial);
1757 STARTUP_COST) < 0))
1758 {
1759 /* Found a cheap (or even-cheaper) sorted path */
1761 {
1762 /*
1763 * Avoid rebuilding clause list if we already made one; saves
1764 * memory in big join trees...
1765 */
1767 {
1769 {
1770 newclauses =
1772 mergeclauses,
1773 trialsortkeys);
1775 }
1776 else
1777 newclauses = mergeclauses;
1778 }
1780 joinrel,
1781 outerpath,
1782 innerpath,
1783 merge_pathkeys,
1784 newclauses,
1785 NIL,
1786 NIL,
1787 jointype,
1788 extra,
1789 is_partial);
1790 }
1792 }
1793
1794 /*
1795 * Don't consider truncated sortkeys if we need all clauses.
1796 */
1798 break;
1799 }
1800}
1801
1802/*
1803 * match_unsorted_outer
1804 * Creates possible join paths for processing a single join relation
1805 * 'joinrel' by employing either iterative substitution or
1806 * mergejoining on each of its possible outer paths (considering
1807 * only outer paths that are already ordered well enough for merging).
1808 *
1809 * We always generate a nestloop path for each available outer path.
1810 * In fact we may generate as many as five: one on the cheapest-total-cost
1811 * inner path, one on the same with materialization, one on the
1812 * cheapest-startup-cost inner path (if different), one on the
1813 * cheapest-total inner-indexscan path (if any), and one on the
1814 * cheapest-startup inner-indexscan path (if different).
1815 *
1816 * We also consider mergejoins if mergejoin clauses are available. See
1817 * detailed comments in generate_mergejoin_paths.
1818 *
1819 * 'joinrel' is the join relation
1820 * 'outerrel' is the outer join relation
1821 * 'innerrel' is the inner join relation
1822 * 'jointype' is the type of join to do
1823 * 'extra' contains additional input values
1824 */
1825static void
1827 RelOptInfo *joinrel,
1828 RelOptInfo *outerrel,
1829 RelOptInfo *innerrel,
1830 JoinType jointype,
1831 JoinPathExtraData *extra)
1832{
1838
1839 /*
1840 * For now we do not support RIGHT_SEMI join in mergejoin or nestloop
1841 * join.
1842 */
1844 return;
1845
1846 /*
1847 * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1848 * are doing a right, right-anti or full mergejoin, we must use *all* the
1849 * mergeclauses as join clauses, else we will not have a valid plan.
1850 * (Although these two flags are currently inverses, keep them separate
1851 * for clarity and possible future changes.)
1852 */
1853 switch (jointype)
1854 {
1861 break;
1867 break;
1868 default:
1870 (int) jointype);
1873 break;
1874 }
1875
1876 /*
1877 * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1878 * we will consider it below as a member of cheapest_parameterized_paths,
1879 * but the other possibilities considered in this routine aren't usable.
1880 *
1881 * Furthermore, if the inner side is a unique-ified relation, we cannot
1882 * generate any valid paths here, because the inner rel's dependency on
1883 * the outer rel makes unique-ification meaningless.
1884 */
1886 {
1888
1890 return;
1891 }
1892
1894 {
1895 /*
1896 * Consider materializing the cheapest inner path, unless that is
1897 * disabled or the path in question materializes its output anyway.
1898 */
1904 }
1905
1907 {
1910
1911 /*
1912 * We cannot use an outer path that is parameterized by the inner rel.
1913 */
1915 continue;
1916
1917 /*
1918 * The result will have this sort order (even if it is implemented as
1919 * a nestloop, and even if some of the mergeclauses are implemented by
1920 * qpquals rather than as true mergeclauses):
1921 */
1923 outerpath->pathkeys);
1924
1926 {
1927 /*
1928 * Consider nestloop joins using this outer path and various
1929 * available paths for the inner relation. We consider the
1930 * cheapest-total paths for each available parameterization of the
1931 * inner relation, including the unparameterized case.
1932 */
1934
1936 {
1939
1941 joinrel,
1942 outerpath,
1943 innerpath,
1944 merge_pathkeys,
1945 jointype,
1946 PGS_NESTLOOP_PLAIN,
1947 extra);
1948
1949 /*
1950 * Try generating a memoize path and see if that makes the
1951 * nested loop any cheaper.
1952 */
1955 extra);
1958 joinrel,
1959 outerpath,
1960 mpath,
1961 merge_pathkeys,
1962 jointype,
1963 PGS_NESTLOOP_MEMOIZE,
1964 extra);
1965 }
1966
1967 /* Also consider materialized form of the cheapest inner path */
1970 joinrel,
1971 outerpath,
1972 matpath,
1973 merge_pathkeys,
1974 jointype,
1975 PGS_NESTLOOP_MATERIALIZE,
1976 extra);
1977 }
1978
1979 /* Can't do anything else if inner rel is parameterized by outer */
1981 continue;
1982
1983 /* Generate merge join paths */
1985 jointype, extra, useallclauses,
1987 false);
1988 }
1989
1990 /*
1991 * Consider partial nestloop and mergejoin plan if outerrel has any
1992 * partial path and the joinrel is parallel-safe. However, we can't
1993 * handle joins needing lateral rels, since partial paths must not be
1994 * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
1995 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1996 */
1998 jointype != JOIN_FULL &&
1999 jointype != JOIN_RIGHT &&
2000 jointype != JOIN_RIGHT_ANTI &&
2003 {
2006 jointype, extra);
2007
2008 /*
2009 * If inner_cheapest_total is NULL or non parallel-safe then find the
2010 * cheapest total parallel safe path.
2011 */
2013 !inner_cheapest_total->parallel_safe)
2014 {
2015 inner_cheapest_total =
2017 }
2018
2021 jointype, extra,
2022 inner_cheapest_total);
2023 }
2024}
2025
2026/*
2027 * consider_parallel_mergejoin
2028 * Try to build partial paths for a joinrel by joining a partial path
2029 * for the outer relation to a complete path for the inner relation.
2030 *
2031 * 'joinrel' is the join relation
2032 * 'outerrel' is the outer join relation
2033 * 'innerrel' is the inner join relation
2034 * 'jointype' is the type of join to do
2035 * 'extra' contains additional input values
2036 * 'inner_cheapest_total' cheapest total path for innerrel
2037 */
2038static void
2040 RelOptInfo *joinrel,
2041 RelOptInfo *outerrel,
2042 RelOptInfo *innerrel,
2043 JoinType jointype,
2044 JoinPathExtraData *extra,
2046{
2048
2049 /* generate merge join path for each partial outer path */
2051 {
2054
2055 /*
2056 * Figure out what useful ordering any paths we create will have.
2057 */
2059 outerpath->pathkeys);
2060
2064 }
2065}
2066
2067/*
2068 * consider_parallel_nestloop
2069 * Try to build partial paths for a joinrel by joining a partial path for the
2070 * outer relation to a complete path for the inner relation.
2071 *
2072 * 'joinrel' is the join relation
2073 * 'outerrel' is the outer join relation
2074 * 'innerrel' is the inner join relation
2075 * 'jointype' is the type of join to do
2076 * 'extra' contains additional input values
2077 */
2078static void
2080 RelOptInfo *joinrel,
2081 RelOptInfo *outerrel,
2082 RelOptInfo *innerrel,
2083 JoinType jointype,
2084 JoinPathExtraData *extra)
2085{
2089
2090 /*
2091 * Consider materializing the cheapest inner path, unless: 1)
2092 * materialization is disabled here, 2) the cheapest inner path is not
2093 * parallel-safe, 3) the cheapest inner path is parameterized by the outer
2094 * rel, or 4) the cheapest inner path materializes its output anyway.
2095 */
2097 inner_cheapest_total->parallel_safe &&
2100 {
2104 }
2105
2107 {
2109 List *pathkeys;
2111
2112 /* Figure out what useful ordering any paths we create will have. */
2114 outerpath->pathkeys);
2115
2116 /*
2117 * Try the cheapest parameterized paths; only those which will produce
2118 * an unparameterized path when joined to this outerrel will survive
2119 * try_partial_nestloop_path. The cheapest unparameterized path is
2120 * also in this list.
2121 */
2123 {
2126
2127 /* Can't join to an inner path that is not parallel-safe */
2129 continue;
2130
2132 pathkeys, jointype,
2133 PGS_NESTLOOP_PLAIN, extra);
2134
2135 /*
2136 * Try generating a memoize path and see if that makes the nested
2137 * loop any cheaper.
2138 */
2141 extra);
2144 pathkeys, jointype,
2145 PGS_NESTLOOP_MEMOIZE, extra);
2146 }
2147
2148 /* Also consider materialized form of the cheapest inner path */
2151 pathkeys, jointype,
2152 PGS_NESTLOOP_MATERIALIZE, extra);
2153 }
2154}
2155
2156/*
2157 * hash_inner_and_outer
2158 * Create hashjoin join paths by explicitly hashing both the outer and
2159 * inner keys of each available hash clause.
2160 *
2161 * 'joinrel' is the join relation
2162 * 'outerrel' is the outer join relation
2163 * 'innerrel' is the inner join relation
2164 * 'jointype' is the type of join to do
2165 * 'extra' contains additional input values
2166 */
2167static void
2169 RelOptInfo *joinrel,
2170 RelOptInfo *outerrel,
2171 RelOptInfo *innerrel,
2172 JoinType jointype,
2173 JoinPathExtraData *extra)
2174{
2176 List *hashclauses;
2177 ListCell *l;
2178
2179 /*
2180 * We need to build only one hashclauses list for any given pair of outer
2181 * and inner relations; all of the hashable clauses will be used as keys.
2182 *
2183 * Scan the join's restrictinfo list to find hashjoinable clauses that are
2184 * usable with this pair of sub-relations.
2185 */
2186 hashclauses = NIL;
2188 {
2190
2191 /*
2192 * If processing an outer join, only use its own join clauses for
2193 * hashing. For inner joins we need not be so picky.
2194 */
2196 continue;
2197
2200 continue; /* not hashjoinable */
2201
2202 /*
2203 * Check if clause has the form "outer op inner" or "inner op outer".
2204 */
2206 innerrel->relids))
2207 continue; /* no good for these input relations */
2208
2209 /*
2210 * If clause has the form "inner op outer", check if its operator has
2211 * valid commutator. This is necessary because hashclauses in this
2212 * form will get commuted in createplan.c to put the outer var on the
2213 * left (see get_switched_clauses). This probably shouldn't ever
2214 * fail, since hashable operators ought to have commutators, but be
2215 * paranoid.
2216 *
2217 * The clause being hashjoinable indicates that it's an OpExpr.
2218 */
2221 continue;
2222
2224 }
2225
2226 /* If we found any usable hashclauses, make paths */
2227 if (hashclauses)
2228 {
2229 /*
2230 * We consider both the cheapest-total-cost and cheapest-startup-cost
2231 * outer paths. There's no need to consider any but the
2232 * cheapest-total-cost inner path, however.
2233 */
2239
2240 /*
2241 * If either cheapest-total path is parameterized by the other rel, we
2242 * can't use a hashjoin. (There's no use looking for alternative
2243 * input paths, since these should already be the least-parameterized
2244 * available paths.)
2245 */
2248 return;
2249
2250 /*
2251 * Consider the cheapest startup outer together with the cheapest
2252 * total inner, and then consider pairings of cheapest-total paths
2253 * including parameterized ones. There is no use in generating
2254 * parameterized paths on the basis of possibly cheap startup cost, so
2255 * this is sufficient.
2256 */
2259 joinrel,
2260 cheapest_startup_outer,
2261 cheapest_total_inner,
2262 hashclauses,
2263 jointype,
2264 extra);
2265
2267 {
2269
2270 /*
2271 * We cannot use an outer path that is parameterized by the inner
2272 * rel.
2273 */
2275 continue;
2276
2278 {
2280
2281 /*
2282 * We cannot use an inner path that is parameterized by the
2283 * outer rel, either.
2284 */
2286 continue;
2287
2290 continue; /* already tried it */
2291
2293 joinrel,
2294 outerpath,
2295 innerpath,
2296 hashclauses,
2297 jointype,
2298 extra);
2299 }
2300 }
2301
2302 /*
2303 * If the joinrel is parallel-safe, we may be able to consider a
2304 * partial hash join.
2305 *
2306 * However, we can't handle JOIN_RIGHT_SEMI, because the hash table is
2307 * either a shared hash table or a private hash table per backend. In
2308 * the shared case, there is no concurrency protection for the match
2309 * flags, so multiple workers could inspect and set the flags
2310 * concurrently, potentially producing incorrect results. In the
2311 * private case, each worker has its own copy of the hash table, so no
2312 * single process has all the match flags.
2313 *
2314 * Also, the resulting path must not be parameterized.
2315 */
2317 jointype != JOIN_RIGHT_SEMI &&
2320 {
2324
2325 cheapest_partial_outer =
2327
2328 /*
2329 * Can we use a partial inner plan too, so that we can build a
2330 * shared hash table in parallel?
2331 */
2333 enable_parallel_hash)
2334 {
2335 cheapest_partial_inner =
2338 cheapest_partial_outer,
2339 cheapest_partial_inner,
2340 hashclauses, jointype, extra,
2341 true /* parallel_hash */ );
2342 }
2343
2344 /*
2345 * Normally, given that the joinrel is parallel-safe, the cheapest
2346 * total inner path will also be parallel-safe, but if not, we'll
2347 * have to search for the cheapest safe, unparameterized inner
2348 * path. If full, right, or right-anti join, we can't use
2349 * parallelism (building the hash table in each backend) because
2350 * no one process has all the match bits.
2351 */
2353 jointype == JOIN_RIGHT ||
2354 jointype == JOIN_RIGHT_ANTI)
2358 else
2359 cheapest_safe_inner =
2361
2364 cheapest_partial_outer,
2365 cheapest_safe_inner,
2366 hashclauses, jointype, extra,
2367 false /* parallel_hash */ );
2368 }
2369 }
2370}
2371
2372/*
2373 * select_mergejoin_clauses
2374 * Select mergejoin clauses that are usable for a particular join.
2375 * Returns a list of RestrictInfo nodes for those clauses.
2376 *
2377 * *mergejoin_allowed is normally set to true, but it is set to false if
2378 * this is a right-semi join, or this is a right/right-anti/full join and
2379 * there are nonmergejoinable join clauses. The executor's mergejoin
2380 * machinery cannot handle such cases, so we have to avoid generating a
2381 * mergejoin plan. (Note that this flag does NOT consider whether there are
2382 * actually any mergejoinable clauses. This is correct because in some
2383 * cases we need to build a clauseless mergejoin. Simply returning NIL is
2384 * therefore not enough to distinguish safe from unsafe cases.)
2385 *
2386 * We also mark each selected RestrictInfo to show which side is currently
2387 * being considered as outer. These are transient markings that are only
2388 * good for the duration of the current add_paths_to_joinrel() call!
2389 *
2390 * We examine each restrictinfo clause known for the join to see
2391 * if it is mergejoinable and involves vars from the two sub-relations
2392 * currently of interest.
2393 */
2396 RelOptInfo *joinrel,
2397 RelOptInfo *outerrel,
2398 RelOptInfo *innerrel,
2399 List *restrictlist,
2400 JoinType jointype,
2402{
2406 ListCell *l;
2407
2408 /*
2409 * For now we do not support RIGHT_SEMI join in mergejoin: the benefit of
2410 * swapping inputs tends to be small here.
2411 */
2413 {
2416 }
2417
2418 foreach(l, restrictlist)
2419 {
2421
2422 /*
2423 * If processing an outer join, only use its own join clauses in the
2424 * merge. For inner joins we can use pushed-down clauses too. (Note:
2425 * we don't set have_nonmergeable_joinclause here because pushed-down
2426 * clauses will become otherquals not joinquals.)
2427 */
2429 continue;
2430
2431 /* Check that clause is a mergeable operator clause */
2434 {
2435 /*
2436 * The executor can handle extra joinquals that are constants, but
2437 * not anything else, when doing right/right-anti/full merge join.
2438 * (The reason to support constants is so we can do FULL JOIN ON
2439 * FALSE.)
2440 */
2443 continue; /* not mergejoinable */
2444 }
2445
2446 /*
2447 * Check if clause has the form "outer op inner" or "inner op outer".
2448 */
2450 innerrel->relids))
2451 {
2453 continue; /* no good for these input relations */
2454 }
2455
2456 /*
2457 * If clause has the form "inner op outer", check if its operator has
2458 * valid commutator. This is necessary because mergejoin clauses in
2459 * this form will get commuted in createplan.c to put the outer var on
2460 * the left (see get_switched_clauses). This probably shouldn't ever
2461 * fail, since mergejoinable operators ought to have commutators, but
2462 * be paranoid.
2463 *
2464 * The clause being mergejoinable indicates that it's an OpExpr.
2465 */
2468 {
2470 continue;
2471 }
2472
2473 /*
2474 * Insist that each side have a non-redundant eclass. This
2475 * restriction is needed because various bits of the planner expect
2476 * that each clause in a merge be associable with some pathkey in a
2477 * canonical pathkey list, but redundant eclasses can't appear in
2478 * canonical sort orderings. (XXX it might be worth relaxing this,
2479 * but not enough time to address it for 8.3.)
2480 */
2482
2485 {
2487 continue; /* can't handle redundant eclasses */
2488 }
2489
2491 }
2492
2493 /*
2494 * Report whether mergejoin is allowed (see comment at top of function).
2495 */
2496 switch (jointype)
2497 {
2502 break;
2503 default:
2505 break;
2506 }
2507
2509}
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition analyzejoins.c:1310
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:346
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:292
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:916
bool bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
Definition bitmapset.c:640
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition costsize.c:5261
void initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, uint64 enable_mask, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
Definition costsize.c:3377
void initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra, bool parallel_hash)
Definition costsize.c:4301
void initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, int outer_presorted_keys, JoinPathExtraData *extra)
Definition costsize.c:3662
static void try_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra)
Definition joinpath.c:1267
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition joinpath.c:2395
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition joinpath.c:1402
static List * extract_lateral_vars_from_PHVs(PlannerInfo *root, Relids innerrelids)
Definition joinpath.c:621
static bool paraminfo_get_equal_hashops(PlannerInfo *root, ParamPathInfo *param_info, RelOptInfo *outerrel, RelOptInfo *innerrel, List *ph_lateral_vars, List **param_exprs, List **operators, bool *binary_mode)
Definition joinpath.c:476
static Path * get_memoize_path(PlannerInfo *root, RelOptInfo *innerrel, RelOptInfo *outerrel, Path *inner_path, Path *outer_path, JoinType jointype, JoinPathExtraData *extra)
Definition joinpath.c:712
static void consider_parallel_nestloop(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition joinpath.c:2079
static void try_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, uint64 nestloop_subtype, JoinPathExtraData *extra)
Definition joinpath.c:873
static void try_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra, bool is_partial)
Definition joinpath.c:1074
static void consider_parallel_mergejoin(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra, Path *inner_cheapest_total)
Definition joinpath.c:2039
static void generate_mergejoin_paths(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *innerrel, Path *outerpath, JoinType jointype, JoinPathExtraData *extra, bool useallclauses, Path *inner_cheapest_total, List *merge_pathkeys, bool is_partial)
Definition joinpath.c:1586
static void try_partial_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, JoinType jointype, uint64 nestloop_subtype, JoinPathExtraData *extra)
Definition joinpath.c:994
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition joinpath.c:2168
static void try_partial_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *pathkeys, List *mergeclauses, List *outersortkeys, List *innersortkeys, JoinType jointype, JoinPathExtraData *extra)
Definition joinpath.c:1190
static bool allow_star_schema_join(PlannerInfo *root, Relids outerrelids, Relids inner_paramrels)
Definition joinpath.c:400
static void try_partial_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, Path *outer_path, Path *inner_path, List *hashclauses, JoinType jointype, JoinPathExtraData *extra, bool parallel_hash)
Definition joinpath.c:1344
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition joinpath.c:1826
Path * get_cheapest_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Definition pathkeys.c:620
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition pathkeys.c:558
List * make_inner_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
Definition pathkeys.c:1858
List * find_mergeclauses_for_outer_pathkeys(PlannerInfo *root, List *pathkeys, List *restrictinfos)
Definition pathkeys.c:1544
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition pathkeys.c:1510
List * trim_mergeclauses_for_inner_pathkeys(PlannerInfo *root, List *mergeclauses, List *pathkeys)
Definition pathkeys.c:1961
List * select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
Definition pathkeys.c:1659
List * build_join_pathkeys(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
Definition pathkeys.c:1295
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition pathkeys.c:699
Relids calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
Definition pathnode.c:2248
bool path_is_reparameterizable_by_child(Path *path, RelOptInfo *child_rel)
Definition pathnode.c:4325
MemoizePath * create_memoize_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *param_exprs, List *hash_operators, bool singlerow, bool binary_mode, Cardinality est_calls)
Definition pathnode.c:1690
MaterialPath * create_material_path(RelOptInfo *rel, Path *subpath, bool enabled)
Definition pathnode.c:1656
Relids calc_nestloop_required_outer(Relids outerrelids, Relids outer_paramrels, Relids innerrelids, Relids inner_paramrels)
Definition pathnode.c:2221
HashPath * create_hashjoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, bool parallel_hash, List *restrict_clauses, Relids required_outer, List *hashclauses)
Definition pathnode.c:2465
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition pathnode.c:793
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition pathnode.c:68
bool add_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost startup_cost, Cost total_cost, List *pathkeys, Relids required_outer)
Definition pathnode.c:686
bool add_partial_path_precheck(RelOptInfo *parent_rel, int disabled_nodes, Cost total_cost, List *pathkeys)
Definition pathnode.c:919
MergePath * create_mergejoin_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer, List *mergeclauses, List *outersortkeys, List *innersortkeys, int outer_presorted_keys)
Definition pathnode.c:2397
NestPath * create_nestloop_path(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, JoinCostWorkspace *workspace, JoinPathExtraData *extra, Path *outer_path, Path *inner_path, List *restrict_clauses, List *pathkeys, Relids required_outer)
Definition pathnode.c:2300
#define RELATION_WAS_MADE_UNIQUE(rel, sjinfo, nominal_jointype)
Definition pathnodes.h:1232
PlaceHolderInfo * find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
Definition placeholder.c:83
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition restrictinfo.h:73
Definition bitmapset.h:50
Definition primnodes.h:324
Definition pathnodes.h:3680
Definition pathnodes.h:3574
Definition pg_list.h:54
Definition nodes.h:135
Definition primnodes.h:846
Definition pathnodes.h:1899
Definition pathnodes.h:1787
Definition pathnodes.h:1945
Definition pathnodes.h:3374
Definition pathnodes.h:3085
Definition pathnodes.h:297
Definition pathnodes.h:992
List * cheapest_parameterized_paths
Definition pathnodes.h:1037
Definition pathnodes.h:2864
Definition pathnodes.h:3191
Definition typcache.h:32
Definition primnodes.h:262
Definition regcomp.c:282
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition typcache.c:386
Definition pg_list.h:46
◆ PATH_PARAM_BY_REL
| #define PATH_PARAM_BY_REL | ( | path, | |
| rel | |||
| ) | (PATH_PARAM_BY_REL_SELF(path, rel) || PATH_PARAM_BY_PARENT(path, rel)) |
Definition at line 45 of file joinpath.c.
◆ PATH_PARAM_BY_REL_SELF
| #define PATH_PARAM_BY_REL_SELF | ( | path, | |
| rel | |||
| ) | ((path)->param_info && bms_overlap(PATH_REQ_OUTER(path), (rel)->relids)) |
Definition at line 42 of file joinpath.c.
Function Documentation
◆ add_paths_to_joinrel()
| void add_paths_to_joinrel | ( | PlannerInfo * | root, |
| RelOptInfo * | joinrel, | ||
| RelOptInfo * | outerrel, | ||
| RelOptInfo * | innerrel, | ||
| JoinType | jointype, | ||
| SpecialJoinInfo * | sjinfo, | ||
| List * | restrictlist | ||
| ) |
Definition at line 123 of file joinpath.c.
130{
132 JoinPathExtraData extra;
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 */
146 else
148
149 extra.restrictlist = restrictlist;
151 extra.sjinfo = sjinfo;
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 */
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 */
200 switch (jointype)
201 {
204 break;
207 outerrel->relids);
208 break;
211 joinrel->relids,
212 outerrel->relids,
213 innerrel,
214 JOIN_INNER,
215 restrictlist,
216 false);
217 break;
218 default:
220 joinrel->relids,
221 outerrel->relids,
222 innerrel,
223 jointype,
224 restrictlist,
225 false);
226 break;
227 }
228
229 /*
230 * If the outer or inner relation has been unique-ified, handle as a plain
231 * inner join.
232 */
234 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 */
244 joinrel,
245 outerrel,
246 innerrel,
247 restrictlist,
248 jointype,
249 &mergejoin_allowed);
250
251 /*
252 * If it's SEMI, ANTI, or inner_unique join, compute correction factors
253 * for cost estimation. These will be the same for all paths.
254 */
257 jointype, sjinfo, restrictlist,
258 &extra.semifactors);
259
260 /*
261 * Decide whether it's sensible to generate parameterized paths for this
262 * joinrel, and if so, which relations such paths should require. There
263 * is usually no need to create a parameterized result path unless there
264 * is a join order restriction that prevents joining one of our input rels
265 * directly to the parameter source rel instead of joining to the other
266 * input rel. (But see allow_star_schema_join().) This restriction
267 * reduces the number of parameterized paths we have to deal with at
268 * higher join levels, without compromising the quality of the resulting
269 * plan. We express the restriction as a Relids set that must overlap the
270 * parameterization of any proposed join path. Note: param_source_rels
271 * should contain only baserels, not OJ relids, so starting from
272 * all_baserels not all_query_rels is correct.
273 */
275 {
277
278 /*
279 * SJ is relevant to this join if we have some part of its RHS
280 * (possibly not all of it), and haven't yet joined to its LHS. (This
281 * test is pretty simplistic, but should be sufficient considering the
282 * join has already been proven legal.) If the SJ is relevant, it
283 * presents constraints for joining to anything not in its RHS.
284 */
289 sjinfo2->min_righthand));
290
291 /* full joins constrain both sides symmetrically */
297 sjinfo2->min_lefthand));
298 }
299
300 /*
301 * However, when a LATERAL subquery is involved, there will simply not be
302 * any paths for the joinrel that aren't parameterized by whatever the
303 * subquery is parameterized by, unless its parameterization is resolved
304 * within the joinrel. So we might as well allow additional dependencies
305 * on whatever residual lateral dependencies the joinrel will have.
306 */
308 joinrel->lateral_relids);
309
310 /*
311 * 1. Consider mergejoin paths where both relations must be explicitly
312 * sorted. Skip this if we can't mergejoin.
313 */
316 jointype, &extra);
317
318 /*
319 * 2. Consider paths where the outer relation need not be explicitly
320 * sorted. This includes both nestloops and mergejoins where the outer
321 * path is already ordered. Again, skip this if we can't mergejoin.
322 * (That's okay because we know that nestloop can't handle
323 * right/right-anti/right-semi/full joins at all, so it wouldn't work in
324 * the prohibited cases either.)
325 */
328 jointype, &extra);
329
330#ifdef NOT_USED
331
332 /*
333 * 3. Consider paths where the inner relation need not be explicitly
334 * sorted. This includes mergejoins only (nestloops were already built in
335 * match_unsorted_outer).
336 *
337 * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
338 * significant difference between the inner and outer side of a mergejoin,
339 * so match_unsorted_inner creates no paths that aren't equivalent to
340 * those made by match_unsorted_outer when add_paths_to_joinrel() is
341 * invoked with the two rels given in the other order.
342 */
345 jointype, &extra);
346#endif
347
348 /*
349 * 4. Consider paths where both outer and inner relations must be hashed
350 * before being joined. As above, when it's a full join, we must try this
351 * even when the path type is disabled, because it may be our only option.
352 */
355 jointype, &extra);
356
357 /*
358 * 5. If inner and outer relations are foreign tables (or joins) belonging
359 * to the same server and assigned to the same user to check access
360 * permissions as, give the FDW a chance to push down joins.
361 */
363 joinrel->fdwroutine->GetForeignJoinPaths)
364 joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
365 outerrel, innerrel,
366 save_jointype, &extra);
367
368 /*
369 * 6. Finally, give extensions a chance to manipulate the path list. They
370 * could add new paths (such as CustomPaths) by calling add_path(), or
371 * add_partial_path() if parallel aware.
372 *
373 * In theory, extensions could also use this hook to delete or modify
374 * paths added by the core code, but in practice this is difficult to make
375 * work, since it's too late to get back any paths that have already been
376 * discarded by add_path() or add_partial_path(). If you're trying to
377 * suppress paths, consider using join_path_setup_hook instead.
378 */
381 save_jointype, &extra);
382}
References bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), fb(), hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, join_path_setup_hook, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, NIL, JoinPathExtraData::param_source_rels, PGS_FOREIGNJOIN, PGS_HASHJOIN, RelOptInfo::pgs_mask, JoinPathExtraData::pgs_mask, PGS_MERGEJOIN_ANY, RelOptInfo::relids, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, JoinPathExtraData::restrictlist, root, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, sort_inner_and_outer(), and RelOptInfo::top_parent_relids.
Referenced by populate_joinrel_with_paths().
◆ allow_star_schema_join()
|
inlinestatic |
Definition at line 400 of file joinpath.c.
403{
404 /*
405 * It's a star-schema case if the outer rel provides some but not all of
406 * the inner rel's parameterization.
407 */
410}
References bms_nonempty_difference(), bms_overlap(), and fb().
Referenced by try_nestloop_path().
◆ consider_parallel_mergejoin()
|
static |
Definition at line 2039 of file joinpath.c.
2046{
2048
2049 /* generate merge join path for each partial outer path */
2051 {
2054
2055 /*
2056 * Figure out what useful ordering any paths we create will have.
2057 */
2059 outerpath->pathkeys);
2060
2064 }
2065}
References build_join_pathkeys(), fb(), generate_mergejoin_paths(), lfirst, RelOptInfo::partial_pathlist, and root.
Referenced by match_unsorted_outer().
◆ consider_parallel_nestloop()
|
static |
Definition at line 2079 of file joinpath.c.
2085{
2089
2090 /*
2091 * Consider materializing the cheapest inner path, unless: 1)
2092 * materialization is disabled here, 2) the cheapest inner path is not
2093 * parallel-safe, 3) the cheapest inner path is parameterized by the outer
2094 * rel, or 4) the cheapest inner path materializes its output anyway.
2095 */
2097 inner_cheapest_total->parallel_safe &&
2100 {
2104 }
2105
2107 {
2109 List *pathkeys;
2111
2112 /* Figure out what useful ordering any paths we create will have. */
2114 outerpath->pathkeys);
2115
2116 /*
2117 * Try the cheapest parameterized paths; only those which will produce
2118 * an unparameterized path when joined to this outerrel will survive
2119 * try_partial_nestloop_path. The cheapest unparameterized path is
2120 * also in this list.
2121 */
2123 {
2126
2127 /* Can't join to an inner path that is not parallel-safe */
2129 continue;
2130
2132 pathkeys, jointype,
2133 PGS_NESTLOOP_PLAIN, extra);
2134
2135 /*
2136 * Try generating a memoize path and see if that makes the nested
2137 * loop any cheaper.
2138 */
2141 extra);
2144 pathkeys, jointype,
2145 PGS_NESTLOOP_MEMOIZE, extra);
2146 }
2147
2148 /* Also consider materialized form of the cheapest inner path */
2151 pathkeys, jointype,
2152 PGS_NESTLOOP_MATERIALIZE, extra);
2153 }
2154}
References Assert, build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, create_material_path(), ExecMaterializesOutput(), fb(), get_memoize_path(), lfirst, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, JoinPathExtraData::pgs_mask, PGS_NESTLOOP_MATERIALIZE, PGS_NESTLOOP_MEMOIZE, PGS_NESTLOOP_PLAIN, root, and try_partial_nestloop_path().
Referenced by match_unsorted_outer().
◆ extract_lateral_vars_from_PHVs()
|
static |
Definition at line 621 of file joinpath.c.
622{
625
626 /* Nothing would be found if the query contains no LATERAL RTEs */
629
630 /*
631 * No need to consider PHVs that are due to be evaluated at joinrels,
632 * since we do not add Memoize nodes on top of joinrel paths.
633 */
636
638 {
641 ListCell *cell;
642
643 /* PHV is uninteresting if no lateral refs */
645 continue;
646
647 /* PHV is uninteresting if not due to be evaluated at innerrelids */
649 continue;
650
651 /*
652 * If the PHV does not reference any rels in innerrelids, use its
653 * contained expression as a cache key rather than extracting the
654 * Vars/PHVs from it and using those. This can be beneficial in cases
655 * where the expression results in fewer distinct values to cache
656 * tuples for.
657 */
659 innerrelids))
660 {
662 continue;
663 }
664
665 /* Fetch Vars and PHVs of lateral references within PlaceHolderVars */
668 {
670
672 {
674
676
679 }
681 {
683
685
689 }
690 else
692 }
693
695 }
696
698}
References Assert, bms_equal(), bms_is_member(), bms_is_subset(), bms_membership(), BMS_MULTIPLE, bms_overlap(), fb(), find_placeholder_info(), IsA, lappend(), lfirst, list_free(), NIL, PlaceHolderInfo::ph_lateral, pull_varnos(), pull_vars_of_level(), root, Var::varlevelsup, and Var::varno.
Referenced by get_memoize_path().
◆ generate_mergejoin_paths()
|
static |
Definition at line 1586 of file joinpath.c.
1596{
1597 List *mergeclauses;
1598 List *innersortkeys;
1604
1605 /* Look for useful mergeclauses (if any) */
1606 mergeclauses =
1608 outerpath->pathkeys,
1609 extra->mergeclause_list);
1610
1611 /*
1612 * Done with this outer path if no chance for a mergejoin.
1613 *
1614 * Special corner case: for "x FULL JOIN y ON true", there will be no join
1615 * clauses at all. Ordinarily we'd generate a clauseless nestloop path,
1616 * but since mergejoin is our only join type that supports FULL JOIN
1617 * without any join clauses, it's necessary to generate a clauseless
1618 * mergejoin path instead.
1619 */
1621 {
1623 /* okay to try for mergejoin */ ;
1624 else
1625 return;
1626 }
1629 return;
1630
1631 /* Compute the required ordering of the inner path */
1633 mergeclauses,
1634 outerpath->pathkeys);
1635
1636 /*
1637 * Generate a mergejoin on the basis of sorting the cheapest inner. Since
1638 * a sort will be needed, only cheapest total cost matters. (But
1639 * try_mergejoin_path will do the right thing if inner_cheapest_total is
1640 * already correctly sorted.)
1641 */
1643 joinrel,
1644 outerpath,
1645 inner_cheapest_total,
1646 merge_pathkeys,
1647 mergeclauses,
1648 NIL,
1649 innersortkeys,
1650 jointype,
1651 extra,
1652 is_partial);
1653
1654 /*
1655 * Look for presorted inner paths that satisfy the innersortkey list ---
1656 * or any truncation thereof, if we are allowed to build a mergejoin using
1657 * a subset of the merge clauses. Here, we consider both cheap startup
1658 * cost and cheap total cost.
1659 *
1660 * Currently we do not consider parameterized inner paths here. This
1661 * interacts with decisions elsewhere that also discriminate against
1662 * mergejoins with parameterized inputs; see comments in
1663 * src/backend/optimizer/README.
1664 *
1665 * As we shorten the sortkey list, we should consider only paths that are
1666 * strictly cheaper than (in particular, not the same as) any path found
1667 * in an earlier iteration. Otherwise we'd be intentionally using fewer
1668 * merge keys than a given path allows (treating the rest as plain
1669 * joinquals), which is unlikely to be a good idea. Also, eliminating
1670 * paths here on the basis of compare_path_costs is a lot cheaper than
1671 * building the mergejoin path only to throw it away.
1672 *
1673 * If inner_cheapest_total is well enough sorted to have not required a
1674 * sort in the path made above, we shouldn't make a duplicate path with
1675 * it, either. We handle that case with the same logic that handles the
1676 * previous consideration, by initializing the variables that track
1677 * cheapest-so-far properly. Note that we do NOT reject
1678 * inner_cheapest_total if we find it matches some shorter set of
1679 * pathkeys. That case corresponds to using fewer mergekeys to avoid
1680 * sorting inner_cheapest_total, whereas we did sort it above, so the
1681 * plans being considered are different.
1682 */
1684 inner_cheapest_total->pathkeys))
1685 {
1686 /* inner_cheapest_total didn't require a sort */
1689 }
1690 else
1691 {
1692 /* it did require a sort, at least for the full set of keys */
1695 }
1699 else
1701
1703 {
1706
1707 /*
1708 * Look for an inner path ordered well enough for the first
1709 * 'sortkeycnt' innersortkeys. NB: trialsortkeys list is modified
1710 * destructively, which is why we made a copy...
1711 */
1714 trialsortkeys,
1715 NULL,
1716 TOTAL_COST,
1717 is_partial);
1721 TOTAL_COST) < 0))
1722 {
1723 /* Found a cheap (or even-cheaper) sorted path */
1724 /* Select the right mergeclauses, if we didn't already */
1726 {
1727 newclauses =
1729 mergeclauses,
1730 trialsortkeys);
1732 }
1733 else
1734 newclauses = mergeclauses;
1736 joinrel,
1737 outerpath,
1738 innerpath,
1739 merge_pathkeys,
1740 newclauses,
1741 NIL,
1742 NIL,
1743 jointype,
1744 extra,
1745 is_partial);
1747 }
1748 /* Same on the basis of cheapest startup cost ... */
1750 trialsortkeys,
1751 NULL,
1752 STARTUP_COST,
1753 is_partial);
1757 STARTUP_COST) < 0))
1758 {
1759 /* Found a cheap (or even-cheaper) sorted path */
1761 {
1762 /*
1763 * Avoid rebuilding clause list if we already made one; saves
1764 * memory in big join trees...
1765 */
1767 {
1769 {
1770 newclauses =
1772 mergeclauses,
1773 trialsortkeys);
1775 }
1776 else
1777 newclauses = mergeclauses;
1778 }
1780 joinrel,
1781 outerpath,
1782 innerpath,
1783 merge_pathkeys,
1784 newclauses,
1785 NIL,
1786 NIL,
1787 jointype,
1788 extra,
1789 is_partial);
1790 }
1792 }
1793
1794 /*
1795 * Don't consider truncated sortkeys if we need all clauses.
1796 */
1798 break;
1799 }
1800}
References Assert, compare_path_costs(), fb(), find_mergeclauses_for_outer_pathkeys(), get_cheapest_path_for_pathkeys(), JOIN_FULL, list_copy(), list_length(), list_truncate(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, pathkeys_contained_in(), RelOptInfo::pathlist, root, STARTUP_COST, TOTAL_COST, trim_mergeclauses_for_inner_pathkeys(), and try_mergejoin_path().
Referenced by consider_parallel_mergejoin(), and match_unsorted_outer().
◆ get_memoize_path()
|
static |
Definition at line 712 of file joinpath.c.
716{
717 List *param_exprs;
718 List *hash_operators;
720 bool binary_mode;
722
723 /* Obviously not if it's disabled */
726
727 /*
728 * We can safely not bother with all this unless we expect to perform more
729 * than one inner scan. The first scan is always going to be a cache
730 * miss. This would likely fail later anyway based on costs, so this is
731 * really just to save some wasted effort.
732 */
735
736 /*
737 * Extract lateral Vars/PHVs within PlaceHolderVars that are due to be
738 * evaluated at innerrel. These lateral Vars/PHVs could be used as
739 * memoize cache keys.
740 */
742
743 /*
744 * We can only have a memoize node when there's some kind of cache key,
745 * either parameterized path clauses or lateral Vars. No cache key sounds
746 * more like something a Materialize node might be more useful for.
747 */
753
754 /*
755 * Currently we don't do this for SEMI and ANTI joins, because nested loop
756 * SEMI/ANTI joins don't scan the inner node to completion, which means
757 * memoize cannot mark the cache entry as complete. Nor can we mark the
758 * cache entry as complete after fetching the first inner tuple, because
759 * if that tuple and the current outer tuple don't satisfy the join
760 * clauses, a second inner tuple that satisfies the parameters would find
761 * the cache entry already marked as complete. The only exception is when
762 * the inner relation is provably unique, as in that case, there won't be
763 * a second matching tuple and we can safely mark the cache entry as
764 * complete after fetching the first inner tuple. Note that in such
765 * cases, the SEMI join should have been reduced to an inner join by
766 * reduce_unique_semijoins.
767 */
769 !extra->inner_unique)
771
772 /*
773 * Memoize normally marks cache entries as complete when it runs out of
774 * tuples to read from its subplan. However, with unique joins, Nested
775 * Loop will skip to the next outer tuple after finding the first matching
776 * inner tuple. This means that we may not read the inner side of the
777 * join to completion which leaves no opportunity to mark the cache entry
778 * as complete. To work around that, when the join is unique we
779 * automatically mark cache entries as complete after fetching the first
780 * tuple. This works when the entire join condition is parameterized.
781 * Otherwise, when the parameterization is only a subset of the join
782 * condition, we can't be sure which part of it causes the join to be
783 * unique. This means there are no guarantees that only 1 tuple will be
784 * read. We cannot mark the cache entry as complete after reading the
785 * first tuple without that guarantee. This means the scope of Memoize
786 * node's usefulness is limited to only outer rows that have no join
787 * partner as this is the only case where Nested Loop would exhaust the
788 * inner scan of a unique join. Since the scope is limited to that, we
789 * just don't bother making a memoize path in this case.
790 *
791 * Lateral vars needn't be considered here as they're not considered when
792 * determining if the join is unique.
793 */
795 {
796 Bitmapset *ppi_serials;
797
800
801 ppi_serials = inner_path->param_info->ppi_serials;
802
804 {
807 }
808 }
809
810 /*
811 * We can't use a memoize node if there are volatile functions in the
812 * inner rel's target list or restrict list. A cache hit could reduce the
813 * number of calls to these functions.
814 */
817
819 {
821
824 }
825
826 /*
827 * Also check the parameterized path restrictinfos for volatile functions.
828 * Indexed functions must be immutable so shouldn't have any volatile
829 * functions, however, with a lateral join the inner scan may not be an
830 * index scan.
831 */
833 {
835 {
837
840 }
841 }
842
843 /* Check if we have hash ops for each parameter to the path */
845 inner_path->param_info,
846 outerrel->top_parent ?
847 outerrel->top_parent : outerrel,
848 innerrel,
849 ph_lateral_vars,
850 ¶m_exprs,
851 &hash_operators,
852 &binary_mode))
853 {
855 innerrel,
856 inner_path,
857 param_exprs,
858 hash_operators,
859 extra->inner_unique,
860 binary_mode,
861 outer_path->rows);
862 }
863
865}
References RelOptInfo::baserestrictinfo, bms_is_member(), contain_volatile_functions(), create_memoize_path(), extract_lateral_vars_from_PHVs(), fb(), foreach_node, JoinPathExtraData::inner_unique, JOIN_ANTI, JOIN_SEMI, RelOptInfo::lateral_vars, lfirst, NIL, paraminfo_get_equal_hashops(), JoinPathExtraData::pgs_mask, PGS_NESTLOOP_MEMOIZE, RelOptInfo::relids, RelOptInfo::reltarget, JoinPathExtraData::restrictlist, and root.
Referenced by consider_parallel_nestloop(), and match_unsorted_outer().
◆ hash_inner_and_outer()
|
static |
Definition at line 2168 of file joinpath.c.
2174{
2176 List *hashclauses;
2177 ListCell *l;
2178
2179 /*
2180 * We need to build only one hashclauses list for any given pair of outer
2181 * and inner relations; all of the hashable clauses will be used as keys.
2182 *
2183 * Scan the join's restrictinfo list to find hashjoinable clauses that are
2184 * usable with this pair of sub-relations.
2185 */
2186 hashclauses = NIL;
2188 {
2190
2191 /*
2192 * If processing an outer join, only use its own join clauses for
2193 * hashing. For inner joins we need not be so picky.
2194 */
2196 continue;
2197
2200 continue; /* not hashjoinable */
2201
2202 /*
2203 * Check if clause has the form "outer op inner" or "inner op outer".
2204 */
2206 innerrel->relids))
2207 continue; /* no good for these input relations */
2208
2209 /*
2210 * If clause has the form "inner op outer", check if its operator has
2211 * valid commutator. This is necessary because hashclauses in this
2212 * form will get commuted in createplan.c to put the outer var on the
2213 * left (see get_switched_clauses). This probably shouldn't ever
2214 * fail, since hashable operators ought to have commutators, but be
2215 * paranoid.
2216 *
2217 * The clause being hashjoinable indicates that it's an OpExpr.
2218 */
2221 continue;
2222
2224 }
2225
2226 /* If we found any usable hashclauses, make paths */
2227 if (hashclauses)
2228 {
2229 /*
2230 * We consider both the cheapest-total-cost and cheapest-startup-cost
2231 * outer paths. There's no need to consider any but the
2232 * cheapest-total-cost inner path, however.
2233 */
2239
2240 /*
2241 * If either cheapest-total path is parameterized by the other rel, we
2242 * can't use a hashjoin. (There's no use looking for alternative
2243 * input paths, since these should already be the least-parameterized
2244 * available paths.)
2245 */
2248 return;
2249
2250 /*
2251 * Consider the cheapest startup outer together with the cheapest
2252 * total inner, and then consider pairings of cheapest-total paths
2253 * including parameterized ones. There is no use in generating
2254 * parameterized paths on the basis of possibly cheap startup cost, so
2255 * this is sufficient.
2256 */
2259 joinrel,
2260 cheapest_startup_outer,
2261 cheapest_total_inner,
2262 hashclauses,
2263 jointype,
2264 extra);
2265
2267 {
2269
2270 /*
2271 * We cannot use an outer path that is parameterized by the inner
2272 * rel.
2273 */
2275 continue;
2276
2278 {
2280
2281 /*
2282 * We cannot use an inner path that is parameterized by the
2283 * outer rel, either.
2284 */
2286 continue;
2287
2290 continue; /* already tried it */
2291
2293 joinrel,
2294 outerpath,
2295 innerpath,
2296 hashclauses,
2297 jointype,
2298 extra);
2299 }
2300 }
2301
2302 /*
2303 * If the joinrel is parallel-safe, we may be able to consider a
2304 * partial hash join.
2305 *
2306 * However, we can't handle JOIN_RIGHT_SEMI, because the hash table is
2307 * either a shared hash table or a private hash table per backend. In
2308 * the shared case, there is no concurrency protection for the match
2309 * flags, so multiple workers could inspect and set the flags
2310 * concurrently, potentially producing incorrect results. In the
2311 * private case, each worker has its own copy of the hash table, so no
2312 * single process has all the match flags.
2313 *
2314 * Also, the resulting path must not be parameterized.
2315 */
2317 jointype != JOIN_RIGHT_SEMI &&
2320 {
2324
2325 cheapest_partial_outer =
2327
2328 /*
2329 * Can we use a partial inner plan too, so that we can build a
2330 * shared hash table in parallel?
2331 */
2333 enable_parallel_hash)
2334 {
2335 cheapest_partial_inner =
2338 cheapest_partial_outer,
2339 cheapest_partial_inner,
2340 hashclauses, jointype, extra,
2341 true /* parallel_hash */ );
2342 }
2343
2344 /*
2345 * Normally, given that the joinrel is parallel-safe, the cheapest
2346 * total inner path will also be parallel-safe, but if not, we'll
2347 * have to search for the cheapest safe, unparameterized inner
2348 * path. If full, right, or right-anti join, we can't use
2349 * parallelism (building the hash table in each backend) because
2350 * no one process has all the match bits.
2351 */
2353 jointype == JOIN_RIGHT ||
2354 jointype == JOIN_RIGHT_ANTI)
2358 else
2359 cheapest_safe_inner =
2361
2364 cheapest_partial_outer,
2365 cheapest_safe_inner,
2366 hashclauses, jointype, extra,
2367 false /* parallel_hash */ );
2368 }
2369 }
2370}
References bms_is_empty, castNode, RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, clause_sides_match_join(), RelOptInfo::consider_parallel, enable_parallel_hash, fb(), get_cheapest_parallel_safe_total_inner(), get_commutator(), InvalidOid, IS_OUTER_JOIN, JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, lappend(), RelOptInfo::lateral_relids, lfirst, linitial, NIL, OidIsValid, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, RelOptInfo::relids, JoinPathExtraData::restrictlist, RINFO_IS_PUSHED_DOWN, root, try_hashjoin_path(), and try_partial_hashjoin_path().
Referenced by add_paths_to_joinrel().
◆ match_unsorted_outer()
|
static |
Definition at line 1826 of file joinpath.c.
1832{
1838
1839 /*
1840 * For now we do not support RIGHT_SEMI join in mergejoin or nestloop
1841 * join.
1842 */
1844 return;
1845
1846 /*
1847 * Nestloop only supports inner, left, semi, and anti joins. Also, if we
1848 * are doing a right, right-anti or full mergejoin, we must use *all* the
1849 * mergeclauses as join clauses, else we will not have a valid plan.
1850 * (Although these two flags are currently inverses, keep them separate
1851 * for clarity and possible future changes.)
1852 */
1853 switch (jointype)
1854 {
1861 break;
1867 break;
1868 default:
1870 (int) jointype);
1873 break;
1874 }
1875
1876 /*
1877 * If inner_cheapest_total is parameterized by the outer rel, ignore it;
1878 * we will consider it below as a member of cheapest_parameterized_paths,
1879 * but the other possibilities considered in this routine aren't usable.
1880 *
1881 * Furthermore, if the inner side is a unique-ified relation, we cannot
1882 * generate any valid paths here, because the inner rel's dependency on
1883 * the outer rel makes unique-ification meaningless.
1884 */
1886 {
1888
1890 return;
1891 }
1892
1894 {
1895 /*
1896 * Consider materializing the cheapest inner path, unless that is
1897 * disabled or the path in question materializes its output anyway.
1898 */
1904 }
1905
1907 {
1910
1911 /*
1912 * We cannot use an outer path that is parameterized by the inner rel.
1913 */
1915 continue;
1916
1917 /*
1918 * The result will have this sort order (even if it is implemented as
1919 * a nestloop, and even if some of the mergeclauses are implemented by
1920 * qpquals rather than as true mergeclauses):
1921 */
1923 outerpath->pathkeys);
1924
1926 {
1927 /*
1928 * Consider nestloop joins using this outer path and various
1929 * available paths for the inner relation. We consider the
1930 * cheapest-total paths for each available parameterization of the
1931 * inner relation, including the unparameterized case.
1932 */
1934
1936 {
1939
1941 joinrel,
1942 outerpath,
1943 innerpath,
1944 merge_pathkeys,
1945 jointype,
1946 PGS_NESTLOOP_PLAIN,
1947 extra);
1948
1949 /*
1950 * Try generating a memoize path and see if that makes the
1951 * nested loop any cheaper.
1952 */
1955 extra);
1958 joinrel,
1959 outerpath,
1960 mpath,
1961 merge_pathkeys,
1962 jointype,
1963 PGS_NESTLOOP_MEMOIZE,
1964 extra);
1965 }
1966
1967 /* Also consider materialized form of the cheapest inner path */
1970 joinrel,
1971 outerpath,
1972 matpath,
1973 merge_pathkeys,
1974 jointype,
1975 PGS_NESTLOOP_MATERIALIZE,
1976 extra);
1977 }
1978
1979 /* Can't do anything else if inner rel is parameterized by outer */
1981 continue;
1982
1983 /* Generate merge join paths */
1985 jointype, extra, useallclauses,
1987 false);
1988 }
1989
1990 /*
1991 * Consider partial nestloop and mergejoin plan if outerrel has any
1992 * partial path and the joinrel is parallel-safe. However, we can't
1993 * handle joins needing lateral rels, since partial paths must not be
1994 * parameterized. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT and
1995 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1996 */
1998 jointype != JOIN_FULL &&
1999 jointype != JOIN_RIGHT &&
2000 jointype != JOIN_RIGHT_ANTI &&
2003 {
2006 jointype, extra);
2007
2008 /*
2009 * If inner_cheapest_total is NULL or non parallel-safe then find the
2010 * cheapest total parallel safe path.
2011 */
2013 !inner_cheapest_total->parallel_safe)
2014 {
2015 inner_cheapest_total =
2017 }
2018
2021 jointype, extra,
2022 inner_cheapest_total);
2023 }
2024}
References bms_is_empty, build_join_pathkeys(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, consider_parallel_mergejoin(), consider_parallel_nestloop(), create_material_path(), elog, ERROR, ExecMaterializesOutput(), fb(), generate_mergejoin_paths(), get_cheapest_parallel_safe_total_inner(), get_memoize_path(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_LEFT, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, JOIN_SEMI, RelOptInfo::lateral_relids, lfirst, NIL, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, JoinPathExtraData::pgs_mask, PGS_NESTLOOP_MATERIALIZE, PGS_NESTLOOP_MEMOIZE, PGS_NESTLOOP_PLAIN, RELATION_WAS_MADE_UNIQUE, root, JoinPathExtraData::sjinfo, and try_nestloop_path().
Referenced by add_paths_to_joinrel().
◆ paraminfo_get_equal_hashops()
|
static |
Definition at line 476 of file joinpath.c.
481{
482 List *lateral_vars;
484
485 *param_exprs = NIL;
486 *operators = NIL;
487 *binary_mode = false;
488
489 /* Add join clauses from param_info to the hash key */
491 {
493
495 {
497 OpExpr *opexpr;
498 Node *expr;
500
502
503 /*
504 * Bail if the rinfo is not compatible. We need a join OpExpr
505 * with 2 args.
506 */
509 innerrel->relids))
510 {
511 list_free(*operators);
512 list_free(*param_exprs);
513 return false;
514 }
515
516 if (rinfo->outer_is_left)
517 {
519 hasheqoperator = rinfo->left_hasheqoperator;
520 }
521 else
522 {
524 hasheqoperator = rinfo->right_hasheqoperator;
525 }
526
527 /* can't do memoize if we can't hash the outer type */
529 {
530 list_free(*operators);
531 list_free(*param_exprs);
532 return false;
533 }
534
535 /*
536 * 'expr' may already exist as a parameter from a previous item in
537 * ppi_clauses. No need to include it again, however we'd better
538 * ensure we do switch into binary mode if required. See below.
539 */
541 {
543 *param_exprs = lappend(*param_exprs, expr);
544 }
545
546 /*
547 * When the join operator is not hashable then it's possible that
548 * the operator will be able to distinguish something that the
549 * hash equality operator could not. For example with floating
550 * point types -0.0 and +0.0 are classed as equal by the hash
551 * function and equality function, but some other operator may be
552 * able to tell those values apart. This means that we must put
553 * memoize into binary comparison mode so that it does bit-by-bit
554 * comparisons rather than a "logical" comparison as it would
555 * using the hash equality operator.
556 */
558 *binary_mode = true;
559 }
560 }
561
562 /* Now add any lateral vars to the cache key too */
565 {
567 TypeCacheEntry *typentry;
568
569 /* Reject if there are any volatile functions in lateral vars */
571 {
572 list_free(*operators);
573 list_free(*param_exprs);
574 return false;
575 }
576
579
580 /* can't use memoize without a valid hash proc and equals operator */
582 {
583 list_free(*operators);
584 list_free(*param_exprs);
585 return false;
586 }
587
588 /*
589 * 'expr' may already exist as a parameter from the ppi_clauses. No
590 * need to include it again, however we'd better ensure we do switch
591 * into binary mode.
592 */
594 {
596 *param_exprs = lappend(*param_exprs, expr);
597 }
598
599 /*
600 * We must go into binary mode as we don't have too much of an idea of
601 * how these lateral Vars are being used. See comment above when we
602 * set *binary_mode for the non-lateral Var case. This could be
603 * relaxed a bit if we had the RestrictInfos and knew the operators
604 * being used, however for cases like Vars that are arguments to
605 * functions we must operate in binary mode as we don't have
606 * visibility into what the function is doing with the Vars.
607 */
608 *binary_mode = true;
609 }
610
611 /* We're okay to use memoize */
612 return true;
613}
References OpExpr::args, RestrictInfo::clause, clause_sides_match_join(), contain_volatile_functions(), TypeCacheEntry::eq_opr, exprType(), fb(), TypeCacheEntry::hash_proc, IsA, lappend(), lappend_oid(), RelOptInfo::lateral_vars, lfirst, linitial, list_concat(), list_free(), list_length(), list_member(), lookup_type_cache(), lsecond, NIL, OidIsValid, RelOptInfo::relids, TYPECACHE_EQ_OPR, and TYPECACHE_HASH_PROC.
Referenced by get_memoize_path().
◆ select_mergejoin_clauses()
|
static |
Definition at line 2395 of file joinpath.c.
2402{
2406 ListCell *l;
2407
2408 /*
2409 * For now we do not support RIGHT_SEMI join in mergejoin: the benefit of
2410 * swapping inputs tends to be small here.
2411 */
2413 {
2416 }
2417
2418 foreach(l, restrictlist)
2419 {
2421
2422 /*
2423 * If processing an outer join, only use its own join clauses in the
2424 * merge. For inner joins we can use pushed-down clauses too. (Note:
2425 * we don't set have_nonmergeable_joinclause here because pushed-down
2426 * clauses will become otherquals not joinquals.)
2427 */
2429 continue;
2430
2431 /* Check that clause is a mergeable operator clause */
2434 {
2435 /*
2436 * The executor can handle extra joinquals that are constants, but
2437 * not anything else, when doing right/right-anti/full merge join.
2438 * (The reason to support constants is so we can do FULL JOIN ON
2439 * FALSE.)
2440 */
2443 continue; /* not mergejoinable */
2444 }
2445
2446 /*
2447 * Check if clause has the form "outer op inner" or "inner op outer".
2448 */
2450 innerrel->relids))
2451 {
2453 continue; /* no good for these input relations */
2454 }
2455
2456 /*
2457 * If clause has the form "inner op outer", check if its operator has
2458 * valid commutator. This is necessary because mergejoin clauses in
2459 * this form will get commuted in createplan.c to put the outer var on
2460 * the left (see get_switched_clauses). This probably shouldn't ever
2461 * fail, since mergejoinable operators ought to have commutators, but
2462 * be paranoid.
2463 *
2464 * The clause being mergejoinable indicates that it's an OpExpr.
2465 */
2468 {
2470 continue;
2471 }
2472
2473 /*
2474 * Insist that each side have a non-redundant eclass. This
2475 * restriction is needed because various bits of the planner expect
2476 * that each clause in a merge be associable with some pathkey in a
2477 * canonical pathkey list, but redundant eclasses can't appear in
2478 * canonical sort orderings. (XXX it might be worth relaxing this,
2479 * but not enough time to address it for 8.3.)
2480 */
2482
2485 {
2487 continue; /* can't handle redundant eclasses */
2488 }
2489
2491 }
2492
2493 /*
2494 * Report whether mergejoin is allowed (see comment at top of function).
2495 */
2496 switch (jointype)
2497 {
2502 break;
2503 default:
2505 break;
2506 }
2507
2509}
References castNode, clause_sides_match_join(), EC_MUST_BE_REDUNDANT, fb(), get_commutator(), IS_OUTER_JOIN, IsA, JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, lappend(), lfirst, NIL, OidIsValid, RelOptInfo::relids, RINFO_IS_PUSHED_DOWN, root, and update_mergeclause_eclasses().
Referenced by add_paths_to_joinrel().
◆ sort_inner_and_outer()
|
static |
Definition at line 1402 of file joinpath.c.
1408{
1414 ListCell *l;
1415
1416 /* Nothing to do if there are no available mergejoin clauses */
1418 return;
1419
1420 /*
1421 * We only consider the cheapest-total-cost input paths, since we are
1422 * assuming here that a sort is required. We will consider
1423 * cheapest-startup-cost input paths later, and only if they don't need a
1424 * sort.
1425 *
1426 * This function intentionally does not consider parameterized input
1427 * paths, except when the cheapest-total is parameterized. If we did so,
1428 * we'd have a combinatorial explosion of mergejoin paths of dubious
1429 * value. This interacts with decisions elsewhere that also discriminate
1430 * against mergejoins with parameterized inputs; see comments in
1431 * src/backend/optimizer/README.
1432 */
1435
1436 /*
1437 * If either cheapest-total path is parameterized by the other rel, we
1438 * can't use a mergejoin. (There's no use looking for alternative input
1439 * paths, since these should already be the least-parameterized available
1440 * paths.)
1441 */
1444 return;
1445
1446 /*
1447 * If the joinrel is parallel-safe, we may be able to consider a partial
1448 * merge join. However, we can't handle JOIN_FULL, JOIN_RIGHT and
1449 * JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1450 * Also, the resulting path must not be parameterized.
1451 */
1453 jointype != JOIN_FULL &&
1454 jointype != JOIN_RIGHT &&
1455 jointype != JOIN_RIGHT_ANTI &&
1458 {
1460
1463 else
1464 cheapest_safe_inner =
1466 }
1467
1468 /*
1469 * Each possible ordering of the available mergejoin clauses will generate
1470 * a differently-sorted result path at essentially the same cost. We have
1471 * no basis for choosing one over another at this level of joining, but
1472 * some sort orders may be more useful than others for higher-level
1473 * mergejoins, so it's worth considering multiple orderings.
1474 *
1475 * Actually, it's not quite true that every mergeclause ordering will
1476 * generate a different path order, because some of the clauses may be
1477 * partially redundant (refer to the same EquivalenceClasses). Therefore,
1478 * what we do is convert the mergeclause list to a list of canonical
1479 * pathkeys, and then consider different orderings of the pathkeys.
1480 *
1481 * Generating a path for *every* permutation of the pathkeys doesn't seem
1482 * like a winning strategy; the cost in planning time is too high. For
1483 * now, we generate one path for each pathkey, listing that pathkey first
1484 * and the rest in random order. This should allow at least a one-clause
1485 * mergejoin without re-sorting against any other possible mergejoin
1486 * partner path. But if we've not guessed the right ordering of secondary
1487 * keys, we may end up evaluating clauses as qpquals when they could have
1488 * been done as mergeclauses. (In practice, it's rare that there's more
1489 * than two or three mergeclauses, so expending a huge amount of thought
1490 * on that is probably not worth it.)
1491 *
1492 * The pathkey order returned by select_outer_pathkeys_for_merge() has
1493 * some heuristics behind it (see that function), so be sure to try it
1494 * exactly as-is as well as making variants.
1495 */
1497 extra->mergeclause_list,
1498 joinrel);
1499
1501 {
1507
1508 /* Make a pathkey list with this guy first */
1512 foreach_current_index(l)));
1513 else
1515
1516 /* Sort the mergeclauses into the corresponding ordering */
1517 cur_mergeclauses =
1519 outerkeys,
1520 extra->mergeclause_list);
1521
1522 /* Should have used them all... */
1524
1525 /* Build sort pathkeys for the inner side */
1527 cur_mergeclauses,
1528 outerkeys);
1529
1530 /* Build pathkeys representing output sort order */
1532 outerkeys);
1533
1534 /*
1535 * And now we can make the path.
1536 *
1537 * Note: it's possible that the cheapest paths will already be sorted
1538 * properly. try_mergejoin_path will detect that case and suppress an
1539 * explicit sort step, so we needn't do so here.
1540 */
1542 joinrel,
1543 outer_path,
1544 inner_path,
1545 merge_pathkeys,
1546 cur_mergeclauses,
1547 outerkeys,
1548 innerkeys,
1549 jointype,
1550 extra,
1551 false);
1552
1553 /*
1554 * If we have partial outer and parallel safe inner path then try
1555 * partial mergejoin path.
1556 */
1559 joinrel,
1560 cheapest_partial_outer,
1561 cheapest_safe_inner,
1562 merge_pathkeys,
1563 cur_mergeclauses,
1564 outerkeys,
1565 innerkeys,
1566 jointype,
1567 extra);
1568 }
1569}
References Assert, bms_is_empty, build_join_pathkeys(), RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, fb(), find_mergeclauses_for_outer_pathkeys(), foreach_current_index, get_cheapest_parallel_safe_total_inner(), JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, RelOptInfo::lateral_relids, lcons(), lfirst, linitial, list_copy(), list_delete_nth_cell(), list_head(), list_length(), make_inner_pathkeys_for_merge(), JoinPathExtraData::mergeclause_list, NIL, RelOptInfo::partial_pathlist, PATH_PARAM_BY_REL, RelOptInfo::pathlist, root, select_outer_pathkeys_for_merge(), try_mergejoin_path(), and try_partial_mergejoin_path().
Referenced by add_paths_to_joinrel().
◆ try_hashjoin_path()
|
static |
Definition at line 1267 of file joinpath.c.
1274{
1276 JoinCostWorkspace workspace;
1277
1278 /*
1279 * If we are forming an outer join at this join, it's nonsensical to use
1280 * an input path that uses the outer join as part of its parameterization.
1281 * (This can happen despite our join order restrictions, since those apply
1282 * to what is in an input relation not what its parameters are.)
1283 */
1287 return;
1288
1289 /*
1290 * Check to see if proposed path is still parameterized, and reject if the
1291 * parameterization wouldn't be sensible.
1292 */
1294 inner_path);
1297 {
1298 /* Waste no memory when we reject a path here */
1300 return;
1301 }
1302
1303 /*
1304 * See comments in try_nestloop_path(). Also note that hashjoin paths
1305 * never have any output pathkeys, per comments in create_hashjoin_path.
1306 */
1309
1313 {
1316 joinrel,
1317 jointype,
1318 &workspace,
1319 extra,
1320 outer_path,
1321 inner_path,
1322 false, /* parallel_hash */
1323 extra->restrictlist,
1324 required_outer,
1325 hashclauses));
1326 }
1327 else
1328 {
1329 /* Waste no memory when we reject a path here */
1331 }
1332}
References add_path(), add_path_precheck(), bms_free(), bms_is_member(), bms_overlap(), calc_non_nestloop_required_outer(), create_hashjoin_path(), JoinCostWorkspace::disabled_nodes, fb(), initial_cost_hashjoin(), NIL, SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_REQ_OUTER, JoinPathExtraData::restrictlist, root, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, and JoinCostWorkspace::total_cost.
Referenced by hash_inner_and_outer().
◆ try_mergejoin_path()
|
static |
Definition at line 1074 of file joinpath.c.
1085{
1087 int outer_presorted_keys = 0;
1088 JoinCostWorkspace workspace;
1089
1091 {
1093 joinrel,
1094 outer_path,
1095 inner_path,
1096 pathkeys,
1097 mergeclauses,
1098 outersortkeys,
1099 innersortkeys,
1100 jointype,
1101 extra);
1102 return;
1103 }
1104
1105 /*
1106 * If we are forming an outer join at this join, it's nonsensical to use
1107 * an input path that uses the outer join as part of its parameterization.
1108 * (This can happen despite our join order restrictions, since those apply
1109 * to what is in an input relation not what its parameters are.)
1110 */
1114 return;
1115
1116 /*
1117 * Check to see if proposed path is still parameterized, and reject if the
1118 * parameterization wouldn't be sensible.
1119 */
1121 inner_path);
1124 {
1125 /* Waste no memory when we reject a path here */
1127 return;
1128 }
1129
1130 /*
1131 * If the given paths are already well enough ordered, we can skip doing
1132 * an explicit sort.
1133 *
1134 * We need to determine the number of presorted keys of the outer path to
1135 * decide whether explicit incremental sort can be applied when
1136 * outersortkeys is not NIL. We do not need to do the same for the inner
1137 * path though, as incremental sort currently does not support
1138 * mark/restore.
1139 */
1140 if (outersortkeys &&
1142 &outer_presorted_keys))
1143 outersortkeys = NIL;
1144 if (innersortkeys &&
1146 innersortkeys = NIL;
1147
1148 /*
1149 * See comments in try_nestloop_path().
1150 */
1153 outersortkeys, innersortkeys,
1154 outer_presorted_keys,
1155 extra);
1156
1159 pathkeys, required_outer))
1160 {
1163 joinrel,
1164 jointype,
1165 &workspace,
1166 extra,
1167 outer_path,
1168 inner_path,
1169 extra->restrictlist,
1170 pathkeys,
1171 required_outer,
1172 mergeclauses,
1173 outersortkeys,
1174 innersortkeys,
1175 outer_presorted_keys));
1176 }
1177 else
1178 {
1179 /* Waste no memory when we reject a path here */
1181 }
1182}
References add_path(), add_path_precheck(), bms_free(), bms_is_member(), bms_overlap(), calc_non_nestloop_required_outer(), create_mergejoin_path(), JoinCostWorkspace::disabled_nodes, fb(), initial_cost_mergejoin(), NIL, SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, PATH_REQ_OUTER, pathkeys_contained_in(), pathkeys_count_contained_in(), JoinPathExtraData::restrictlist, root, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, JoinCostWorkspace::total_cost, and try_partial_mergejoin_path().
Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().
◆ try_nestloop_path()
|
static |
Definition at line 873 of file joinpath.c.
881{
883 JoinCostWorkspace workspace;
887 Relids outerrelids;
890
891 /*
892 * If we are forming an outer join at this join, it's nonsensical to use
893 * an input path that uses the outer join as part of its parameterization.
894 * (This can happen despite our join order restrictions, since those apply
895 * to what is in an input relation not what its parameters are.)
896 */
900 return;
901
902 /*
903 * Any parameterization of the input paths refers to topmost parents of
904 * the relevant relations, because reparameterize_path_by_child() hasn't
905 * been called yet. So we must consider topmost parents of the relations
906 * being joined, too, while determining parameterization of the result and
907 * checking for disallowed parameterization cases.
908 */
911 else
913
915 outerrelids = outerrel->top_parent_relids;
916 else
917 outerrelids = outerrel->relids;
918
919 /*
920 * Check to see if proposed path is still parameterized, and reject if the
921 * parameterization wouldn't be sensible --- unless allow_star_schema_join
922 * says to allow it anyway.
923 */
929 {
930 /* Waste no memory when we reject a path here */
932 return;
933 }
934
935 /* If we got past that, we shouldn't have any unsafe outer-join refs */
937
938 /*
939 * If the inner path is parameterized, it is parameterized by the topmost
940 * parent of the outer rel, not the outer rel itself. We will need to
941 * translate the parameterization, if this path is chosen, during
942 * create_plan(). Here we just check whether we will be able to perform
943 * the translation, and if not avoid creating a nestloop path.
944 */
947 {
949 return;
950 }
951
952 /*
953 * Do a precheck to quickly eliminate obviously-inferior paths. We
954 * calculate a cheap lower bound on the path's cost and then use
955 * add_path_precheck() to see if the path is clearly going to be dominated
956 * by some existing path for the joinrel. If not, do the full pushup with
957 * creating a fully valid path structure and submitting it to add_path().
958 * The latter two steps are expensive enough to make this two-phase
959 * methodology worthwhile.
960 */
964
967 pathkeys, required_outer))
968 {
971 joinrel,
972 jointype,
973 &workspace,
974 extra,
975 outer_path,
976 inner_path,
977 extra->restrictlist,
978 pathkeys,
979 required_outer));
980 }
981 else
982 {
983 /* Waste no memory when we reject a path here */
985 }
986}
References add_path(), add_path_precheck(), allow_star_schema_join(), Assert, bms_free(), bms_is_member(), bms_overlap(), calc_nestloop_required_outer(), create_nestloop_path(), JoinCostWorkspace::disabled_nodes, fb(), initial_cost_nestloop(), SpecialJoinInfo::ojrelid, JoinPathExtraData::param_source_rels, path_is_reparameterizable_by_child(), PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, PGS_CONSIDER_NONPARTIAL, RelOptInfo::relids, JoinPathExtraData::restrictlist, root, JoinPathExtraData::sjinfo, JoinCostWorkspace::startup_cost, RelOptInfo::top_parent_relids, and JoinCostWorkspace::total_cost.
Referenced by match_unsorted_outer().
◆ try_partial_hashjoin_path()
|
static |
Definition at line 1344 of file joinpath.c.
1352{
1353 JoinCostWorkspace workspace;
1354
1355 /*
1356 * If the inner path is parameterized, we can't use a partial hashjoin.
1357 * Parameterized partial paths are not supported. The caller should
1358 * already have verified that no lateral rels are required here.
1359 */
1363 return;
1364
1365 /*
1366 * Before creating a path, get a quick lower bound on what it is likely to
1367 * cost. Bail out right away if it looks terrible.
1368 */
1373 return;
1374
1375 /* Might be good enough to be worth trying, so let's try it. */
1378 joinrel,
1379 jointype,
1380 &workspace,
1381 extra,
1382 outer_path,
1383 inner_path,
1384 parallel_hash,
1385 extra->restrictlist,
1386 NULL,
1387 hashclauses));
1388}
References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty, create_hashjoin_path(), JoinCostWorkspace::disabled_nodes, fb(), initial_cost_hashjoin(), RelOptInfo::lateral_relids, NIL, PATH_REQ_OUTER, JoinPathExtraData::restrictlist, root, and JoinCostWorkspace::total_cost.
Referenced by hash_inner_and_outer().
◆ try_partial_mergejoin_path()
|
static |
Definition at line 1190 of file joinpath.c.
1200{
1201 int outer_presorted_keys = 0;
1202 JoinCostWorkspace workspace;
1203
1204 /*
1205 * See comments in try_partial_hashjoin_path().
1206 */
1210 return;
1211
1212 /*
1213 * If the given paths are already well enough ordered, we can skip doing
1214 * an explicit sort.
1215 *
1216 * We need to determine the number of presorted keys of the outer path to
1217 * decide whether explicit incremental sort can be applied when
1218 * outersortkeys is not NIL. We do not need to do the same for the inner
1219 * path though, as incremental sort currently does not support
1220 * mark/restore.
1221 */
1222 if (outersortkeys &&
1224 &outer_presorted_keys))
1225 outersortkeys = NIL;
1226 if (innersortkeys &&
1228 innersortkeys = NIL;
1229
1230 /*
1231 * See comments in try_partial_nestloop_path().
1232 */
1235 outersortkeys, innersortkeys,
1236 outer_presorted_keys,
1237 extra);
1238
1240 workspace.total_cost, pathkeys))
1241 return;
1242
1243 /* Might be good enough to be worth trying, so let's try it. */
1246 joinrel,
1247 jointype,
1248 &workspace,
1249 extra,
1250 outer_path,
1251 inner_path,
1252 extra->restrictlist,
1253 pathkeys,
1254 NULL,
1255 mergeclauses,
1256 outersortkeys,
1257 innersortkeys,
1258 outer_presorted_keys));
1259}
References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty, create_mergejoin_path(), JoinCostWorkspace::disabled_nodes, fb(), initial_cost_mergejoin(), RelOptInfo::lateral_relids, NIL, PATH_REQ_OUTER, pathkeys_contained_in(), pathkeys_count_contained_in(), JoinPathExtraData::restrictlist, root, and JoinCostWorkspace::total_cost.
Referenced by sort_inner_and_outer(), and try_mergejoin_path().
◆ try_partial_nestloop_path()
|
static |
Definition at line 994 of file joinpath.c.
1002{
1003 JoinCostWorkspace workspace;
1004
1005 /*
1006 * If the inner path is parameterized, the parameterization must be fully
1007 * satisfied by the proposed outer path. Parameterized partial paths are
1008 * not supported. The caller should already have verified that no lateral
1009 * rels are required here.
1010 */
1014 {
1017 Relids outerrelids;
1018
1019 /*
1020 * The inner and outer paths are parameterized, if at all, by the top
1021 * level parents, not the child relations, so we must use those relids
1022 * for our parameterization tests.
1023 */
1025 outerrelids = outerrel->top_parent_relids;
1026 else
1027 outerrelids = outerrel->relids;
1028
1030 return;
1031 }
1032
1033 /*
1034 * If the inner path is parameterized, it is parameterized by the topmost
1035 * parent of the outer rel, not the outer rel itself. We will need to
1036 * translate the parameterization, if this path is chosen, during
1037 * create_plan(). Here we just check whether we will be able to perform
1038 * the translation, and if not avoid creating a nestloop path.
1039 */
1042 return;
1043
1044 /*
1045 * Before creating a path, get a quick lower bound on what it is likely to
1046 * cost. Bail out right away if it looks terrible.
1047 */
1051 workspace.total_cost, pathkeys))
1052 return;
1053
1054 /* Might be good enough to be worth trying, so let's try it. */
1057 joinrel,
1058 jointype,
1059 &workspace,
1060 extra,
1061 outer_path,
1062 inner_path,
1063 extra->restrictlist,
1064 pathkeys,
1065 NULL));
1066}
References add_partial_path(), add_partial_path_precheck(), Assert, bms_is_empty, bms_is_subset(), create_nestloop_path(), JoinCostWorkspace::disabled_nodes, fb(), initial_cost_nestloop(), RelOptInfo::lateral_relids, path_is_reparameterizable_by_child(), PATH_PARAM_BY_PARENT, PATH_REQ_OUTER, RelOptInfo::relids, JoinPathExtraData::restrictlist, root, RelOptInfo::top_parent_relids, and JoinCostWorkspace::total_cost.
Referenced by consider_parallel_nestloop().
Variable Documentation
◆ join_path_setup_hook
| join_path_setup_hook_type join_path_setup_hook = NULL |
Definition at line 32 of file joinpath.c.
Referenced by add_paths_to_joinrel().
◆ set_join_pathlist_hook
| set_join_pathlist_hook_type set_join_pathlist_hook = NULL |
Definition at line 31 of file joinpath.c.
Referenced by add_paths_to_joinrel().
