MySQL Bugs: #58490: Incorrect result in multi level OUTER JOIN in combination with IS NULL

Bug #58490	Incorrect result in multi level OUTER JOIN in combination with IS NULL
Submitted:	25 Nov 2010 12:54	Modified:	11 Mar 2011 13:18
Reporter:	Ole John Aske	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.6.99, 5.5, 5.1, 5.0.91	OS:	Any
Assigned to:	Ole John Aske	CPU Architecture:	Any

Description:
Qualifying an OUTER JOINed result with WHERE <column> IS NULL return an incorrect result on all releases 5.1 - 5.6.99. Likely also on 5.0 which I have not checked.

This is assumed to be caused by incorrect implementation of 'not_exists_optimize' as explained with 'Not exists' below:

+----+-------------+-------+------+---------------+------+---------+------+------+----------+-------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                   |
+----+-------------+-------+------+---------------+------+---------+------+------+----------+-------------------------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL |    4 |   100.00 |                         |
|  1 | SIMPLE      | t2    | ALL  | NULL          | NULL | NULL    | NULL |    4 |   100.00 |                         |
|  1 | SIMPLE      | t3    | ALL  | NULL          | NULL | NULL    | NULL |    4 |   100.00 |                         |
|  1 | SIMPLE      | t4    | ALL  | NULL          | NULL | NULL    | NULL |    4 |   100.00 | Using where; Not exists |
+----+-------------+-------+------+---------------+------+---------+------+------+----------+-------------------------+

How to repeat:
create table t1 (i int not null) engine = innodb;
insert into t1 values (0),    (2),(3),(4);
create table t2 (i int not null) engine = innodb;
insert into t2 values (0),(1),    (3),(4);
create table t3 (i int not null) engine = innodb;
insert into t3 values (0),(1),(2),    (4);
create table t4 (i int not null) engine = innodb;
insert into t4 values (0),(1),(2),(3)   ;

select * from
 t1 LEFT JOIN
 ( t2 LEFT JOIN
   ( t3 LEFT JOIN 
     t4
     ON t4.i = t3.i
   )
   ON t3.i = t2.i
 )
 ON t2.i = t1.i
 ;

Returns the (correct) outer joined result:
+---+------+------+------+
| i | i    | i    | i    |
+---+------+------+------+
| 0 |    0 |    0 |    0 |
| 2 | NULL | NULL | NULL |
| 3 |    3 | NULL | NULL |
| 4 |    4 |    4 | NULL |
+---+------+------+------+
4 rows in set (0.00 sec)

I then append the condition 'WHERE t4.i IS NULL'

select * from
 t1 LEFT JOIN
 ( t2 LEFT JOIN
   ( t3 LEFT JOIN 
     t4
     ON t4.i = t3.i
   )
   ON t3.i = t2.i
 )
 ON t2.i = t1.i
 WHERE t4.i IS NULL;

Depending on the version this will return the incorrect result:

5.1.53 & 5.5.7:
==============
+---+------+------+------+
| i | i    | i    | i    |
+---+------+------+------+
| 0 |    0 | NULL | NULL |
| 2 | NULL | NULL | NULL |
| 3 |    3 | NULL | NULL |
| 4 |    4 |    4 | NULL |
+---+------+------+------+
4 rows in set (0.00 sec)

5.6.99:
======
+---+------+------+------+
| i | i    | i    | i    |
+---+------+------+------+
| 2 | NULL | NULL | NULL |
+---+------+------+------+
1 row in set (0.00 sec)

It should have been:
+---+------+------+------+
| i | i    | i    | i    |
+---+------+------+------+
| 2 | NULL | NULL | NULL |
| 3 |    3 | NULL | NULL |
| 4 |    4 |    4 | NULL |
+---+------+------+------+
3 rows in set (0.00 sec)

Verified also with 5.0.91:

