Обсуждение: Bug in planner
Hi!
I faced with planner error:
ERROR: could not find RelOptInfo for given relids
A test case is in attachment, all supported versions of pgsql and HEAD are
affected.
Suppose, there is something wrong in pull_up_sublinks_qual_recurse() near
converting NOT EXISTS into join, because preventing such convertion makes query
worked. But I'm not sure.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/
Вложения
On 24 April 2015 at 21:43, Teodor Sigaev <teodor@sigaev.ru> wrote:
Hi!
I faced with planner error:
ERROR: could not find RelOptInfo for given relids
Good find!
I've simplified your query a bit, the following still shows the issue (using your schema):
SELECT *
FROM t1
WHERE NOT EXISTS (SELECT t2.c2 AS c1
FROM t2
LEFT OUTER JOIN t3 ON t2.c3 = t3.c1
LEFT OUTER JOIN (SELECT t5.c1 AS c1
FROM t4
LEFT OUTER JOIN t5 ON t4.c2 = t5.c1 --offset 0
) a1 ON a1.c1 = t3.c2
WHERE t1.c1 = t2.c2
);
I've done a little debugging on this too and I get the idea that in eqjoinsel() that min_righthand incorrectly does not have a bit set for "t3"
When the failing call is made to find_join_rel() with the above query relids being searched for has a decimal value of 388 (binary 110000100 i.e t5, t4, t2)
find_join_rel makes a pass over join_rel_list to search for the 388 valued relids.
join_rel_list contains the following:
1 -> 396 (110001100) t5, t4, t3, t2
2 -> 384 (110000000) t5, t4
3 -> 392 (110001000) t5, t4, t3
4 -> 396 (110001100) t5, t4, t3, t2
I looked up simple_rte_array to determine which bits are for which relation.
simple_rte_array:
1 -> t1
2 -> t2
3 -> t3
4 -> join
5 -> a1
6 -> join
7 -> t4
8 -> t5
I'd imagine that the find_join_input_rel() search should actually be for relids 396. I need to spend more time in this area to get a better grasp of what's actually meant to be happening, but I think the problem lies in make_outerjoininfo() when it determines what min_righthand should be set to with the following:
/*
* Similarly for required RHS. But here, we must also include any lower
* inner joins, to ensure we don't try to commute with any of them.
*/
min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
right_rels);
I think the problem seems to be down to the fact that inner_join_rels and clause_relids are built from deconstruct_jointree() which I'd imagine does not get modified when the subquery for t4 and t5 is pulled up, therefore is out-of-date. </theory>
I've attached a patch which appears to fix the problem, but this is more for the purposes of a demonstration of where the problem lies. I don't have enough knowledge of what's meant to be happening here, I'll need to spend more time reading code and debugging.
On a side note, I just discovered another join removal opportunity:
explain select * from t1 where not exists(select 1 from t2 left join t3 on t2.c1 = t3.c1 where t1.c1=t2.c1);
The join to t3 here is useless, as since it's a left join, the join could only cause duplication of t2 rows, and this does not matter as we're performing an anti join anyway (same applies for semi join).
Regards
David Rowley
Вложения
David Rowley <dgrowleyml@gmail.com> writes:
> On 24 April 2015 at 21:43, Teodor Sigaev <teodor@sigaev.ru> wrote:
>> I faced with planner error:
>> ERROR: could not find RelOptInfo for given relids
> I've done a little debugging on this too and I get the idea that in
> eqjoinsel() that min_righthand incorrectly does not have a bit set for "t3"
Yeah. The short of it seems to be that initsplan.c is too optimistic
about whether antijoins can be reordered against outer joins in their RHS.
The discussion in optimizer/README says pretty clearly that they can't
(and eqjoinsel is relying on that, per the comment therein), so I think
this is basically brain fade in translating that logic to code.
regards, tom lane
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index a7655e4..00b2625 100644
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
*************** make_outerjoininfo(PlannerInfo *root,
*** 1165,1173 ****
* For a lower OJ in our RHS, if our join condition does not use the
* lower join's RHS and the lower OJ's join condition is strict, we
* can interchange the ordering of the two OJs; otherwise we must add
! * lower OJ's full syntactic relset to min_righthand. Here, we must
! * preserve ordering anyway if either the current join is a semijoin,
! * or the lower OJ is either a semijoin or an antijoin.
*
* Here, we have to consider that "our join condition" includes any
* clauses that syntactically appeared above the lower OJ and below
--- 1165,1173 ----
* For a lower OJ in our RHS, if our join condition does not use the
* lower join's RHS and the lower OJ's join condition is strict, we
* can interchange the ordering of the two OJs; otherwise we must add
! * the lower OJ's full syntactic relset to min_righthand. Also, we
! * must preserve ordering anyway if either the current join or the
! * lower OJ is either a semijoin or an antijoin.
*
* Here, we have to consider that "our join condition" includes any
* clauses that syntactically appeared above the lower OJ and below
*************** make_outerjoininfo(PlannerInfo *root,
*** 1184,1189 ****
--- 1184,1190 ----
{
if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
jointype == JOIN_SEMI ||
+ jointype == JOIN_ANTI ||
otherinfo->jointype == JOIN_SEMI ||
otherinfo->jointype == JOIN_ANTI ||
!otherinfo->lhs_strict || otherinfo->delay_upper_joins)
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index e4f3f22..ed9ad0e 100644
*** a/src/test/regress/expected/join.out
--- b/src/test/regress/expected/join.out
*************** WHERE d.f1 IS NULL;
*** 2284,2289 ****
--- 2284,2331 ----
(3 rows)
--
+ -- regression test for proper handling of outer joins within antijoins
+ --
+ create temp table tt4x(c1 int, c2 int, c3 int);
+ explain (costs off)
+ select * from tt4x t1
+ where not exists (
+ select 1 from tt4x t2
+ left join tt4x t3 on t2.c3 = t3.c1
+ left join ( select t5.c1 as c1
+ from tt4x t4 left join tt4x t5 on t4.c2 = t5.c1
+ ) a1 on t3.c2 = a1.c1
+ where t1.c1 = t2.c2
+ );
+ QUERY PLAN
+ ---------------------------------------------------------
+ Hash Anti Join
+ Hash Cond: (t1.c1 = t2.c2)
+ -> Seq Scan on tt4x t1
+ -> Hash
+ -> Merge Right Join
+ Merge Cond: (t5.c1 = t3.c2)
+ -> Merge Join
+ Merge Cond: (t4.c2 = t5.c1)
+ -> Sort
+ Sort Key: t4.c2
+ -> Seq Scan on tt4x t4
+ -> Sort
+ Sort Key: t5.c1
+ -> Seq Scan on tt4x t5
+ -> Sort
+ Sort Key: t3.c2
+ -> Merge Left Join
+ Merge Cond: (t2.c3 = t3.c1)
+ -> Sort
+ Sort Key: t2.c3
+ -> Seq Scan on tt4x t2
+ -> Sort
+ Sort Key: t3.c1
+ -> Seq Scan on tt4x t3
+ (24 rows)
+
+ --
-- regression test for problems of the sort depicted in bug #3494
--
create temp table tt5(f1 int, f2 int);
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d0cf0a0..5b65ea8 100644
*** a/src/test/regress/sql/join.sql
--- b/src/test/regress/sql/join.sql
*************** LEFT JOIN (
*** 448,453 ****
--- 448,470 ----
WHERE d.f1 IS NULL;
--
+ -- regression test for proper handling of outer joins within antijoins
+ --
+
+ create temp table tt4x(c1 int, c2 int, c3 int);
+
+ explain (costs off)
+ select * from tt4x t1
+ where not exists (
+ select 1 from tt4x t2
+ left join tt4x t3 on t2.c3 = t3.c1
+ left join ( select t5.c1 as c1
+ from tt4x t4 left join tt4x t5 on t4.c2 = t5.c1
+ ) a1 on t3.c2 = a1.c1
+ where t1.c1 = t2.c2
+ );
+
+ --
-- regression test for problems of the sort depicted in bug #3494
--