Bug #54359 Extra rows with join_cache_level=7,8 and two joins and multi-column index
Submitted: 9 Jun 2010 8:49 Modified: 23 Nov 2010 3:32
Reporter: John Embretsen Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:bzr_next-mr-opt-backporting, 6.0.14 OS:Any
Assigned to: Guilhem Bichot CPU Architecture:Any
Tags: join_cache_level, optimizer_switch

[9 Jun 2010 8:49] John Embretsen
Description:
The following query returns extra rows when:

optimizer_join_cache_level=7 or 8,
and optimizer_switch includes "mrr=on" and/or "index_condition_pushdown=on",
and t2 has a multiple-column index (`col_varchar_key`,`col_int_key`).

SELECT table2 .`col_int_key`  
FROM t1  
  JOIN 
    ( t2 table2 JOIN t2 table3  ON table3 .`pk` )  
  ON table3 .`col_int_key`  >= table2 .`pk`  
  AND table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`;

Using mysql-next-mr-opt-backporting
revision-id: olav@sun.com-20100607114637-5lpjsoqs1w8s1074

Observed during RQG testing using optimizer_no_subquery.yy grammar, comparing against mysql-5.1-bugteam.

Issue is not repeatable if replacing 

( t2 table2 JOIN t2 table3  ON table3 .`pk` )

with

( t2 table2 CROSS JOIN t2 table3)

or if removing the multiple-column index
or if doing SET SESSION optimizer_switch = "index_condition_pushdown=off";
or if doing SET SESSION optimizer_switch = "mrr=off";

EXPLAIN output (query returns 9 rows):

EXPLAIN SELECT table2 .`col_int_key`   FROM t1     JOIN ( t2 table2  JOIN t2 table3  ON table3 .`pk`  )  ON table3 .`col_int_key`  >= table2 .`pk`     AND table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`;
+----+-------------+--------+--------+-----------------------------+-----------------+---------+-------------------------------+------+------------------------------------------------------------+
| id | select_type | table  | type   | possible_keys               | key             | key_len | ref                           | rows | Extra                                                      |
+----+-------------+--------+--------+-----------------------------+-----------------+---------+-------------------------------+------+------------------------------------------------------------+
|  1 | SIMPLE      | t1     | system | NULL                        | NULL            | NULL    | NULL                          |    1 |                                                            |
|  1 | SIMPLE      | table2 | ALL    | PRIMARY                     | NULL            | NULL    | NULL                          |   15 | Using where                                                |
|  1 | SIMPLE      | table3 | ref    | col_int_key,col_varchar_key | col_varchar_key | 4       | test.table2.col_varchar_nokey |    2 | Using index condition(BKA); Using where; Using join buffer |
+----+-------------+--------+--------+-----------------------------+-----------------+---------+-------------------------------+------+------------------------------------------------------------+
3 rows in set (0.00 sec)

EXPLAIN output with CROSS JOIN (as described above) (query returns 6 rows):

