Skip to content

Commit d860ba4

Browse files
tglsfdctglsfdc
committed
Further fixes for degenerate outer join clauses.
Further testing revealed that commit f69b4b9 was still a few bricks shy of a load: minor tweaking of the previous test cases resulted in the same wrong-outer-join-order problem coming back. After study I concluded that my previous changes in make_outerjoininfo() were just accidentally masking the problem, and should be reverted in favor of forcing syntactic join order whenever an upper outer join's predicate doesn't mention a lower outer join's LHS. This still allows the chained-outer-joins style that is the normally optimizable case. I also tightened things up some more in join_is_legal(). It seems to me on review that what's really happening in the exception case where we ignore a mismatched special join is that we're allowing the proposed join to associate into the RHS of the outer join we're comparing it to. As such, we should *always* insist that the proposed join be a left join, which eliminates a bunch of rather dubious argumentation. The case where we weren't enforcing that was the one that was already known buggy anyway (it had a violatable Assert before the aforesaid commit) so it hardly deserves a lot of deference. Back-patch to all active branches, like the previous patch. The added regression test case failed in all branches back to 9.1, and I think it's only an unrelated change in costing calculations that kept 9.0 from choosing a broken plan.
1 parent c084f61 commit d860ba4

File tree

5 files changed

+153
-68
lines changed

5 files changed

+153
-68
lines changed

‎src/backend/optimizer/README

Lines changed: 17 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -241,12 +241,23 @@ non-FULL joins can be freely associated into the lefthand side of an
241241
OJ, but in some cases they can't be associated into the righthand side.
242242
So the restriction enforced by join_is_legal is that a proposed join
243243
can't join a rel within or partly within an RHS boundary to one outside
244-
the boundary, unless the join validly implements some outer join.
245-
(To support use of identity 3, we have to allow cases where an apparent
246-
violation of a lower OJ's RHS is committed while forming an upper OJ.
247-
If this wouldn't in fact be legal, the upper OJ's minimum LHS or RHS
248-
set must be expanded to include the whole of the lower OJ, thereby
249-
preventing it from being formed before the lower OJ is.)
244+
the boundary, unless the proposed join is a LEFT join that can associate
245+
into the SpecialJoinInfo's RHS using identity 3.
246+
247+
The use of minimum Relid sets has some pitfalls; consider a query like
248+
A leftjoin (B leftjoin (C innerjoin D) on (Pbcd)) on Pa
249+
where Pa doesn't mention B/C/D at all. In this case a naive computation
250+
would give the upper leftjoin's min LHS as {A} and min RHS as {C,D} (since
251+
we know that the innerjoin can't associate out of the leftjoin's RHS, and
252+
enforce that by including its relids in the leftjoin's min RHS). And the
253+
lower leftjoin has min LHS of {B} and min RHS of {C,D}. Given such
254+
information, join_is_legal would think it's okay to associate the upper
255+
join into the lower join's RHS, transforming the query to
256+
B leftjoin (A leftjoin (C innerjoin D) on Pa) on (Pbcd)
257+
which yields totally wrong answers. We prevent that by forcing the min LHS
258+
for the upper join to include B. This is perhaps overly restrictive, but
259+
such cases don't arise often so it's not clear that it's worth developing a
260+
more complicated system.
250261

251262

252263
Pulling Up Subqueries

‎src/backend/optimizer/path/joinrels.c

Lines changed: 27 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -325,7 +325,7 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
325325
SpecialJoinInfo *match_sjinfo;
326326
bool reversed;
327327
bool unique_ified;
328-
bool is_valid_inner;
328+
bool must_be_leftjoin;
329329
ListCell *l;
330330

331331
/*
@@ -338,12 +338,12 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
338338
/*
339339
* If we have any special joins, the proposed join might be illegal; and
340340
* in any case we have to determine its join type. Scan the join info
341-
* list for conflicts.
341+
* list for matches and conflicts.
342342
*/
343343
match_sjinfo = NULL;
344344
reversed = false;
345345
unique_ified = false;
346-
is_valid_inner = true;
346+
must_be_leftjoin = false;
347347

