Bug #42020 Wrong results returned by BKA outer join with several outer tables.
Submitted: 10 Jan 2009 20:07 Modified: 20 Nov 2010 23:12
Reporter: Igor Babaev Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S1 (Critical)
Version:6.0.9 OS:Any
Assigned to: Igor Babaev CPU Architecture:Any

[10 Jan 2009 20:07] Igor Babaev
Description:
A query with an outer join may return a wrong result set if BKA is employed to execute the outer join and fields of more than one outer tables are put into the join buffer that is used for this operation.
This bug originally was reported to me by Gene Pang with a pretty complicated test case. 

How to repeat:
Create and populate 3 tables with the following commands:

CREATE TABLE t1 (
  a bigint NOT NULL,
  PRIMARY KEY (a) 
);
INSERT INTO t1 VALUES
  (2), (1);

CREATE TABLE t2 (
  a bigint NOT NULL,
  b bigint NOT NULL,
  PRIMARY KEY (a,b)
);
INSERT INTO t2 VALUES
  (2,30), (2,40), (2,50), (2,60), (2,70), (2,80), (2,90),
  (1,10), (1, 20), (1,30), (1,40), (1,50), (1,60), (1,70), (1,80), (1,90);

CREATE TABLE t3 (
  pk bigint NOT NULL AUTO_INCREMENT,
  a bigint NOT NULL,
  b bigint NOT NULL,
  val bigint DEFAULT '0',
  PRIMARY KEY (pk),
  KEY idx (a,b)
);
INSERT INTO t3(a,b) VALUES
  (2,30), (2,40), (2,50), (2,60), (2,70), (2,80), (2,90),
  (4,30), (4,40), (4,50), (4,60), (4,70), (4,80), (4,90), 
  (5,30), (5,40), (5,50), (5,60), (5,70), (5,80), (5,90),
  (7,30), (7,40), (7,50), (7,60), (7,70), (7,80), (7,90);

Enable BKA joins with a small join buffer:

set join_cache_level=6;
set join_buffer_size=256;

Run the query:
SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val 
  FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b) 
    WHERE t1.a=t2.a; 

The result set is wrong:

mysql> SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val
    ->   FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b)
    ->     WHERE t1.a=t2.a;
+---+---+------+----+------+------+
| a | a | a    | b  | b    | val  |
+---+---+------+----+------+------+
| 1 | 1 | NULL | 10 | NULL | NULL |
| 1 | 1 | NULL | 20 | NULL | NULL |
| 1 | 1 | NULL | 30 | NULL | NULL |
| 1 | 1 | NULL | 40 | NULL | NULL |
| 1 | 1 | NULL | 50 | NULL | NULL |
| 1 | 1 | NULL | 60 | NULL | NULL |
| 2 | 2 |    2 | 30 |   30 |    0 |
| 2 | 2 |    2 | 40 |   40 |    0 |
| 2 | 2 |    2 | 50 |   50 |    0 |
| 1 | 1 | NULL | 70 | NULL | NULL |
| 1 | 1 | NULL | 80 | NULL | NULL |
| 1 | 1 | NULL | 90 | NULL | NULL |
| 1 | 2 | NULL | 60 | NULL | NULL |
| 1 | 2 | NULL | 70 | NULL | NULL |
| 1 | 2 | NULL | 80 | NULL | NULL |
| 1 | 2 | NULL | 90 | NULL | NULL |
+---+---+------+----+------+------+

If no BKA is used the query returns the right result set:

mysql> set join_buffer_size=default;
Query OK, 0 rows affected (0.00 sec)

mysql> set join_cache_level=default;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val
    ->   FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b)
    ->     WHERE t1.a=t2.a;
+---+---+------+----+------+------+
| a | a | a    | b  | b    | val  |
+---+---+------+----+------+------+
| 1 | 1 | NULL | 10 | NULL | NULL |
| 1 | 1 | NULL | 20 | NULL | NULL |
| 1 | 1 | NULL | 30 | NULL | NULL |
| 1 | 1 | NULL | 40 | NULL | NULL |
| 1 | 1 | NULL | 50 | NULL | NULL |
| 1 | 1 | NULL | 60 | NULL | NULL |
| 1 | 1 | NULL | 70 | NULL | NULL |
| 1 | 1 | NULL | 80 | NULL | NULL |
| 1 | 1 | NULL | 90 | NULL | NULL |
| 2 | 2 |    2 | 30 |   30 |    0 |
| 2 | 2 |    2 | 40 |   40 |    0 |
| 2 | 2 |    2 | 50 |   50 |    0 |
| 2 | 2 |    2 | 60 |   60 |    0 |
| 2 | 2 |    2 | 70 |   70 |    0 |
| 2 | 2 |    2 | 80 |   80 |    0 |
| 2 | 2 |    2 | 90 |   90 |    0 |
+---+---+------+----+------+------+
[10 Jan 2009 20:13] MySQL Verification Team
Thank you for the bug report. Verified as described.
[11 Jan 2009 0:45] Sergey Petrunya
Ok to push the fix discussed on irc + testcase.
[11 Jan 2009 21:23] Igor Babaev
The same bug may lead to wrong results when BNL is used:

