8000 Further fixes for degenerate outer join clauses. · prmdeveloper/postgres@8703059 · GitHub
[go: up one dir, main page]
Skip to content

Commit 8703059

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 df0a67f commit 8703059

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
@@ -331,7 +331,7 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
331331
SpecialJoinInfo *match_sjinfo;
332332
bool reversed;
333333
bool unique_ified;
334-
bool is_valid_inner;
334+
bool must_be_leftjoin;
335335
bool lateral_fwd;
336336
bool lateral_rev;
337337
ListCell *l;
@@ -346,12 +346,12 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
346346
/*
347347
* If we have any special joins, the proposed join might be illegal; and
348348
* in any case we have to determine its join type. Scan the join info
349-
* list for conflicts.
349+
* list for matches and conflicts.
350350
*/
351351
match_sjinfo = NULL;
352352
reversed = false;
353353
unique_ified = false;
354-
is_valid_inner = true;
354+
must_be_leftjoin = false;
355355

356356
foreach(l, root->join_info_list)
357357
{
@@ -402,7 +402,8 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
402402
* If one input contains min_lefthand and the other contains
403403
* min_righthand, then we can perform the SJ at this join.
404404
*
405-
* Barf if we get matches to more than one SJ (is that possible?)
405+
* Reject if we get matches to more than one SJ; that implies we're
406+
* considering something that's not really valid.
406407
*/
407408
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
408409
bms_is_subset(sjinfo->min_righthand, rel2->relids))
@@ -470,58 +471,38 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
470471
/*
471472
* Otherwise, the proposed join overlaps the RHS but isn't a valid
472473
* implementation of this SJ. It might still be a legal join,
473-
* however, if it does not overlap the LHS. But we never allow
474-
* violations of the RHS of SEMI or ANTI joins. (In practice,
475-
* therefore, only LEFT joins ever allow RHS violation.)
474+
* however, if we're allowed to associate it into the RHS of this
475+
* SJ. That means this SJ must be a LEFT join (not SEMI or ANTI,
476+
* and certainly not FULL) and the proposed join must not overlap
477+
* the LHS.
476478
*/
477-
if (sjinfo->jointype == JOIN_SEMI ||
478-
sjinfo->jointype == JOIN_ANTI ||
479+
if (sjinfo->jointype != JOIN_LEFT ||
479480
bms_overlap(joinrelids, sjinfo->min_lefthand))
480481
return false; /* invalid join path */
481482

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

518493
/*
519-
* Fail if violated some SJ's RHS and didn't match to another SJ. However,
520-
* "matching" to a semijoin we are implementing by unique-ification
521-
* doesn't count (think: it's really an inner join).
494+
* Fail if violated any SJ's RHS and didn't match to a LEFT SJ: the
495+
* proposed join can't associate into an SJ's RHS.
496+
*
497+
* Also, fail if the proposed join's predicate isn't strict; we're
498+
* essentially checking to see if we can apply outer-join identity 3, and
499+
* that's a requirement. (This check may be redundant with checks in
500+
* make_outerjoininfo, but I'm not quite sure, and it's cheap to test.)
522501
*/
523-
if (!is_valid_inner &&
524-
(match_sjinfo == NULL || unique_ified))
502+
if (must_be_leftjoin &&
503+
(match_sjinfo == NULL ||
504+
match_sjinfo->jointype != JOIN_LEFT ||
505+
!match_sjinfo->lhs_strict))
525506
return false; /* invalid join path */
526507

527508
/*

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

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

1131-
/*
1132-
* If we have a dege F987 nerate join clause that doesn't mention any RHS rels,
1133-
* force the min RHS to be the syntactic RHS; otherwise we can end up
1134-
* making serious errors, like putting the LHS on the wrong side of an
1135-
* outer join. It seems to be safe to not do this when we have a
1136-
* contribution from inner_join_rels, though; that's enough to pin the SJ
1137-
* to occur at a reasonable place in the tree.
1138-
*/
1139-
if (bms_is_empty(min_righthand))
1140-
min_righthand = bms_copy(right_rels);
1141-
11421131
/*
11431132
* Now check previous outer joins for ordering restrictions.
11441133
*/
@@ -1181,9 +1170,15 @@ make_outerjoininfo(PlannerInfo *root,
11811170
* For a lower OJ in our RHS, if our join condition does not use the
11821171
* lower join's RHS and the lower OJ's join condition is strict, we
11831172
* can interchange the ordering of the two OJs; otherwise we must add
1184-
* the lower OJ's full syntactic relset to min_righthand. Also, we
1185-
* must preserve ordering anyway if either the current join or the
1186-
* lower OJ is either a semijoin or an antijoin.
1173+
* the lower OJ's full syntactic relset to min_righthand.
1174+
*
1175+
* Also, if our join condition does not use the lower join's LHS
1176+
* either, force the ordering to be preserved. Otherwise we can end
1177+
* up with SpecialJoinInfos with identical min_righthands, which can
1178+
* confuse join_is_legal (see discussion in backend/optimizer/README).
1179+
*
1180+
* Also, we must preserve ordering anyway if either the current join
1181+
* or the lower OJ is either a semijoin or an antijoin.
11871182
*
11881183
* Here, we have to consider that "our join condition" includes any
11891184
* clauses that syntactically appeared above the lower OJ and below
@@ -1199,6 +1194,7 @@ make_outerjoininfo(PlannerInfo *root,
11991194
if (bms_overlap(right_rels, otherinfo->syn_righthand))
12001195
{
12011196
if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
1197+
!bms_overlap(clause_relids, otherinfo->min_leftha 1241 nd) ||
12021198
jointype == JOIN_SEMI ||
12031199
jointype == JOIN_ANTI ||
12041200
otherinfo->jointype == JOIN_SEMI ||
@@ -1238,10 +1234,12 @@ make_outerjoininfo(PlannerInfo *root,
12381234
* If we found nothing to put in min_lefthand, punt and make it the full
12391235
* LHS, to avoid having an empty min_lefthand which will confuse later
12401236
* processing. (We don't try to be smart about such cases, just correct.)
1241-
* We already forced min_righthand nonempty, so nothing to do for that.
1237+
* Likewise for min_righthand.
12421238
*/
12431239
if (bms_is_empty(min_lefthand))
12441240
min_lefthand = bms_copy(left_rels);
1241+
if (bms_is_empty(min_righthand))
1242+
min_righthand = bms_copy(right_rels);
12451243

12461244
/* Now they'd better be nonempty */
12471245
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
@@ -3425,7 +3425,7 @@ select t1.* from
34253425
Output: t1.f1
34263426
Hash Cond: (i8.q2 = i4.f1)
34273427
-> Nested Loop Left Join
3428-
Output: i8.q2, t1.f1
3428+
Output: t1.f1, i8.q2
34293429
Join Filter: (t1.f1 = '***'::text)
34303430
-> Seq Scan on public.text_tbl t1
34313431
Output: t1.f1
@@ -3473,6 +3473,76 @@ select t1.* from
34733473
hi de ho neighbor
34743474
(2 rows)
34753475

3476+
explain (verbose, costs off)
3477+
select t1.* from
3478+
text_tbl t1
3479+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
3480+
left join int8_tbl i8
3481+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
3482+
where q1 = f1) b2
3483+
on (i8.q1 = b2.q1)
3484+
on (b2.d2 = b1.q2)
3485+
on (t1.f1 = b1.d1)
3486+
left join int4_tbl i4
3487+
on (i8.q2 = i4.f1);
3488+
QUERY PLAN
3489+
----------------------------------------------------------------------------
3490+
Hash Left Join
3491+
Output: t1.f1
3492+
Hash Cond: (i8.q2 = i4.f1)
3493+
-> Nested Loop Left Join
3494+
Output: t1.f1, i8.q2
3495+
Join Filter: (t1.f1 = '***'::text)
3496+
-> Seq Scan on public.text_tbl t1
3497+
Output: t1.f1
3498+
-> Materialize
3499+
Output: i8.q2
3500+
-> Hash Right Join
3501+
Output: i8.q2
3502+
Hash Cond: ((NULL::integer) = i8b1.q2)
3503+
-> Hash Right Join
3504+
Output: i8.q2, (NULL::integer)
3505+
Hash Cond: (i8b2.q1 = i8.q1)
3506+
-> Hash Join
3507+
Output: i8b2.q1, NULL::integer
3508+
Hash Cond: (i8b2.q1 = i4b2.f1)
3509+
-> Seq Scan on public.int8_tbl i8b2
3510+
Output: i8b2.q1, i8b2.q2
3511+
-> Hash
3512+
Output: i4b2.f1
3513+
-> Seq Scan on public.int4_tbl i4b2
3514+
Output: i4b2.f1
3515+
-> Hash
3516+
Output: i8.q1, i8.q2
3517+
-> Seq Scan on public.int8_tbl i8
3518+
Output: i8.q1, i8.q2
3519+
-> Hash
3520+
Output: i8b1.q2
3521+
-> Seq Scan on public.int8_tbl i8b1
3522+
Output: i8b1.q2
3523+
-> Hash
3524+
Output: i4.f1
3525+
-> Seq Scan on public.int4_tbl i4
3526+
Output: i4.f1
3527+
(37 rows)
3528+
3529+
select t1.* from
3530+
text_tbl t1
3531+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
3532+
left join int8_tbl i8
3533+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
3534+
where q1 = f1) b2
3535+
on (i8.q1 = b2.q1)
3536+
on (b2.d2 = b1.q2)
3537+
on (t1.f1 = b1.d1)
3538+
left join int4_tbl i4
3539+
on (i8.q2 = i4.f1);
3540+
f1
3541+
-------------------
3542+
doh!
3543+
hi de ho neighbor
3544+
(2 rows)
3545+
34763546
--
34773547
-- test ability to push constants through outer join clauses
34783548
--

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

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

1068+
explain (verbose, costs off)
1069+
select t1.* from
1070+
text_tbl t1
1071+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
1072+
left join int8_tbl i8
1073+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
1074+
where q1 = f1) b2
1075+
on (i8.q1 = b2.q1)
1076+
on (b2.d2 = b1.q2)
1077+
on (t1.f1 = b1.d1)
1078+
left join int4_tbl i4
1079+
on (i8.q2 = i4.f1);
1080+
1081+
select t1.* from
1082+
text_tbl t1
1083+
left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
1084+
left join int8_tbl i8
1085+
left join (select *, null::int as d2 from int8_tbl i8b2, int4_tbl i4b2
1086+
where q1 = f1) b2
1087+
on (i8.q1 = b2.q1)
1088+
on (b2.d2 = b1.q2)
1089+
on (t1.f1 = b1.d1)
1090+
left join int4_tbl i4
1091+
on (i8.q2 = i4.f1);
1092+
10681093
--
10691094
-- test ability to push constants through outer join clauses
10701095
--

0 commit comments

Comments
 (0)
0