EXPLAIN SELECT table2 .`col_int_key`   FROM t1     JOIN ( t2 table2  CROSS JOIN t2 table3 )  ON table3 .`col_int_key`  >= table2 .`pk`     AND table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`;
+----+-------------+--------+--------+-----------------------------+-----------------+---------+-------------------------------+------+--------------------------+
| id | select_type | table  | type   | possible_keys               | key             | key_len | ref                           | rows | Extra                    |
+----+-------------+--------+--------+-----------------------------+-----------------+---------+-------------------------------+------+--------------------------+
|  1 | SIMPLE      | t1     | system | NULL                        | NULL            | NULL    | NULL                          |    1 |                          |
|  1 | SIMPLE      | table2 | ALL    | PRIMARY                     | NULL            | NULL    | NULL                          |   15 | Using where              |
|  1 | SIMPLE      | table3 | ref    | col_int_key,col_varchar_key | col_varchar_key | 4       | test.table2.col_varchar_nokey |    2 | Using where; Using index |
+----+-------------+--------+--------+-----------------------------+-----------------+---------+-------------------------------+------+--------------------------+
3 rows in set (0.00 sec)

EXPLAIN output with no multi-column index (query returns 6 rows):

EXPLAIN SELECT table2 .`col_int_key`   FROM t1     JOIN ( t2 table2  JOIN t2 table3  ON table3 .`pk`  )  ON table3 .`col_int_key`  >= table2 .`pk`     AND table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`;
+----+-------------+--------+--------+---------------+------+---------+------+------+------------------------------------------------+
| id | select_type | table  | type   | possible_keys | key  | key_len | ref  | rows | Extra                                          |
+----+-------------+--------+--------+---------------+------+---------+------+------+------------------------------------------------+
|  1 | SIMPLE      | t1     | system | NULL          | NULL | NULL    | NULL |    1 |                                                |
|  1 | SIMPLE      | table2 | ALL    | PRIMARY       | NULL | NULL    | NULL |   15 |                                                |
|  1 | SIMPLE      | table3 | ALL    | col_int_key   | NULL | NULL    | NULL |   15 | Range checked for each record (index map: 0x2) |
+----+-------------+--------+--------+---------------+------+---------+------+------+------------------------------------------------+
3 rows in set (0.00 sec)

How to repeat:
SET SESSION optimizer_join_cache_level=8;
SET SESSION optimizer_switch = "engine_condition_pushdown=on,firstmatch=on,index_condition_pushdown=on,index_merge=on,index_merge_intersection=on,index_merge_sort_union=on,index_merge_union=on,loosescan=on,materialization=on,mrr=on,mrr_cost_based=off,semijoin=off";  

DROP TABLE /*! IF EXISTS */ t1;
DROP TABLE /*! IF EXISTS */ t2;

CREATE TABLE t1 (  
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int_key` int(11) DEFAULT NULL,  
  `col_varchar_key` varchar(1) DEFAULT NULL,  
  `col_varchar_nokey` varchar(1) DEFAULT NULL,  
  PRIMARY KEY (`pk`),  
  KEY `col_int_key` (`col_int_key`),  
  KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`)) 
;

INSERT INTO t1 VALUES (29,4,'c','c');