mysql> DROP INDEX idx ON t3;
Query OK, 28 rows affected (0.14 sec)
Records: 28  Duplicates: 0  Warnings: 0

mysql> set join_cache_level=4;
Query OK, 0 rows affected (0.00 sec)

mysql> set join_buffer_size=256;
Query OK, 0 rows affected (0.00 sec)

mysql> delete from t2 where b>=80;
Query OK, 4 rows affected (0.00 sec)

mysql> EXPLAIN SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val    FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b)      WHERE t1.a=t2.a;
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+--------------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref       | rows | Extra                          |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+--------------------------------+
|  1 | SIMPLE      | t1    | index | PRIMARY       | PRIMARY | 8       | NULL      |    2 | Using index                    |
|  1 | SIMPLE      | t2    | ref   | PRIMARY       | PRIMARY | 8       | test.t1.a |    1 | Using index                    |
|  1 | SIMPLE      | t3    | ALL   | NULL          | NULL    | NULL    | NULL      |   28 | Using where; Using join buffer |
+----+-------------+-------+-------+---------------+---------+---------+-----------+------+--------------------------------+
3 rows in set (0.00 sec)

mysql> SELECT t1.a, t2.a, t3.a, t2.b, t3.b, t3.val    FROM (t1,t2) LEFT JOIN t3 ON (t1.a=t3.a AND t2.b=t3.b)      WHERE t1.a=t2.a;
+---+---+------+----+------+------+
| a | a | a    | b  | b    | val  |
+---+---+------+----+------+------+
| 2 | 2 |    2 | 30 |   30 |    0 |
| 2 | 2 |    2 | 40 |   40 |    0 |
| 1 | 1 | NULL | 10 | NULL | NULL |
| 1 | 1 | NULL | 20 | NULL | NULL |
| 1 | 1 | NULL | 30 | NULL | NULL |
| 1 | 1 | NULL | 40 | NULL | NULL |
| 1 | 1 | NULL | 50 | NULL | NULL |
| 1 | 1 | NULL | 60 | NULL | NULL |
| 1 | 1 | NULL | 70 | NULL | NULL |
| 1 | 2 | NULL | 50 | NULL | NULL |
| 1 | 2 | NULL | 60 | NULL | NULL |
| 1 | 2 | NULL | 70 | NULL | NULL |
+---+---+------+----+------+------+
12 rows in set (0.00 sec)
[11 Jan 2009 22:02] Bugs System
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/62947

2806 Igor Babaev	2009-01-11
      Fixed bug #42020.
      When an outer join is executed using a join buffer the buffer
      is scanned twice. At the first scan matches for records in the
      buffer are looked for and any record for which a match is found
      is marked. At the second scan the records without matches are
      looked through and each of them is complemented by null columns
      after having been read into the record buffer. Records with
      matches are just skipped and not even read into the join buffer.
      As a result at the end of the scan the record in the record buffer
      is not guaranteed to be the last record from join buffer. This
      can break the whole nested loop process and lead to wrong 
      results produced by the operation.
      All fields of the last record from the join buffer must be restored
      in the corresponding record buffers after the second scan.
[2 Feb 2009 16:06] Bugs System
Pushed into 6.0.10-alpha (revid:sergefp@mysql.com-20090202090240-dlkxhmc1asrar5rl) (version source revid:sergefp@mysql.com-20090121091459-7gc5ok2ia3f09fpe) (merge vers: 6.0.10-alpha) (pib:6)
[11 Feb 2009 2:58] Paul DuBois
Noted in 6.0.10 changelog.

Queries executed using a join buffer could return incorrect results.
[16 Aug 2010 6:36] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)
[13 Nov 2010 16:12] Bugs System
Pushed into mysql-trunk 5.6.99-m5 (revid:alexander.nozdrin@oracle.com-20101113155825-czmva9kg4n31anmu) (version source revid:vasil.dimov@oracle.com-20100629074804-359l9m9gniauxr94) (merge vers: 5.6.99-m4) (pib:21)
[20 Nov 2010 23:12] Paul DuBois
Noted in 5.6.1 changelog.
[23 Nov 2010 2:10] Paul DuBois
Correction: No 5.6.1 changelog entry. Bug does not appear in any released 5.6.x version.