[DERBY-4471] Left outer join reassociation rewrite gives wrong result

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 10.0.2.0, 10.0.2.1, 10.1.1.0, 10.1.2.1, 10.1.3.1, 10.2.1.6, 10.2.2.0, 10.3.1.4, 10.3.2.1, 10.3.3.0, 10.4.1.3, 10.4.2.0, 10.5.1.1, 10.5.2.0, 10.5.3.0
• Fix Version/s: 10.6.2.1, 10.7.1.1
• Component/s: SQL
• Labels: derby_backport_reject_10_5
• Bug behavior facts: Wrong query result
• Assignee: Dag H. Wanvik
• Reporter: Dag H. Wanvik
• Created: 12/Dec/09 00:35
• Updated: 23/Mar/11 14:45
• Resolved: 23/Mar/11 14:45

Description

The following script and output shows the problem:

> create table r(c1 char(1));
> create table s(c1 char(1), c2 char(1));
> create table t(c1 char(1));

> insert into r values 'a';
> insert into s values ('b', default);
> insert into t values ('c');

> select * from s left outer join t on s.c2=t.c1 or s.c2 is null;

C1 |C2 |C1
--------------
b |NULL|c

> select * from r left outer join s on r.c1=s.c1;
C1 |C1 |C2
--------------
a |NULL|NULL

> select * from (r left outer join s on r.c1=s.c1) left outer join t on s.c2=t.c1 or s.c2 is null;

C1 |C1 |C2 |C1
-------------------
a |NULL|NULL|c

> select * from r left outer join (s left outer join t on s.c2=t.c1 or s.c2 is null) on r.c1=s.c1;

C1 |C1 |C2 |C1
-------------------
a |NULL|NULL|c

The last result is wrong. The correct answer should be:

C1 |C1 |C2 |C1
-------------------
a |NULL|NULL|NULL

since in the last form, the left table r has the value 'a', which does
not match any row in result of the compound inner given the join
predicate ("r.c1=s.c1"), so all nulls should be appended to the 'a'
from the outer table r.

This happens because internally the last form is rewritten to the
second but the last form (left-deep), but this rewrite is not
justified here unless the join predicate on s rejects null, which the
present one explicitly does not ("or s.c2 is null"). Cf. for example
[1], page 52, which describes this transform and its prerequisite
condition as indentity #7.

[1] Galindo-Legaria, C. & Rosenthal, A.: "Outerjoin simplification and
reordering for query optimization", ACM Transactions on Database
Systems, Vol 22, No 1, March 1997.

Issue Links

• is related to: DERBY-4712 Complex nested joins problems
• relates to: DERBY-4736 ASSERT FAIL when code generating a column reference in a join predicate in presence of other outer join reordering
• relates to: DERBY-4742 Make outer join reordering work for right outer joins