CREATE TABLE t2 (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int_key` int(11) DEFAULT NULL,
  `col_varchar_key` varchar(1) DEFAULT NULL,
  `col_varchar_nokey` varchar(1) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_int_key` (`col_int_key`),
  KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`))
;

INSERT INTO t2 VALUES (4,9,'k','k');
INSERT INTO t2 VALUES (5,NULL,'r','r');
INSERT INTO t2 VALUES (6,9,'t','t');
INSERT INTO t2 VALUES (7,3,'j','j');
INSERT INTO t2 VALUES (8,8,'u','u');
INSERT INTO t2 VALUES (9,8,'h','h');
INSERT INTO t2 VALUES (10,53,'o','o');
INSERT INTO t2 VALUES (11,0,NULL,NULL);
INSERT INTO t2 VALUES (12,5,'k','k');
INSERT INTO t2 VALUES (13,166,'e','e');
INSERT INTO t2 VALUES (14,3,'n','n');
INSERT INTO t2 VALUES (15,0,'t','t');
INSERT INTO t2 VALUES (16,1,'c','c');
INSERT INTO t2 VALUES (17,9,'m','m');
INSERT INTO t2 VALUES (18,5,'y','y');

SELECT table2 .`col_int_key`  
FROM t1  
  JOIN ( t2 table2  JOIN t2 table3  ON table3 .`pk`  )  ON table3 .`col_int_key`  >= table2 .`pk`  
  AND table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`   
;

+-------------+
| col_int_key |
+-------------+
|           5 |
|           9 |
|           0 |
|           9 |
|           8 |
|          53 |
|           5 |
|           9 |
|         166 |
+-------------+
9 rows in set (0.00 sec)

mysql> ALTER TABLE t2 DROP INDEX `col_varchar_key`;
Query OK, 15 rows affected (0.02 sec)
Records: 15  Duplicates: 0  Warnings: 0

mysql> SELECT table2 .`col_int_key`   FROM t1     JOIN ( t2 table2  JOIN t2 table3  ON table3 .`pk`  )  ON table3 .`col_int_key`  >= table2 .`pk`     AND table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`;
+-------------+
| col_int_key |
+-------------+
|           9 |
|           9 |
|           9 |
|           8 |
|          53 |
|         166 |
+-------------+
6 rows in set (0.00 sec)
[22 Jun 2010 8:47] Guilhem Bichot
smaller testcase (less rows and tables and less complicated syntax):
-- source include/have_innodb.inc
set storage_engine=innodb;
set optimizer_join_cache_level=7;

CREATE TABLE t2 (
  `pk` int(11) NOT NULL,
  `col_int_key` int(11) DEFAULT NULL,
  `col_varchar_key` varchar(1) DEFAULT NULL,
  `col_varchar_nokey` varchar(1) DEFAULT NULL,
  KEY `col_varchar_key` (`col_varchar_key`,`col_int_key`))
;

INSERT INTO t2 VALUES (4,9,'k','k');
INSERT INTO t2 VALUES (12,5,'k','k');

SELECT table2 .`col_int_key` FROM t2 table2,
t2 table3 force index (`col_varchar_key`)
where
table3 .`pk` and table3 .`col_int_key`  >= table2 .`pk`  
  AND table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`   
;
this returns 9,9,5,5 instead of 9,9.
[28 Jun 2010 9:21] Guilhem Bichot
sent analysis and waiting for Gluh's feedback as it's his code.
[30 Jun 2010 20:20] 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/112622

3204 Guilhem Bichot	2010-06-30
      Fix for BUG#54359 "Extra rows with join_cache_level=7,8 and two joins
      --and multi-column index"; pushed index condition wasn't correctly checked
      in BKA_UNIQUE.
     @ mysql-test/include/join_cache.inc
        test for bug
     @ mysql-test/r/join_cache_jcl1.result
        correct result
     @ mysql-test/r/join_cache_jcl7.result
        without the code fix, result of SELECT would be 5,5,9,9 instead of 9,9
     @ mysql-test/r/join_cache_jcl8.result
        without the code fix, result of SELECT would be 5,5,9,9 instead of 9,9
     @ sql/sql_join_cache.cc
        See added doxygen comments.
        Without this fix, in the testcase (see join_cache.inc) we had this:
        - this is BKA_UNIQUE, which prepares distinct keys for lookup in table3's index,
        which lookup will satisfy
          table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`
        - the two cached records of table2 have the same distinct key prefix 'k'
        - the index condition pushed to table3 is
          table3 .`col_int_key`  >= table2 .`pk`
        - a lookup for 'k' in table3 is done using the available index, the
        found index tuples also provide the value of table3.col_int_key: we have
        (9,'k') and (5,'k')
        - both index tuples are not eliminated by bka_unique_skip_index_tuple() as
        each of them satisfies the pushed condition when paired with at least
        one table2's cached record: (9,'k') paired with (4,9,'k','k'), (5,'k')
        paired with (4,9,'k','k')
        - the two table3 records corresponding to the accepted index tuples are
        retrieved
        - and, in join_matching_records(), joined with the two table2 records
        having distinct key 'k'; the mistake is here; we had determined in
        bka_unique_skip_index_tuple() than the two table3 records 
        would join with at least one cached table2 record; it doesn't mean that
        they join with all cached table2 records. A re-check of the index
        condition is needed. We do it in check_match().
     @ sql/sql_select.h
        subclasses of JOIN_CACHE can now specialize check_match():
        BKA_UNIQUE does so.
[1 Jul 2010 8:54] 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/112650

3204 Guilhem Bichot	2010-07-01
      Fix for BUG#54359 "Extra rows with join_cache_level=7,8 and two joins
      --and multi-column index"; pushed index condition wasn't correctly checked
      in BKA_UNIQUE.
     @ mysql-test/include/join_cache.inc
        test for bug
     @ mysql-test/r/join_cache_jcl1.result
        correct result
     @ mysql-test/r/join_cache_jcl7.result
        without the code fix, result of SELECT would be 5,5,9,9 instead of 9,9
     @ mysql-test/r/join_cache_jcl8.result
        without the code fix, result of SELECT would be 5,5,9,9 instead of 9,9
     @ sql/sql_join_cache.cc
        See added doxygen comments.
        Without this fix, in the testcase (see join_cache.inc) we had this:
        - this is BKA_UNIQUE, which prepares distinct keys for lookup in table3's index,
        which lookup will satisfy
          table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`
        - the two cached records of table2 have the same distinct key prefix 'k'
        - the index condition pushed to table3 is
          table3 .`col_int_key`  >= table2 .`pk`
        - a lookup for 'k' in table3 is done using the available index, the
        found index tuples also provide the value of table3.col_int_key: we have
        (9,'k') and (5,'k')
        - both index tuples are not eliminated by bka_unique_skip_index_tuple() as
        each of them satisfies the pushed condition when paired with at least
        one table2's cached record: (9,'k') paired with (4,9,'k','k'), (5,'k')
        paired with (4,9,'k','k')
        - the two table3 records corresponding to the accepted index tuples are
        retrieved
        - and, in join_matching_records(), joined with the two table2 records
        having distinct key 'k'; the mistake is here; we had determined in
        bka_unique_skip_index_tuple() than the two table3 records 
        would join with at least one cached table2 record; it doesn't mean that
        they join with all cached table2 records. A re-check of the index
        condition is needed. We do it in check_match().
     @ sql/sql_select.h
        subclasses of JOIN_CACHE can now specialize check_match():
        BKA_UNIQUE does so.
[4 Jul 2010 15:47] 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/112832

3209 Guilhem Bichot	2010-07-04
      Fix for BUG#54359 "Extra rows with join_cache_level=7,8 and two joins
      --and multi-column index"; pushed index condition wasn't correctly checked
      in BKA_UNIQUE.
     @ mysql-test/include/join_cache.inc
        test for bug
     @ mysql-test/r/join_cache_jcl1.result
        correct result
     @ mysql-test/r/join_cache_jcl7.result
        without the code fix, result of SELECT would be 5,5,9,9 instead of 9,9
     @ mysql-test/r/join_cache_jcl8.result
        without the code fix, result of SELECT would be 5,5,9,9 instead of 9,9
     @ sql/sql_join_cache.cc
        See added doxygen comments.
        Without this fix, in the testcase (see join_cache.inc) we had this:
        - this is BKA_UNIQUE, which prepares distinct keys for lookup in table3's index,
        which lookup will satisfy
          table3 .`col_varchar_key`  = table2 .`col_varchar_nokey`
        - the two cached records of table2 have the same distinct key prefix 'k'
        - the index condition pushed to table3 is
          table3 .`col_int_key`  >= table2 .`pk`
        - a lookup for 'k' in table3 is done using the available index, the
        found index tuples also provide the value of table3.col_int_key: we have
        (9,'k') and (5,'k')
        - both index tuples are not eliminated by bka_unique_skip_index_tuple() as
        each of them satisfies the pushed condition when paired with at least
        one table2's cached record: (9,'k') paired with (4,9,'k','k'), (5,'k')
        paired with (4,9,'k','k')
        - the two table3 records corresponding to the accepted index tuples are
        retrieved
        - and, in join_matching_records(), joined with the two table2 records
        having distinct key 'k'; the mistake is here; we had determined in
        bka_unique_skip_index_tuple() than the two table3 records 
        would join with at least one cached table2 record; it doesn't mean that
        they join with all cached table2 records. A re-check of the index
        condition is needed. We do it in check_match().
     @ sql/sql_select.h
        subclasses of JOIN_CACHE can now specialize check_match():
        BKA_UNIQUE does so.
[4 Jul 2010 15:49] Guilhem Bichot
queued to next-mr-opt-backporting
[16 Aug 2010 6:31] 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:21] 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)
[23 Nov 2010 3:32] Paul DuBois
Bug does not appear in any released 5.6.x version. No 5.6.1 changelog entry needed.