| blob | 1007cf05339a073c575d03de892c6fdb0eee0a84 |
1 /*-------------------------------------------------------------------------
2 *
3 * joinrels.c
4 * Routines to determine which relations should be joined
5 *
6 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * $PostgreSQL$
12 *
13 *-------------------------------------------------------------------------
14 */
35 /*
36 * join_search_one_level
37 * Consider ways to produce join relations containing exactly 'level'
38 * jointree items. (This is one step of the dynamic-programming method
39 * embodied in standard_join_search.) Join rel nodes for each feasible
40 * combination of lower-level rels are created and returned in a list.
41 * Implementation paths are created for each such joinrel, too.
42 *
43 * level: level of rels we want to make this time.
44 * joinrels[j], 1 <= j < level, is a list of rels containing j items.
45 */
46 List *
48 {
54 /*
55 * First, consider left-sided and right-sided plans, in which rels of
56 * exactly level-1 member relations are joined against initial relations.
57 * We prefer to join using join clauses, but if we find a rel of level-1
58 * members that has no join clauses, we will generate Cartesian-product
59 * joins against all initial rels not already contained in it.
60 *
61 * In the first pass (level == 2), we try to join each initial rel to each
62 * initial rel that appears later in joinrels[1]. (The mirror-image joins
63 * are handled automatically by make_join_rel.) In later passes, we try
64 * to join rels of size level-1 from joinrels[level-1] to each initial rel
65 * in joinrels[1].
66 */
68 {
74 * rels */
75 else
77 * rels */
81 {
82 /*
83 * Note that if all available join clauses for this rel require
84 * more than one other rel, we will fail to make any joins against
85 * it here. In most cases that's OK; it'll be considered by
86 * "bushy plan" join code in a higher-level pass where we have
87 * those other rels collected into a join rel.
88 *
89 * See also the last-ditch case below.
90 */
92 old_rel,
93 other_rels);
94 }
95 else
96 {
97 /*
98 * Oops, we have a relation that is not joined to any other
99 * relation, either directly or by join-order restrictions.
100 * Cartesian product time.
101 */
103 old_rel,
104 other_rels);
105 }
107 /*
108 * At levels above 2 we will generate the same joined relation in
109 * multiple ways --- for example (a join b) join c is the same
110 * RelOptInfo as (b join c) join a, though the second case will add a
111 * different set of Paths to it. To avoid making extra work for
112 * subsequent passes, do not enter the same RelOptInfo into our output
113 * list multiple times.
114 */
116 }
118 /*
119 * Now, consider "bushy plans" in which relations of k initial rels are
120 * joined to relations of level-k initial rels, for 2 <= k <= level-2.
121 *
122 * We only consider bushy-plan joins for pairs of rels where there is a
123 * suitable join clause (or join order restriction), in order to avoid
124 * unreasonable growth of planning time.
125 */
127 {
130 /*
131 * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
132 * need to go as far as the halfway point.
133 */
138 {
143 /*
144 * We can ignore clauseless joins here, *except* when they
145 * participate in join-order restrictions --- then we might have
146 * to force a bushy join plan.
147 */
154 else
158 {
162 {
163 /*
164 * OK, we can build a rel of the right level from this
165 * pair of rels. Do so if there is at least one usable
166 * join clause or a relevant join restriction.
167 */
170 {
174 /* Avoid making duplicate entries ... */
177 jrel);
178 }
179 }
180 }
181 }
182 }
184 /*
185 * Last-ditch effort: if we failed to find any usable joins so far, force
186 * a set of cartesian-product joins to be generated. This handles the
187 * special case where all the available rels have join clauses but we
188 * cannot use any of those clauses yet. An example is
189 *
190 * SELECT * FROM a,b,c WHERE (a.f1 + b.f2 + c.f3) = 0;
191 *
192 * The join clause will be usable at level 3, but at level 2 we have no
193 * choice but to make cartesian joins. We consider only left-sided and
194 * right-sided cartesian joins in this case (no bushy).
195 */
197 {
198 /*
199 * This loop is just like the first one, except we always call
200 * make_rels_by_clauseless_joins().
201 */
203 {
209 * rels */
210 else
212 * rels */
215 old_rel,
216 other_rels);
219 }
221 /*----------
222 * When special joins are involved, there may be no legal way
223 * to make an N-way join for some values of N. For example consider
224 *
225 * SELECT ... FROM t1 WHERE
226 * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
227 * y IN (SELECT ... FROM t4,t5 WHERE ...)
228 *
229 * We will flatten this query to a 5-way join problem, but there are
230 * no 4-way joins that join_is_legal() will consider legal. We have
231 * to accept failure at level 4 and go on to discover a workable
232 * bushy plan at level 5.
233 *
234 * However, if there are no special joins then join_is_legal() should
235 * never fail, and so the following sanity check is useful.
236 *----------
237 */
240 }
243 }
245 /*
246 * make_rels_by_clause_joins
247 * Build joins between the given relation 'old_rel' and other relations
248 * that participate in join clauses that 'old_rel' also participates in
249 * (or participate in join-order restrictions with it).
250 * The join rel nodes are returned in a list.
251 *
252 * 'old_rel' is the relation entry for the relation to be joined
253 * 'other_rels': the first cell in a linked list containing the other
254 * rels to be considered for joining
255 *
256 * Currently, this is only used with initial rels in other_rels, but it
257 * will work for joining to joinrels too.
258 */
263 {
268 {
274 {
280 }
281 }
284 }
286 /*
287 * make_rels_by_clauseless_joins
288 * Given a relation 'old_rel' and a list of other relations
289 * 'other_rels', create a join relation between 'old_rel' and each
290 * member of 'other_rels' that isn't already included in 'old_rel'.
291 * The join rel nodes are returned in a list.
292 *
293 * 'old_rel' is the relation entry for the relation to be joined
294 * 'other_rels': the first cell of a linked list containing the
295 * other rels to be considered for joining
296 *
297 * Currently, this is only used with initial rels in other_rels, but it would
298 * work for joining to joinrels too.
299 */
304 {
309 {
313 {
318 /*
319 * As long as given other_rels are distinct, don't need to test to
320 * see if jrel is already part of output list.
321 */
324 }
325 }
328 }
331 /*
332 * join_is_legal
333 * Determine whether a proposed join is legal given the query's
334 * join order constraints; and if it is, determine the join type.
335 *
336 * Caller must supply not only the two rels, but the union of their relids.
337 * (We could simplify the API by computing joinrelids locally, but this
338 * would be redundant work in the normal path through make_join_rel.)
339 *
340 * On success, *sjinfo_p is set to NULL if this is to be a plain inner join,
341 * else it's set to point to the associated SpecialJoinInfo node. Also,
342 * *reversed_p is set TRUE if the given relations need to be swapped to
343 * match the SpecialJoinInfo node.
344 */
345 static bool
347 Relids joinrelids,
349 {
355 /*
356 * Ensure output params are set on failure return. This is just to
357 * suppress uninitialized-variable warnings from overly anal compilers.
358 */
362 /*
363 * If we have any special joins, the proposed join might be illegal; and
364 * in any case we have to determine its join type. Scan the join info
365 * list for conflicts.
366 */
372 {
375 /*
376 * This special join is not relevant unless its RHS overlaps the
377 * proposed join. (Check this first as a fast path for dismissing
378 * most irrelevant SJs quickly.)
379 */
383 /*
384 * Also, not relevant if proposed join is fully contained within RHS
385 * (ie, we're still building up the RHS).
386 */
390 /*
391 * Also, not relevant if SJ is already done within either input.
392 */
400 /*
401 * If one input contains min_lefthand and the other contains
402 * min_righthand, then we can perform the SJ at this join.
403 *
404 * Barf if we get matches to more than one SJ (is that possible?)
405 */
408 {
413 }
416 {
421 }
426 {
427 /*----------
428 * For a semijoin, we can join the RHS to anything else by
429 * unique-ifying the RHS (if the RHS can be unique-ified).
430 * We will only get here if we have the full RHS but less
431 * than min_lefthand on the LHS.
432 *
433 * The reason to consider such a join path is exemplified by
434 * SELECT ... FROM a,b WHERE (a.x,b.y) IN (SELECT c1,c2 FROM c)
435 * If we insist on doing this as a semijoin we will first have
436 * to form the cartesian product of A*B. But if we unique-ify
437 * C then the semijoin becomes a plain innerjoin and we can join
438 * in any order, eg C to A and then to B. When C is much smaller
439 * than A and B this can be a huge win. So we allow C to be
440 * joined to just A or just B here, and then make_join_rel has
441 * to handle the case properly.
442 *
443 * Note that actually we'll allow unique-ified C to be joined to
444 * some other relation D here, too. That is legal, if usually not
445 * very sane, and this routine is only concerned with legality not
446 * with whether the join is good strategy.
447 *----------
448 */
453 }
458 {
459 /* Reversed semijoin case */
464 }
465 else
466 {
467 /*----------
468 * Otherwise, the proposed join overlaps the RHS but isn't
469 * a valid implementation of this SJ. It might still be
470 * a legal join, however. If both inputs overlap the RHS,
471 * assume that it's OK. Since the inputs presumably got past
472 * this function's checks previously, they can't overlap the
473 * LHS and their violations of the RHS boundary must represent
474 * SJs that have been determined to commute with this one.
475 * We have to allow this to work correctly in cases like
476 * (a LEFT JOIN (b JOIN (c LEFT JOIN d)))
477 * when the c/d join has been determined to commute with the join
478 * to a, and hence d is not part of min_righthand for the upper
479 * join. It should be legal to join b to c/d but this will appear
480 * as a violation of the upper join's RHS.
481 * Furthermore, if one input overlaps the RHS and the other does
482 * not, we should still allow the join if it is a valid
483 * implementation of some other SJ. We have to allow this to
484 * support the associative identity
485 * (a LJ b on Pab) LJ c ON Pbc = a LJ (b LJ c ON Pbc) on Pab
486 * since joining B directly to C violates the lower SJ's RHS.
487 * We assume that make_outerjoininfo() set things up correctly
488 * so that we'll only match to some SJ if the join is valid.
489 * Set flag here to check at bottom of loop.
490 *
491 * For a semijoin, assume it's okay if either side fully contains
492 * the RHS (per the unique-ification case above).
493 *----------
494 */
498 {
499 /* seems OK */
501 }
505 {
506 /* seems OK */
507 }
508 else
510 }
511 }
513 /* Fail if violated some SJ's RHS and didn't match to another SJ */
517 /* Otherwise, it's a valid join */
521 }
524 /*
525 * make_join_rel
526 * Find or create a join RelOptInfo that represents the join of
527 * the two given rels, and add to it path information for paths
528 * created with the two rels as outer and inner rel.
529 * (The join rel may already contain paths generated from other
530 * pairs of rels that add up to the same set of base rels.)
531 *
532 * NB: will return NULL if attempted join is not valid. This can happen
533 * when working with outer joins, or with IN or EXISTS clauses that have been
534 * turned into joins.
535 */
536 RelOptInfo *
538 {
539 Relids joinrelids;
542 SpecialJoinInfo sjinfo_data;
546 /* We should never try to join two overlapping sets of rels. */
549 /* Construct Relids set that identifies the joinrel. */
552 /* Check validity and determine join type. */
555 {
556 /* invalid join path */
559 }
561 /* Swap rels if needed to match the join info. */
563 {
568 }
570 /*
571 * If it's a plain inner join, then we won't have found anything in
572 * join_info_list. Make up a SpecialJoinInfo so that selectivity
573 * estimation functions will know what's being joined.
574 */
576 {
584 /* we don't bother trying to make the remaining fields valid */
588 }
590 /*
591 * Find or build the join RelOptInfo, and compute the restrictlist that
592 * goes with this particular joining.
593 */
597 /*
598 * If we've already proven this join is empty, we needn't consider any
599 * more paths for it.
600 */
602 {
605 }
607 /*
608 * Consider paths using each rel as both outer and inner. Depending on
609 * the join type, a provably empty outer or inner rel might mean the join
610 * is provably empty too; in which case throw away any previously computed
611 * paths and mark the join as dummy. (We do it this way since it's
612 * conceivable that dummy-ness of a multi-element join might only be
613 * noticeable for certain construction paths.)
614 *
615 * Also, a provably constant-false join restriction typically means that
616 * we can skip evaluating one or both sides of the join. We do this by
617 * marking the appropriate rel as dummy.
618 *
619 * We need only consider the jointypes that appear in join_info_list, plus
620 * JOIN_INNER.
621 */
623 {
627 {
630 }
633 restrictlist);
636 restrictlist);
640 {
643 }
649 restrictlist);
652 restrictlist);
656 {
659 }
662 restrictlist);
665 restrictlist);
669 /*
670 * We might have a normal semijoin, or a case where we don't have
671 * enough rels to do the semijoin but can unique-ify the RHS and
672 * then do an innerjoin (see comments in join_is_legal). In the
673 * latter case we can't apply JOIN_SEMI joining.
674 */
677 {
680 {
683 }
686 restrictlist);
687 }
689 /*
690 * If we know how to unique-ify the RHS and one input rel is
691 * exactly the RHS (not a superset) we can consider unique-ifying
692 * it and then doing a regular join. (The create_unique_path
693 * check here is probably redundant with what join_is_legal did,
694 * but if so the check is cheap because it's cached. So test
695 * anyway to be sure.)
696 */
700 {
703 restrictlist);
706 restrictlist);
707 }
711 {
714 }
720 restrictlist);
723 /* other values not expected here */
726 }
731 }
734 /*
735 * have_join_order_restriction
736 * Detect whether the two relations should be joined to satisfy
737 * a join-order restriction arising from special joins.
738 *
739 * In practice this is always used with have_relevant_joinclause(), and so
740 * could be merged with that function, but it seems clearer to separate the
741 * two concerns. We need this test because there are degenerate cases where
742 * a clauseless join must be performed to satisfy join-order restrictions.
743 *
744 * Note: this is only a problem if one side of a degenerate outer join
745 * contains multiple rels, or a clauseless join is required within an
746 * IN/EXISTS RHS; else we will find a join path via the "last ditch" case in
747 * join_search_one_level(). We could dispense with this test if we were
748 * willing to try bushy plans in the "last ditch" case, but that seems much
749 * less efficient.
750 */
751 bool
754 {
758 /*
759 * It's possible that the rels correspond to the left and right sides of a
760 * degenerate outer join, that is, one with no joinclause mentioning the
761 * non-nullable side; in which case we should force the join to occur.
762 *
763 * Also, the two rels could represent a clauseless join that has to be
764 * completed to build up the LHS or RHS of an outer join.
765 */
767 {
770 /* ignore full joins --- other mechanisms handle them */
774 /* Can we perform the SJ with these rels? */
777 {
780 }
783 {
786 }
788 /*
789 * Might we need to join these rels to complete the RHS? We have to
790 * use "overlap" tests since either rel might include a lower SJ that
791 * has been proven to commute with this one.
792 */
795 {
798 }
800 /* Likewise for the LHS. */
803 {
806 }
807 }
809 /*
810 * We do not force the join to occur if either input rel can legally be
811 * joined to anything else using joinclauses. This essentially means that
812 * clauseless bushy joins are put off as long as possible. The reason is
813 * that when there is a join order restriction high up in the join tree
814 * (that is, with many rels inside the LHS or RHS), we would otherwise
815 * expend lots of effort considering very stupid join combinations within
816 * its LHS or RHS.
817 */
819 {
823 }
826 }
829 /*
830 * has_join_restriction
831 * Detect whether the specified relation has join-order restrictions
832 * due to being inside an outer join or an IN (sub-SELECT).
833 *
834 * Essentially, this tests whether have_join_order_restriction() could
835 * succeed with this rel and some other one. It's OK if we sometimes
836 * say "true" incorrectly. (Therefore, we don't bother with the relatively
837 * expensive has_legal_joinclause test.)
838 */
839 static bool
841 {
845 {
848 /* ignore full joins --- other mechanisms preserve their ordering */
852 /* ignore if SJ is already contained in rel */
857 /* restricted if it overlaps LHS or RHS, but doesn't contain SJ */
861 }
864 }
867 /*
868 * has_legal_joinclause
869 * Detect whether the specified relation can legally be joined
870 * to any other rels using join clauses.
871 *
872 * We consider only joins to single other relations in the current
873 * initial_rels list. This is sufficient to get a "true" result in most real
874 * queries, and an occasional erroneous "false" will only cost a bit more
875 * planning time. The reason for this limitation is that considering joins to
876 * other joins would require proving that the other join rel can legally be
877 * formed, which seems like too much trouble for something that's only a
878 * heuristic to save planning time. (Note: we must look at initial_rels
879 * and not all of the query, since when we are planning a sub-joinlist we
880 * may be forced to make clauseless joins within initial_rels even though
881 * there are join clauses linking to other parts of the query.)
882 */
883 static bool
885 {
889 {
892 /* ignore rels that are already in "rel" */
897 {
898 Relids joinrelids;
902 /* join_is_legal needs relids of the union */
907 {
908 /* Yes, this will work */
911 }
914 }
915 }
918 }
921 /*
922 * is_dummy_rel --- has relation been proven empty?
923 *
924 * If so, it will have a single path that is dummy.
925 */
926 static bool
928 {
931 }
933 /*
934 * Mark a rel as proven empty.
935 */
936 static void
938 {
939 /* Set dummy size estimate */
942 /* Evict any previously chosen paths */
945 /* Set up the dummy path */
948 /* Set or update cheapest_total_path */
950 }
953 /*
954 * restriction_is_constant_false --- is a restrictlist just FALSE?
955 *
956 * In cases where a qual is provably constant FALSE, eval_const_expressions
957 * will generally have thrown away anything that's ANDed with it. In outer
958 * join situations this will leave us computing cartesian products only to
959 * decide there's no match for an outer row, which is pretty stupid. So,
960 * we need to detect the case.
961 */
962 static bool
964 {
967 /*
968 * Despite the above comment, the restriction list we see here might
969 * possibly have other members besides the FALSE constant, since other
970 * quals could get "pushed down" to the outer join level. So we check
971 * each member of the list.
972 */
974 {
979 {
982 /* constant NULL is as good as constant FALSE for our purposes */
987 }
988 }
990 }