348348
foreach(l, root->join_info_list)
349349
{
@@ -394,7 +394,8 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
394394
* If one input contains min_lefthand and the other contains
395395
* min_righthand, then we can perform the SJ at this join.
396396
*
397-
* Barf if we get matches to more than one SJ (is that possible?)
397+
* Reject if we get matches to more than one SJ; that implies we're
398+
* considering something that's not really valid.
398399
*/
399400
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
400401
bms_is_subset(sjinfo->min_righthand, rel2->relids))
@@ -462,58 +463,38 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
462463
/*
463464
* Otherwise, the proposed join overlaps the RHS but isn't a valid
464465
* implementation of this SJ. It might still be a legal join,
465-
* however, if it does not overlap the LHS. But we never allow
466-
* violations of the RHS of SEMI or ANTI joins. (In practice,
467-
* therefore, only LEFT joins ever allow RHS violation.)
466+
* however, if we're allowed to associate it into the RHS of this
467+
* SJ. That means this SJ must be a LEFT join (not SEMI or ANTI,
468+
* and certainly not FULL) and the proposed join must not overlap
469+
* the LHS.
468470
*/
469-
if (sjinfo->jointype == JOIN_SEMI ||
470-
sjinfo->jointype == JOIN_ANTI ||
471+
if (sjinfo->jointype != JOIN_LEFT ||
471472
bms_overlap(joinrelids, sjinfo->min_lefthand))
472473
return false; /* invalid join path */
473474

474-
/*----------
475-
* If both inputs overlap the RHS, assume that it's OK. Since the
476-
* inputs presumably got past this function's checks previously,
477-
* their violations of the RHS boundary must represent SJs that
478-
* have been determined to commute with this one.
479-
* We have to allow this to work correctly in cases like
480-
* (a LEFT JOIN (b JOIN (c LEFT JOIN d)))
481-
* when the c/d join has been determined to commute with the join
482-
* to a, and hence d is not part of min_righthand for the upper
483-
* join. It should be legal to join b to c/d but this will appear
484-
* as a violation of the upper join's RHS.
485-
*
486-
* Furthermore, if one input overlaps the RHS and the other does
487-
* not, we should still allow the join if it is a valid
488-
* implementation of some other SJ. We have to allow this to
489-
* support the associative identity
490-
* (a LJ b on Pab) LJ c ON Pbc = a LJ (b LJ c ON Pbc) on Pab
491-
* since joining B directly to C violates the lower SJ's RHS.
492-
* We assume that make_outerjoininfo() set things up correctly
493-
* so that we'll only match to some SJ if the join is valid.
494-
* Set flag here to check at bottom of loop.
495-
*----------
475+
/*
476+
* To be valid, the proposed join must be a LEFT join; otherwise
477+
* it can't associate into this SJ's RHS. But we may not yet have
478+
* found the SpecialJoinInfo matching the proposed join, so we
479+
* can't test that yet. Remember the requirement for later.
496480
*/
497-
if (bms_overlap(rel1->relids, sjinfo->min_righthand) &&
498-
bms_overlap(rel2->relids, sjinfo->min_righthand))
499-
{
500-
/* both overlap; assume OK */
501-
}
502-
else
503-
{
504-
/* one overlaps, the other doesn't */
505-
is_valid_inner = false;
506-
}
481+
must_be_leftjoin = true;
507482
}
508483
}
509484

510485
/*
511-
* Fail if violated some SJ's RHS and didn't match to another SJ. However,
512-
* "matching" to a semijoin we are implementing by unique-ification
513-
* doesn't count (think: it's really an inner join).
486+
* Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
487+
* proposed join can't associate into an SJ's RHS.
488+
*
489+
* Also, fail if the proposed join's predicate isn't strict; we're
490+
* essentially checking to see if we can apply outer-join identity 3, and
491+
* that's a requirement. (This check may be redundant with checks in
492+
* make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
514493
*/
515-
if (!is_valid_inner &&
516-
(match_sjinfo == NULL || unique_ified))
494+
if (must_be_leftjoin &&
495+
(match_sjinfo == NULL ||
496+
match_sjinfo->jointype != JOIN_LEFT ||
497+
!match_sjinfo->lhs_strict))
517498
return false; /* invalid join path */
518499

