Skip to content

Commit 0901d68

Browse files
tglsfdctglsfdc
committed
Fix another oversight in checking if a join with LATERAL refs is legal.
It was possible for the planner to decide to join a LATERAL subquery to the outer side of an outer join before the outer join itself is completed. Normally that's fine because of the associativity rules, but it doesn't work if the subquery contains a lateral reference to the inner side of the outer join. In such a situation the outer join *must* be done first. join_is_legal() missed this consideration and would allow the join to be attempted, but the actual path-building code correctly decided that no valid join path could be made, sometimes leading to planner errors such as "failed to build any N-way joins". Per report from Andreas Seltenreich. Back-patch to 9.3 where LATERAL support was added.
1 parent 0cc6bad commit 0901d68

File tree

5 files changed

+130
-0
lines changed

5 files changed

+130
-0
lines changed

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

+30
Original file line numberDiff line numberDiff line change
@@ -334,6 +334,7 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
334334
bool must_be_leftjoin;
335335
bool lateral_fwd;
336336
bool lateral_rev;
337+
Relids join_lateral_rels;
337338
ListCell *l;
338339

339340
/*
@@ -569,6 +570,35 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2,
569570
}
570571
}
571572

573+
/*
574+
* LATERAL references could also cause problems later on if we accept this
575+
* join: if the join's minimum parameterization includes any rels that
576+
* would have to be on the inside of an outer join with this join rel,
577+
* then it's never going to be possible to build the complete query using
578+
* this join. We should reject this join not only because it'll save
579+
* work, but because if we don't, the clauseless-join heuristics might
580+
* think that legality of this join means that some other join rel need
581+
* not be formed, and that could lead to failure to find any plan at all.
582+
* It seems best not to merge this check into the main loop above, because
583+
* it is concerned with SJs that are not otherwise relevant to this join.
584+
*/
585+
join_lateral_rels = min_join_parameterization(root, joinrelids);
586+
if (join_lateral_rels)
587+
{
588+
foreach(l, root->join_info_list)
589+
{
590+
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
591+
592+
if (bms_overlap(sjinfo->min_righthand, join_lateral_rels) &&
593+
bms_overlap(sjinfo->min_lefthand, joinrelids))
594+
return false; /* will not be able to join to min_righthand */
595+
if (sjinfo->jointype == JOIN_FULL &&
596+
bms_overlap(sjinfo->min_lefthand, join_lateral_rels) &&
597+
bms_overlap(sjinfo->min_righthand, joinrelids))
598+
return false; /* will not be able to join to min_lefthand */
599+
}
600+
}
601+
572602
/* Otherwise, it's a valid join */
573603
*sjinfo_p = match_sjinfo;
574604
*reversed_p = reversed;

‎src/backend/optimizer/util/relnode.c

+39
Original file line numberDiff line numberDiff line change
@@ -465,6 +465,45 @@ build_join_rel(PlannerInfo *root,
465465
return joinrel;
466466
}
467467

