Index: src/backend/optimizer/README =================================================================== RCS file: /cvsroot/pgsql/src/backend/optimizer/README,v retrieving revision 1.35 diff -c -r1.35 README *** src/backend/optimizer/README 1 Jul 2006 18:38:32 -0000 1.35 --- src/backend/optimizer/README 13 Feb 2007 02:21:36 -0000 *************** *** 225,232 **** non-FULL joins can be freely associated into the lefthand side of an OJ, but in general they can't be associated into the righthand side. So the restriction enforced by make_join_rel is that a proposed join ! can't join across a RHS boundary (ie, join anything inside the RHS ! to anything else) unless the join validly implements some outer join. (To support use of identity 3, we have to allow cases where an apparent violation of a lower OJ's RHS is committed while forming an upper OJ. If this wouldn't in fact be legal, the upper OJ's minimum LHS or RHS --- 225,232 ---- non-FULL joins can be freely associated into the lefthand side of an OJ, but in general they can't be associated into the righthand side. So the restriction enforced by make_join_rel is that a proposed join ! can't join a rel within or partly within an RHS boundary to one outside ! the boundary, unless the join validly implements some outer join. (To support use of identity 3, we have to allow cases where an apparent violation of a lower OJ's RHS is committed while forming an upper OJ. If this wouldn't in fact be legal, the upper OJ's minimum LHS or RHS Index: src/backend/optimizer/geqo/geqo_eval.c =================================================================== RCS file: /cvsroot/pgsql/src/backend/optimizer/geqo/geqo_eval.c,v retrieving revision 1.81.2.1 diff -c -r1.81.2.1 geqo_eval.c *** src/backend/optimizer/geqo/geqo_eval.c 12 Dec 2006 21:31:09 -0000 1.81.2.1 --- src/backend/optimizer/geqo/geqo_eval.c 13 Feb 2007 02:21:36 -0000 *************** *** 182,188 **** * tour other than the one given. To the extent that the heuristics are * helpful, however, this will be a better plan than the raw tour. * ! * Also, when a join attempt fails (because of IN-clause constraints), we * may be able to recover and produce a workable plan, where the old code * just had to give up. This case acts the same as a false result from * desirable_join(). --- 182,188 ---- * tour other than the one given. To the extent that the heuristics are * helpful, however, this will be a better plan than the raw tour. * ! * Also, when a join attempt fails (because of OJ or IN constraints), we * may be able to recover and produce a workable plan, where the old code * just had to give up. This case acts the same as a false result from * desirable_join(). *************** *** 262,270 **** return true; /* ! * Join if the rels are members of the same outer-join side. This is ! * needed to ensure that we can find a valid solution in a case where ! * an OJ contains a clauseless join. */ foreach(l, root->oj_info_list) { --- 262,270 ---- return true; /* ! * Join if the rels overlap the same outer-join side and don't already ! * implement the outer join. This is needed to ensure that we can find a ! * valid solution in a case where an OJ contains a clauseless join. */ foreach(l, root->oj_info_list) { *************** *** 273,283 **** /* ignore full joins --- other mechanisms preserve their ordering */ if (ojinfo->is_full_join) continue; ! if (bms_is_subset(outer_rel->relids, ojinfo->min_righthand) && ! bms_is_subset(inner_rel->relids, ojinfo->min_righthand)) return true; ! if (bms_is_subset(outer_rel->relids, ojinfo->min_lefthand) && ! bms_is_subset(inner_rel->relids, ojinfo->min_lefthand)) return true; } --- 273,287 ---- /* ignore full joins --- other mechanisms preserve their ordering */ if (ojinfo->is_full_join) continue; ! if (bms_overlap(outer_rel->relids, ojinfo->min_righthand) && ! bms_overlap(inner_rel->relids, ojinfo->min_righthand) && ! !bms_overlap(outer_rel->relids, ojinfo->min_lefthand) && ! !bms_overlap(inner_rel->relids, ojinfo->min_lefthand)) return true; ! if (bms_overlap(outer_rel->relids, ojinfo->min_lefthand) && ! bms_overlap(inner_rel->relids, ojinfo->min_lefthand) && ! !bms_overlap(outer_rel->relids, ojinfo->min_righthand) && ! !bms_overlap(inner_rel->relids, ojinfo->min_righthand)) return true; } Index: src/backend/optimizer/path/joinrels.c =================================================================== RCS file: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v retrieving revision 1.81.2.1 diff -c -r1.81.2.1 joinrels.c *** src/backend/optimizer/path/joinrels.c 12 Dec 2006 21:31:09 -0000 1.81.2.1 --- src/backend/optimizer/path/joinrels.c 13 Feb 2007 02:21:36 -0000 *************** *** 350,357 **** /* ignore full joins --- other mechanisms preserve their ordering */ if (ojinfo->is_full_join) continue; ! /* anything inside the RHS is definitely restricted */ ! if (bms_is_subset(rel->relids, ojinfo->min_righthand)) return true; /* if it's a proper subset of the LHS, it's also restricted */ if (bms_is_subset(rel->relids, ojinfo->min_lefthand) && --- 350,358 ---- /* ignore full joins --- other mechanisms preserve their ordering */ if (ojinfo->is_full_join) continue; ! /* if it overlaps RHS and isn't yet joined to LHS, it's restricted */ ! if (bms_overlap(rel->relids, ojinfo->min_righthand) && ! !bms_overlap(rel->relids, ojinfo->min_lefthand)) return true; /* if it's a proper subset of the LHS, it's also restricted */ if (bms_is_subset(rel->relids, ojinfo->min_lefthand) && *************** *** 468,483 **** /*---------- * Otherwise, the proposed join overlaps the RHS but isn't * a valid implementation of this OJ. It might still be ! * a valid implementation of some other OJ, however. We have ! * to allow this to support the associative identity ! * (a LJ b on Pab) LJ c ON Pbc = a LJ (b LJ c ON Pbc) on Pab * since joining B directly to C violates the lower OJ's RHS. * We assume that make_outerjoininfo() set things up correctly ! * so that we'll only match to the upper OJ if the transformation ! * is valid. Set flag here to check at bottom of loop. *---------- */ ! is_valid_inner = false; } } --- 469,504 ---- /*---------- * Otherwise, the proposed join overlaps the RHS but isn't * a valid implementation of this OJ. It might still be ! * a legal join, however. If both inputs overlap the RHS, ! * assume that it's OK. Since the inputs presumably got past ! * this function's checks previously, they can't overlap the ! * LHS and their violations of the RHS boundary must represent ! * OJs that have been determined to commute with this one. ! * We have to allow this to work correctly in cases like ! * (a LEFT JOIN (b JOIN (c LEFT JOIN d))) ! * when the c/d join has been determined to commute with the join ! * to a, and hence d is not part of min_righthand for the upper ! * join. It should be legal to join b to c/d but this will appear ! * as a violation of the upper join's RHS. ! * Furthermore, if one input overlaps the RHS and the other does ! * not, we should still allow the join if it is a valid ! * implementation of some other OJ. We have to allow this to ! * support the associative identity ! * (a LJ b on Pab) LJ c ON Pbc = a LJ (b LJ c ON Pbc) on Pab * since joining B directly to C violates the lower OJ's RHS. * We assume that make_outerjoininfo() set things up correctly ! * so that we'll only match to some OJ if the join is valid. ! * Set flag here to check at bottom of loop. *---------- */ ! if (bms_overlap(rel1->relids, ojinfo->min_righthand) && ! bms_overlap(rel2->relids, ojinfo->min_righthand)) ! { ! /* seems OK */ ! Assert(!bms_overlap(joinrelids, ojinfo->min_lefthand)); ! } ! else ! is_valid_inner = false; } } Index: src/backend/optimizer/plan/initsplan.c =================================================================== RCS file: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v retrieving revision 1.123.2.2 diff -c -r1.123.2.2 initsplan.c *** src/backend/optimizer/plan/initsplan.c 8 Jan 2007 16:47:35 -0000 1.123.2.2 --- src/backend/optimizer/plan/initsplan.c 13 Feb 2007 02:21:36 -0000 *************** *** 373,379 **** /* * For an OJ, form the OuterJoinInfo now, because we need the OJ's ! * semantic scope (ojscope) to pass to distribute_qual_to_rels. */ if (j->jointype != JOIN_INNER) { --- 373,381 ---- /* * For an OJ, form the OuterJoinInfo now, because we need the OJ's ! * semantic scope (ojscope) to pass to distribute_qual_to_rels. But ! * we mustn't add it to oj_info_list just yet, because we don't want ! * distribute_qual_to_rels to think it is an outer join below us. */ if (j->jointype != JOIN_INNER) { *************** *** 454,461 **** * the caller, so that left_rels is always the nonnullable side. Hence * we need only distinguish the LEFT and FULL cases. * ! * The node should eventually be put into root->oj_info_list, but we * do not do that here. */ static OuterJoinInfo * make_outerjoininfo(PlannerInfo *root, --- 456,468 ---- * the caller, so that left_rels is always the nonnullable side. Hence * we need only distinguish the LEFT and FULL cases. * ! * The node should eventually be appended to root->oj_info_list, but we * do not do that here. + * + * Note: we assume that this function is invoked bottom-up, so that + * root->oj_info_list already contains entries for all outer joins that are + * syntactically below this one; and indeed that oj_info_list is ordered + * with syntactically lower joins listed first. */ static OuterJoinInfo * make_outerjoininfo(PlannerInfo *root,