C:\Program Files\MySQL\MySQL Server 5.1\bin>mysql -uroot -proot -P3308 test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 10
Server version: 5.0.91-community-nt MySQL Community Edition (GPL)

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> drop table t1, t2, t3, t4;
Query OK, 0 rows affected (0.23 sec)

mysql> create table t1 (i int not null) engine = innodb;
Query OK, 0 rows affected (0.09 sec)

mysql> insert into t1 values (0),    (2),(3),(4);
Query OK, 4 rows affected (0.08 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> create table t2 (i int not null) engine = innodb;
Query OK, 0 rows affected (0.09 sec)

mysql> insert into t2 values (0),(1),    (3),(4);
Query OK, 4 rows affected (0.05 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> create table t3 (i int not null) engine = innodb;
Query OK, 0 rows affected (0.09 sec)

mysql> insert into t3 values (0),(1),(2),    (4);
Query OK, 4 rows affected (0.03 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> create table t4 (i int not null) engine = innodb;
Query OK, 0 rows affected (0.08 sec)

mysql> insert into t4 values (0),(1),(2),(3)   ;
Query OK, 4 rows affected (0.05 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql>
mysql> select * from
    ->  t1 LEFT JOIN
    ->  ( t2 LEFT JOIN
    ->    ( t3 LEFT JOIN
    ->      t4
    ->      ON t4.i = t3.i
    ->    )
    ->    ON t3.i = t2.i
    ->  )
    ->  ON t2.i = t1.i
    ->  ;
+---+------+------+------+
| i | i    | i    | i    |
+---+------+------+------+
| 0 |    0 |    0 |    0 |
| 2 | NULL | NULL | NULL |
| 3 |    3 | NULL | NULL |
| 4 |    4 |    4 | NULL |
+---+------+------+------+
4 rows in set (0.00 sec)

mysql> select * from
    ->  t1 LEFT JOIN
    ->  ( t2 LEFT JOIN
    ->    ( t3 LEFT JOIN
    ->      t4
    ->      ON t4.i = t3.i
    ->    )
    ->    ON t3.i = t2.i
    ->  )
    ->  ON t2.i = t1.i
    ->  WHERE t4.i IS NULL;
+---+------+------+------+
| i | i    | i    | i    |
+---+------+------+------+
| 0 |    0 | NULL | NULL |
| 2 | NULL | NULL | NULL |
| 3 |    3 | NULL | NULL |
| 4 |    4 |    4 | NULL |
+---+------+------+------+
4 rows in set (0.00 sec)

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/125027

3474 Ole John Aske	2010-11-25
      Fix for bug#58490, 'Incorrect result in multi level OUTER JOIN in combination with IS NULL'
      
      Qualifying an OUTER JOIN with '<column> IS NULL' where <column> is declared as 'NOT NULL' 
      causes the 'not_exists_optimize' to be enabled.
      
      In evaluate_join_record() the 'not_exists_optimize' caused 'NESTED_LOOP_NO_MORE_ROWS' to be 
      returned immediately when a matching row was found.
      
      This happened before all 'first_unmatched->found' had been properly evaluated for all 
      embedding outer joins. This may cause incorrect calls to 
      evaluate_null_complemented_join_record() after we had returned back to sub_select().
      
      This fix ensures that evaluate_join_record() completes the itteration of the 'first_unmatched-loop',
      evaluates all conditions for the unmatched JOIN_TAB's and set 'first_unmatched->found' properly before
      possibly returning NESTED_LOOP_NO_MORE_ROWS iff 'not_exists_optimize' was in effect.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/125028

3377 Ole John Aske	2010-11-25
      SPJ-scan-scan: Cherry picked fix for bug#58490 into SPJ branch

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/125030

3378 Ole John Aske	2010-11-25
      SPJ-scan-scan: Cherry picked fix for bug#58490 into SPJ branch

This is possibly a duplicate of bug#49322....?

Has tested this fix against bugs.mysql.com/49332 and all issues seems to have been resolved. I believe we can conclude that these bugs are duplicates of each other.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/125802

3477 Ole John Aske	2010-12-02
      Updated fix for bug#58490, 'Incorrect result in multi level OUTER JOIN in combination with IS NULL'
      
      After some more testing, and discussion with Roy L. which has also tested my fix on the next-mr branch
      the DBUG_ASSERT(rc==NESTED_LOOP_OK) a line ~11553 was removed.
      This was replaced by 'if (rc == NESTED_LOOP_NO_MORE_ROWS) found= false;'.
      
      Furthermore testcases for the duplicated bug#49332 has been added.
      
      
      --- original description ---
      Qualifying an OUTER JOIN with '<column> IS NULL' where <column> is declared as 'NOT NULL' 
      causes the 'not_exists_optimize' to be enabled.
            
      In evaluate_join_record() the 'not_exists_optimize' caused 'NESTED_LOOP_NO_MORE_ROWS' to be 
      returned immediately when a matching row was found.
            
      This happened before all 'first_unmatched->found' had been properly evaluated for all 
      embedding outer joins. This may cause incorrect calls to 
      evaluate_null_complemented_join_record() after we had returned back to sub_select().
            
      This fix ensures that evaluate_join_record() completes the itteration of the 'first_unmatched-loop',
      evaluates all conditions for the unmatched JOIN_TAB's and set 'first_unmatched->found' properly before
      possibly returning NESTED_LOOP_NO_MORE_ROWS iff 'not_exists_optimize' was in effect.

During the review, I'm trying to gather info about the offending query. It may be useful to know:
- the graph of first_inner/first_upper/last_inner pointers (I am uploading it)
- that the testcase can be simplified to 3 tables and still show the bug:
select * from
 t1 LEFT JOIN
 ( t2 LEFT JOIN
   ( t3 
   )
   ON t3.i = t2.i
 )
 ON t2.i = t1.i
 WHERE t3.i IS NULL
 ;
- that for the simplified testcase above, "not exists" is indeed the cause (commenting out
  field->field->table->reginfo.not_exists_optimize=1;
from sql_select.cc hides the bug), and the conditions attached to tables are only one condition attached to t3 which can be written as:

trigcond_if(found_match(t3),
            trigcond_if(found_match(t2..t3),isnull(`test`.`t3`.`i`), true),
            true)
and
trigcond_if(is_not_null_compl(t3), (`test`.`t2`.`i` = `test`.`t1`.`i`), true)
and
trigcond_if(is_not_null_compl(t3), (`test`.`t3`.`i` = `test`.`t1`.`i`), true)
(this comes from the optimizer trace feature tree).
trigcond_if(a,b,c) is Item_func_trig_cond, if 'a' is true then it evaluates to 'b' otherwise to 'c'.
is_not_null_compl(t3) is true if the current row for t3 is a real row and not a null-complemented one.
found_match(t3) is true if the current row for t3 matches the ON clause for t3.
Those "pseudo-functions" thus have varying values as execution of nested-loop-join advances.

diagram of pointers for 4-table case

Attachment: outer_join_diag.png (image/png, text), 30.25 KiB.

correction to "found_match(t3) is true if the current row for t3 matches the ON clause for t3": I should have written
"found_match(t3) is true if one row for t3 has matched the ON clause for t3 (even a row before the current one)". As soon as a match has been found in t3 for the ON clause for t3, we know that we won't generate NULL values for t3's columns for this partial record t1//t2, so we can push the "WHERE t3.i IS NULL" down to t3 for all other future rows of t3 (as long as we stay on the same partial record t1//t2).

correction to a previous post of mine; found a bug in the optimizer trace code; for the simplified testcase (using t1 t2 t3) there is also a condition attached to t2:
"trigcond_if(is_not_null_compl(t2..t3), (t2.i = t1.i), true)"

minimal testcase:
create table t1 (i int not null) engine = innodb;
insert into t1 values (0);
create table t2 (i int not null) engine = innodb;
insert into t2 values (0);
create table t3 (i int not null) engine = innodb;
insert into t3 values (0);
select * from  t1 LEFT JOIN (t2 LEFT JOIN t3 ON t3.i = t2.i) ON t2.i = t1.i;
0 0 0
select * from  t1 LEFT JOIN (t2 LEFT JOIN t3 ON t3.i = t2.i) ON t2.i = t1.i WHERE t3.i IS NULL;
0 NULL NULL

triage: not clear why this is a 'severe' problem as impact seems to be quite low. But requesting e/r values to see if can be done for MRU

To Triage: if you look at my latest testcase, which involves only 3 single-row tables, I don't see that this is a complex query. So maybe this isn't so low-impact...?

review comments have been sent a while back; patch is ok except that I'd like more comments (see sent mail) and assertions. To be discussed with Ole John.
Setting to "in progress" to mark that it's not waiting on me.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/128171

3534 Ole John Aske	2011-01-07
      Updated fix for bug#58490, 'Incorrect result in multi level OUTER JOIN in combination with IS NULL'
            
      Based on even more testing, and review feedback from Guilhem B. and Roy L.
      
      There are cases where we may exit the while(first_unmatched && found)' loop
      with both found= true and rc= NESTED_LOOP_NO_MORE_ROWS. This simply
      indicates that we should proceed with the 'if(found)' section in
      evaluate_join_record() and produce results from the 'found' row.
      
      It should be noted that this behaviour is identical to what we will
      get when we remove the 'not_exists_optimize' flag (Which is 
      a sensible sanity test as not_exists_optimize is a pure optimization only.)
      
      Testcases has been added to the original fix to cover this situation
      (found= true and rc= NESTED_LOOP_NO_MORE_ROWS.)
      
      As this bug is a duplicate of bug#49322, it also include tescases
      covering this bugreport
      
      --- original description ---
      Qualifying an OUTER JOIN with '<column> IS NULL' where <column> is declared as 'NOT NULL' 
      causes the 'not_exists_optimize' to be enabled.
                  
      In evaluate_join_record() the 'not_exists_optimize' caused 'NESTED_LOOP_NO_MORE_ROWS' to be 
      returned immediately when a matching row was found.
                  
      This happened before all 'first_unmatched->found' had been properly evaluated for all 
      embedding outer joins. This may cause incorrect calls to 
      evaluate_null_complemented_join_record() after we had returned back to sub_select().
                  
      This fix ensures that evaluate_join_record() completes the itteration of the 'first_unmatched-loop',
      evaluates all conditions for the unmatched JOIN_TAB's and set 'first_unmatched->found' properly before
      possibly returning NESTED_LOOP_NO_MORE_ROWS iff 'not_exists_optimize' was in effect.

Reverted status to 'In progress' after discussing last patch with Roy L: There are some issues which should be further investigated before I request a review or commit an updated patch.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

http://lists.mysql.com/commits/128398

3534 Ole John Aske 2011-01-11
Fix for bug#58490, 'Incorrect result in multi level OUTER JOIN in combination with IS NULL'

As this bug is a duplicate of bug#49322, it also include tescases
covering this bugreport

Qualifying an OUTER JOIN with the condition 'WHERE <column> IS NULL',
where <column> is declared as 'NOT NULL' causes the
'not_exists_optimize' to be enabled by the optimizer.

In evaluate_join_record() the 'not_exists_optimize' caused
'NESTED_LOOP_NO_MORE_ROWS' to be returned immediately
when a matching row was found.

However, as the 'not_exists_optimize' is derived from
'JOIN_TAB::select_cond', the usual rules for condition guards
also applies for 'not_exist_optimize'. It is therefore incorrect
to check 'not_exists_optimize' without ensuring that all guards
protecting it is 'open'.

This fix uses the fact that 'not_exists_optimize' is derived from
a 'is_null' condition term in 'tab->select_cond'. Futhrermore,
'is_null' will evaluate to 'false' for any 'non-null' rows
once all guards protecting the is_null is open.

We can use this knowledge as an implicit guard check for the
'not_exists_optimize' by moving 'if (...not_exists_optimize)'
inside the handling of 'select_cond==false'. It will then
not take effect before its guards are open.

We also add an assert which requires that a
'not_exists_optimize' always comes together with
a select_cond. (containing 'is_null').

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/130129

3294 Ole John Aske	2011-02-01
      Fix for bug#58490, 'Incorrect result in multi level OUTER JOIN 
      in combination with IS NULL'
            
      As this bug is a duplicate of bug#49322, it also includes test cases
      covering this bugreport
            
      Qualifying an OUTER JOIN with the condition 'WHERE <column> IS NULL',
      where <column> is declared as 'NOT NULL' causes the
      'not_exists_optimize' to be enabled by the optimizer.
            
      In evaluate_join_record() the 'not_exists_optimize' caused
      'NESTED_LOOP_NO_MORE_ROWS' to be returned immediately
      when a matching row was found.
            
      However, as the 'not_exists_optimize' is derived from
      'JOIN_TAB::select_cond', the usual rules for condition guards
      also applies for 'not_exist_optimize'. It is therefore incorrect
      to check 'not_exists_optimize' without ensuring that all guards
      protecting it is 'open'.
            
      This fix uses the fact that 'not_exists_optimize' is derived from
      a 'is_null' predicate term in 'tab->select_cond'. Furthermore,
      'is_null' will evaluate to 'false' for any 'non-null' rows
      once all guards protecting the is_null is open.
            
      We can use this knowledge as an implicit guard check for the
      'not_exists_optimize' by moving 'if (...not_exists_optimize)'
      inside the handling of 'select_cond==false'. It will then
      not take effect before its guards are open.
            
      We also add an assert which requires that a
      'not_exists_optimize' always comes together with
      a select_cond. (containing 'is_null').

Pushed into mysql-trunk 5.6.2 (revid:ole.john.aske@oracle.com-20110201142457-3hdefsxj12q0acvl) (version source revid:ole.john.aske@oracle.com-20110201142457-3hdefsxj12q0acvl) (merge vers: 5.6.2) (pib:24)

Pushed into mysql-5.5 5.5.10 (revid:ole.john.aske@oracle.com-20110201141934-ppx2z4tn6vv0u8q9) (version source revid:ole.john.aske@oracle.com-20110201141934-ppx2z4tn6vv0u8q9) (merge vers: 5.5.10) (pib:24)

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/130176

4163 Ole John Aske	2011-02-02
      Fix for bug#58490: 'Incorrect result in multi level OUTER JOIN', cherry picked into telco branches.
      Also fix the duplicate bug#49322.
      
      Se original commit http://lists.mysql.com/commits/130129 for comments

Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.22 (revid:ole.john.aske@oracle.com-20110202074752-4c6jzaiwxvf7rngl) (version source revid:ole.john.aske@oracle.com-20110202074752-4c6jzaiwxvf7rngl) (merge vers: 5.1.51-ndb-7.0.22) (pib:24)

Fix has been pushed to mysql-5.5 and mysql-trunk, and cherry picked into mysql-5.1-telco-7.0.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/130180

3586 Ole John Aske	2011-02-02
      Fixed failing testcase after commit of fix for bug#58490.
      
      Added '--sorted_result' to new testcases to get deterministic order of result set.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/130181

3587 Ole John Aske	2011-02-02
      Fixed failing testcase after commit of fix for bug#58490.
      
      Added '--sorted_result' to new testcases to get deterministic order of result set.

Pushed into mysql-trunk 5.6.2 (revid:ole.john.aske@oracle.com-20110202081516-fv7dqwj11afpumsi) (version source revid:ole.john.aske@oracle.com-20110202081516-fv7dqwj11afpumsi) (merge vers: 5.6.2) (pib:24)

Documented as follows in the NDB-7.0.22, NDB-7.1.11, MySQL 5.5.10, and MySQL 5.6.2 changelogs:

      An OUTER JOIN query using WHERE <column> IS NULL could return an 
      incorrect result.

Closed.