| 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: | |
| 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 | ||
[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.
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)