468+
/*
469+
* min_join_parameterization
470+
*
471+
* Determine the minimum possible parameterization of a joinrel, that is, the
472+
* set of other rels it contains LATERAL references to.
473+
*/
474+
Relids
475+
min_join_parameterization(PlannerInfo *root, Relids joinrelids)
476+
{
477+
Relids result;
478+
ListCell *lc;
479+
480+
/* Easy if there are no lateral references */
481+
if (root->lateral_info_list == NIL)
482+
return NULL;
483+
484+
/*
485+
* Scan lateral_info_list to find all the lateral references occurring in
486+
* or below this join.
487+
*/
488+
result = NULL;
489+
foreach(lc, root->lateral_info_list)
490+
{
491+
LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(lc);
492+
493+
if (bms_is_subset(ljinfo->lateral_rhs, joinrelids))
494+
result = bms_add_members(result, ljinfo->lateral_lhs);
495+
}
496+
497+
/* Remove any rels that are already included in the join */
498+
result = bms_del_members(result, joinrelids);
499+
500+
/* Maintain invariant that result is exactly NULL if empty */
501+
if (bms_is_empty(result))
502+
result = NULL;
503+
504+
return result;
505+
}
506+
468507
/*
469508
* build_joinrel_tlist
470509
* Builds a join relation's target list from an input relation.

‎src/include/optimizer/pathnode.h

+1
Original file line numberDiff line numberDiff line change
@@ -142,6 +142,7 @@ extern RelOptInfo *build_join_rel(PlannerInfo *root,
142142
RelOptInfo *inner_rel,
143143
SpecialJoinInfo *sjinfo,
144144
List **restrictlist_ptr);
145+
extern Relids min_join_parameterization(PlannerInfo *root, Relids joinrelids);
145146
extern RelOptInfo *build_empty_join_rel(PlannerInfo *root);
146147
extern AppendRelInfo *find_childrel_appendrelinfo(PlannerInfo *root,
147148
RelOptInfo *rel);

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

+41
Original file line numberDiff line numberDiff line change
@@ -3539,6 +3539,47 @@ select * from
35393539
doh! | 123 | 456 | hi de ho neighbor |
35403540
(2 rows)
35413541

3542+
--
3543+
-- test for appropriate join order in the presence of lateral references
3544+
--
3545+
explain (verbose, costs off)
3546+
select * from
3547+
text_tbl t1
3548+
left join int8_tbl i8
3549+
on i8.q2 = 123,
3550+
lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
3551+
where t1.f1 = ss.f1;
3552+
QUERY PLAN
3553+
--------------------------------------------------
3554+
Nested Loop
3555+
Output: t1.f1, i8.q1, i8.q2, (i8.q1), t2.f1
3556+
Join Filter: (t1.f1 = t2.f1)
3557+
-> Nested Loop Left Join
3558+
Output: t1.f1, i8.q1, i8.q2
3559+
-> Seq Scan on public.text_tbl t1
3560+
Output: t1.f1
3561+
-> Materialize
3562+
Output: i8.q1, i8.q2
3563+
-> Seq Scan on public.int8_tbl i8
3564+
Output: i8.q1, i8.q2
3565+
Filter: (i8.q2 = 123)
3566+
-> Limit
3567+
Output: (i8.q1), t2.f1
3568+
-> Seq Scan on public.text_tbl t2
3569+
Output: i8.q1, t2.f1
3570+
(16 rows)
3571+
3572+
select * from
3573+
text_tbl t1
3574+
left join int8_tbl i8
3575+
on i8.q2 = 123,
3576+
lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
3577+
where t1.f1 = ss.f1;
3578+
f1 | q1 | q2 | q1 | f1
3579+
------+------------------+-----+------------------+------
3580+
doh! | 4567890123456789 | 123 | 4567890123456789 | doh!
3581+
(1 row)
3582+
35423583
--
35433584
-- test ability to push constants through outer join clauses
35443585
--

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

+19
Original file line numberDiff line numberDiff line change
@@ -1099,6 +1099,25 @@ select * from
10991099
left join int4_tbl i4
11001100
on i8.q1 = i4.f1;
11011101

1102+
--
1103+
-- test for appropriate join order in the presence of lateral references
1104+
--
1105+
1106+
explain (verbose, costs off)
1107+
select * from
1108+
text_tbl t1
1109+
left join int8_tbl i8
1110+
on i8.q2 = 123,
1111+
lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
1112+
where t1.f1 = ss.f1;
1113+
1114+
select * from
1115+
text_tbl t1
1116+
left join int8_tbl i8
1117+
on i8.q2 = 123,
1118+
lateral (select i8.q1, t2.f1 from text_tbl t2 limit 1) as ss
1119+
where t1.f1 = ss.f1;
1120+
11021121
--
11031122
-- test ability to push constants through outer join clauses
11041123
--

0 commit comments

Comments
 (0)