MySQL Bugs: #40268: Extra rows for queries with nested outer joins using join buffer

Bug #40268	Extra rows for queries with nested outer joins using join buffer
Submitted:	22 Oct 2008 20:41	Modified:	22 Nov 2010 1:41
Reporter:	Igor Babaev	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	6.0-BKA	OS:	Any
Assigned to:	Igor Babaev	CPU Architecture:	Any

Description:
The server may generate extra rows in the result set for a query with a nested outer join if the inner tables of the outer join are joined using join buffers.
It may happen if the where clause contains a condition over some inner table which not is the last inner table to be accessed by the query execution plan. Additionally the condition (1) has to be not null-rejecting and (2) has to refer to any other previously accessed table. The problem could be demonstrated when (2) is not observed, but only when bug #40192 is fixed. 

How to repeat:
Create and populate tables t2,t3,t4 with the following commands:

CREATE TABLE t2 (a int, b int, c int);
CREATE TABLE t3 (a int, b int, c int);
CREATE TABLE t4 (a int, b int, c int);

INSERT INTO t2 VALUES (3,3,0), (4,2,0), (5,3,0);
INSERT INTO t3 VALUES (1,2,0), (2,2,0);
INSERT INTO t4 VALUES (3,2,0), (4,2,0);

Run this query without using join buffers:

SELECT t2.a,t2.b,t3.a,t3.b,t4.a,t4.b
  FROM t2 LEFT JOIN (t3, t4) ON t2.b=t4.b
     WHERE t3.a+2<t2.a OR t3.c IS NULL;

You get the result set that is expected:

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

mysql> SELECT t2.a,t2.b,t3.a,t3.b,t4.a,t4.b
    ->   FROM t2 LEFT JOIN (t3, t4) ON t2.b=t4.b
    ->      WHERE t3.a+2<t2.a OR t3.c IS NULL;
+------+------+------+------+------+------+
| a    | b    | a    | b    | a    | b    |
+------+------+------+------+------+------+
|    3 |    3 | NULL | NULL | NULL | NULL |
|    4 |    2 |    1 |    2 |    3 |    2 |
|    4 |    2 |    1 |    2 |    4 |    2 |
|    5 |    3 | NULL | NULL | NULL | NULL |
+------+------+------+------+------+------+
4 rows in set (0.00 sec)

However, when join buffers are used we have extra rows in the result set:

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

mysql> EXPLAIN
    -> SELECT t2.a,t2.b,t3.a,t3.b,t4.a,t4.b
    ->   FROM t2 LEFT JOIN (t3, t4) ON t2.b=t4.b
    ->      WHERE t3.a+2<t2.a OR t3.c IS NULL;
+----+-------------+-------+------+---------------+------+---------+------+------+--------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                          |
+----+-------------+-------+------+---------------+------+---------+------+------+--------------------------------+
|  1 | SIMPLE      | t2    | ALL  | NULL          | NULL | NULL    | NULL |    3 |                                |
|  1 | SIMPLE      | t3    | ALL  | NULL          | NULL | NULL    | NULL |    2 | Using where; Using join buffer |
|  1 | SIMPLE      | t4    | ALL  | NULL          | NULL | NULL    | NULL |    2 | Using where; Using join buffer |
+----+-------------+-------+------+---------------+------+---------+------+------+--------------------------------+
3 rows in set (0.00 sec)

mysql> SELECT t2.a,t2.b,t3.a,t3.b,t4.a,t4.b
    ->   FROM t2 LEFT JOIN (t3, t4) ON t2.b=t4.b
    ->      WHERE t3.a+2<t2.a OR t3.c IS NULL;
+------+------+------+------+------+------+
| a    | b    | a    | b    | a    | b    |
+------+------+------+------+------+------+
|    4 |    2 |    1 |    2 |    3 |    2 |
|    4 |    2 |    2 |    2 |    3 |    2 |
|    4 |    2 |    1 |    2 |    4 |    2 |
|    4 |    2 |    2 |    2 |    4 |    2 |
|    3 |    3 | NULL | NULL | NULL | NULL |
|    5 |    3 | NULL | NULL | NULL | NULL |
+------+------+------+------+------+------+
6 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/56862

2661 Igor Babaev	2008-10-22
      Fixed bug #40268.
      This bug caused generation of extra rows in the result sets for
      some queries with nested outer joins. It could happen if
      the pushdown condition attached to not the last inner table 
      of the outer join was extracted from the where clause.
      It happened because this pushdown condition erroneously
      was not checked against matching row combinations from inner
      tables that were not the first matches for a given partial
      row generated from outer tables.

Pushed into 6.0.8-alpha  (revid:igor@mysql.com-20081023045332-vzyi4wzgr67gheaa) (version source revid:igor@mysql.com-20081023045332-vzyi4wzgr67gheaa) (pib:5)

Correction: This is pushed into 6.0.9.

Noted in 6.0.9 changelog.

The server could generate extra rows in the result set for a query 
with a nested outer join if the inner tables of the outer join were
joined using join buffers.

Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)

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)

Bug is not in any released 5.6.x version. No changelog entry needed.