519500
/* Otherwise, it's a valid join */

‎src/backend/optimizer/plan/initsplan.c

Lines changed: 13 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -638,17 +638,6 @@ make_outerjoininfo(PlannerInfo *root,
638638
min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
639639
right_rels);
640640

641-
/*
642-
* If we have a degenerate join clause that doesn't mention any RHS rels,
643-
* force the min RHS to be the syntactic RHS; otherwise we can end up
644-
* making serious errors, like putting the LHS on the wrong side of an
645-
* outer join. It seems to be safe to not do this when we have a
646-
* contribution from inner_join_rels, though; that's enough to pin the SJ
647-
* to occur at a reasonable place in the tree.
648-
*/
649-
if (bms_is_empty(min_righthand))
650-
min_righthand = bms_copy(right_rels);
651-
652641
/*
653642
* Now check previous outer joins for ordering restrictions.
654643
*/
@@ -691,9 +680,15 @@ make_outerjoininfo(PlannerInfo *root,
691680
* For a lower OJ in our RHS, if our join condition does not use the
692681
* lower join's RHS and the lower OJ's join condition is strict, we
693682
* can interchange the ordering of the two OJs; otherwise we must add
694-
* the lower OJ's full syntactic relset to min_righthand. Also, we
695-
* must preserve ordering anyway if either the current join or the
696-
* lower OJ is either a semijoin or an antijoin.
683+
* the lower OJ's full syntactic relset to min_righthand.
684+
*
685+
* Also, if our join condition does not use the lower join's LHS
686+
* either, force the ordering to be preserved. Otherwise we can end
687+
* up with SpecialJoinInfos with identical min_righthands, which can
688+
* confuse join_is_legal (see discussion in backend/optimizer/README).
689+
*
690+
* Also, we must preserve ordering anyway if either the current join
691+
* or the lower OJ is either a semijoin or an antijoin.
697692
*
698693
* Here, we have to consider that "our join condition" includes any
699694
* clauses that syntactically appeared above the lower OJ and below
@@ -709,6 +704,7 @@ make_outerjoininfo(PlannerInfo *root,
709704
if (bms_overlap(right_rels, otherinfo->syn_righthand))
710705
{
711706
if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
707+
!bms_overlap(clause_relids, otherinfo->min_lefthand) ||
712708
jointype == JOIN_SEMI ||
713709
jointype == JOIN_ANTI ||
714710
otherinfo->jointype == JOIN_SEMI ||
@@ -753,10 +749,12 @@ make_outerjoininfo(PlannerInfo *root,
753749
* If we found nothing to put in min_lefthand, punt and make it the full
754750
* LHS, to avoid having an empty min_lefthand which will confuse later
755751
* processing. (We don't try to be smart about such cases, just correct.)
756-
* We already forced min_righthand nonempty, so nothing to do for that.
752+
* Likewise for min_righthand.
757753
*/
758754
if (bms_is_empty(min_lefthand))
759755
min_lefthand = bms_copy(left_rels);
756+
if (bms_is_empty(min_righthand))
757+
min_righthand = bms_copy(right_rels);
760758

761759
/* Now they'd better be nonempty */
762760
Assert(!bms_is_empty(min_lefthand));

‎src/test/regress/expected/join.out

Lines changed: 71 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2847,7 +2847,7 @@ select t1.* from
28472847
Output: t1.f1
28482848
Hash Cond: (i8.q2 = i4.f1)
28492849
-> Nested Loop Left Join
2850-
Output: i8.q2, t1.f1
2850+
Output: t1.f1, i8.q2
28512851
Join Filter: (t1.f1 = '***'::text)
28522852
-> Seq Scan on public.text_tbl t1
28532853
Output: t1.f1
@@ -2895,6 +2895,76 @@ select t1.* from
28952895
hi de ho neighbor
28962896
(2 rows)
28972897

2898+
explain (verbose, costs off)
2899+
select t1.* from
2900+
text_tbl t1
2901+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
2902+
left join int8_tbl i8
2903+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
2904+
where q1 = f1) b2
2905+
on (i8.q1 = b2.q1)
2906+
on (b2.d2 = b1.q2)
2907+
on (t1.f1 = b1.d1)
2908+
left join int4_tbl i4
2909+
on (i8.q2 = i4.f1);
2910+
QUERY PLAN
2911+
----------------------------------------------------------------------------------------
2912+
Hash Left Join
2913+
Output: t1.f1
2914+
Hash Cond: (i8.q2 = i4.f1)
2915+
-> Nested Loop Left Join
2916+
Output: t1.f1, i8.q2
2917+
Join Filter: (t1.f1 = '***'::text)
2918+
-> Seq Scan on public.text_tbl t1
2919+
Output: t1.f1
2920+
-> Materialize
2921+
Output: i8.q2
2922+
-> Hash Left Join
2923+
Output: i8.q2
2924+
Hash Cond: (i8b1.q2 = (NULL::integer))
2925+
-> Seq Scan on public.int8_tbl i8b1
2926+
Output: i8b1.q1, i8b1.q2
2927+
-> Hash
2928+
Output: i8.q2, (NULL::integer)
2929+
-> Hash Left Join
2930+
Output: i8.q2, (NULL::integer)
2931+
Hash Cond: (i8.q1 = i8b2.q1)
2932+
-> Seq Scan on public.int8_tbl i8
2933+
Output: i8.q1, i8.q2
2934+
-> Hash
2935+
Output: i8b2.q1, (NULL::integer)
2936+
-> Hash Join
2937+
Output: i8b2.q1, NULL::integer
2938+
Hash Cond: (i8b2.q1 = i4b2.f1)
2939+
-> Seq Scan on public.int8_tbl i8b2
2940+
Output: i8b2.q1, i8b2.q2
2941+
-> Hash
2942+
Output: i4b2.f1
2943+
-> Seq Scan on public.int4_tbl i4b2
2944+
Output: i4b2.f1
2945+
-> Hash
2946+
Output: i4.f1
2947+
-> Seq Scan on public.int4_tbl i4
2948+
Output: i4.f1
2949+
(37 rows)
2950+
2951+
select t1.* from
2952+
text_tbl t1
2953+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
2954+
left join int8_tbl i8
2955+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
2956+
where q1 = f1) b2
2957+
on (i8.q1 = b2.q1)
2958+
on (b2.d2 = b1.q2)
2959+
on (t1.f1 = b1.d1)
2960+
left join int4_tbl i4
2961+
on (i8.q2 = i4.f1);
2962+
f1
2963+
-------------------
2964+
doh!
2965+
hi de ho neighbor
2966+
(2 rows)
2967+
28982968
--
28992969
-- test ability to push constants through outer join clauses
29002970
--

‎src/test/regress/sql/join.sql

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -786,6 +786,31 @@ select t1.* from
786786
left join int4_tbl i4
787787
on (i8.q2 = i4.f1);
788788

789+
explain (verbose, costs off)
790+
select t1.* from
791+
text_tbl t1
792+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
793+
left join int8_tbl i8
794+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
795+
where q1 = f1) b2
796+
on (i8.q1 = b2.q1)
797+
on (b2.d2 = b1.q2)
798+
on (t1.f1 = b1.d1)
799+
left join int4_tbl i4
800+
on (i8.q2 = i4.f1);
801+
802+
select t1.* from
803+
text_tbl t1
804+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
805+
left join int8_tbl i8
806+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
807+
where q1 = f1) b2
808+
on (i8.q1 = b2.q1)
809+
on (b2.d2 = b1.q2)
810+
on (t1.f1 = b1.d1)
811+
left join int4_tbl i4
812+
on (i8.q2 = i4.f1);
813+
789814
--
790815
-- test ability to push constants through outer join clauses
791816
--

0 commit comments

Comments
 (0)