Bug #45828 Optimizer won't use partial primary key if another index can prevent filesort
Submitted: 29 Jun 2009 15:55 Modified: 6 Aug 2009 15:01
Reporter: Harrison Fisk Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:5.1.35, 5.1.37-bzr, 5.4.0 OS:Any
Assigned to: Georgi Kodinov CPU Architecture:Any
Tags: innodb, Optimizer, order by, primary key, regression
Triage: Triaged: D2 (Serious) / R3 (Medium) / E3 (Medium)

[29 Jun 2009 15:55] Harrison Fisk
Description:
With InnoDB tables, MySQL will use a less ideal index in order to avoid a filesort, even if the prefix of the primary key is much more selective.

With InnoDB, you should prefer to use the primary key when you can, and even in this case, the primary key is the proper choice regardless of clustered index nature.

5.0 does not exhibit this behavior, but both 5.1 and 5.4 do.

This might be related to Bug #28404, but I do not think so.

See how to repeat for more details of exact queries.

How to repeat:
-- Create the table
CREATE TABLE `t1` (
  `c1` int(11) unsigned NOT NULL DEFAULT '0',
  `c2` int(11) unsigned NOT NULL DEFAULT '0',
  `c3` int(11) unsigned NOT NULL DEFAULT '0',
  PRIMARY KEY (`c1`,`c2`),
  KEY `c3` (`c3`)
) ENGINE=InnoDB;

-- populate with data
INSERT INTO `t1` VALUES (5,2,1246276747);
INSERT INTO `t1` VALUES (2,1,1246281721);
INSERT INTO `t1` VALUES (7,3,1246281756);
INSERT INTO `t1` VALUES (4,2,1246282139);
INSERT INTO `t1` VALUES (3,1,1246282230);
INSERT INTO `t1` VALUES (1,0,1246282712);
INSERT INTO `t1` VALUES (8,3,1246282765);
INSERT INTO t1 SELECT c1+10,c2+10,c3+10 FROM t1;
insert into t1 select c1+100,c2+100,c3+100 from t1;
insert into t1 select c1+1000,c2+1000,c3+1000 from t1;
insert into t1 select c1+10000,c2+10000,c3+10000 from t1;
insert into t1 select c1+100000,c2+100000,c3+100000 from t1;
insert into t1 select c1+1000000,c2+1000000,c3+1000000 from t1;

-- query and no rows will match the c1 condition, whereas all will match c3
SELECT * FROM t1 WHERE c1 = 99999999 AND c3 > 1 ORDER BY c3;

-- index on c3 will be used instead of primary key
explain SELECT * FROM t1 WHERE c1 = 99999999 AND c3 > 1 ORDER BY c3;

-- if we force the primary key, we can see the estimate is 1 
explain SELECT * FROM t1 force index (primary) WHERE c1 = 99999999 AND c3 > 1 ORDER BY c3;

-- if we switch to myisam, PRIMARY KEY is used properly
ALTER TABLE t1 ENGINE=MyISAM;
explain SELECT * FROM t1 WHERE c1 = 99999999 AND c3 > 1 ORDER BY c3;
ALTER TABLE t1 ENGINE=InnoDB;

-- if we switch it from a primary key to a regular index, it works correctly as well
ALTER TABLE t1 DROP PRIMARY KEY, ADD INDEX `test` (c1, c2);
explain SELECT * FROM t1 WHERE c1 = 99999999 AND c3 > 1 ORDER BY c3;
ALTER TABLE t1 DROP INDEX test, ADD PRIMARY KEY (c1, c2);

Suggested fix:
Use the primary key when it makes sense to.
[29 Jun 2009 16:14] Valeriy Kravchuk
Note that this bug is InnoDB-specific and it is NOT related to wrong cardinality estimations. So, something is wrong with PRIMARY KEY-related logic in case of InnoDB.
[30 Jun 2009 19:54] Harrison Fisk
This is a regression that was introduced in 5.1.  The behavior was correct in 5.0 and early 5.1 releases.

There is no query pattern where this behavior is good, it is not by design.  

The fact that the behavior is correct if you replace the primary key with a unique or regular index shows that it is incorrect handling of InnoDB primary keys.

This is not a feature request.  It is a bug (ie. software not working as designed).
[1 Jul 2009 14:34] Georgi Kodinov
This is an side effect of the fix for bug #28404. Now it unconditionally prefers covering keys over ref access keys (except when the ref access key is also covering).
[3 Jul 2009 10:32] 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/77871

2990 Georgi Kodinov	2009-07-03
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering indexes to be preferred 
      over non-covering in the following two cases : 
       - when comparing the ordering indexes among themselves
       - when comparing the ref key to ordering indexes.
      
      Fixed by not considering the ordering indexes supperior to the 
      ref key. They're only supperior to non-covering ordering indexes. 
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.
[6 Jul 2009 14:56] 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/78030

2990 Georgi Kodinov	2009-07-06
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering ordering indexes to be 
      preferred unconditionally over non-covering and ref indexes.
      
      Fixed by comparing the cost of using a covering index to the cost of
      using a ref index even for covering ordering indexes.
      Added an assertion to clarify the condition the local variables should
      be in.
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.
[7 Jul 2009 12:53] 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/78124

2990 Georgi Kodinov	2009-07-07
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering ordering indexes to be 
      preferred unconditionally over non-covering and ref indexes.
      
      Fixed by comparing the cost of using a covering index to the cost of
      using a ref index even for covering ordering indexes.
      Added an assertion to clarify the condition the local variables should
      be in.
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.
[9 Jul 2009 15:11] 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/78293

3017 Georgi Kodinov	2009-07-07
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering ordering indexes to be 
      preferred unconditionally over non-covering and ref indexes.
      
      Fixed by comparing the cost of using a covering index to the cost of
      using a ref index even for covering ordering indexes.
      Added an assertion to clarify the condition the local variables should
      be in.
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.
[10 Jul 2009 11:21] Bugs System
Pushed into 5.4.4-alpha (revid:anozdrin@bk-internal.mysql.com-20090710111017-bnh2cau84ug1hvei) (version source revid:joro@sun.com-20090709161101-iov57k1sd3q7kve3) (merge vers: 5.4.4-alpha) (pib:11)
[13 Jul 2009 17:48] Bugs System
Pushed into 5.1.37 (revid:joro@sun.com-20090713174543-cd2x7q1gi1hzoand) (version source revid:staale.smedseng@sun.com-20090710151930-6e6kq5tp7ux1rtbh) (merge vers: 5.1.37) (pib:11)
[15 Jul 2009 16:10] Paul Dubois
Noted in 5.1.37, 5.4.4 changelogs.

With InnoDB tables, MySQL used a less-selective secondary index to
avoid a filesort even if a prefix of the primary key was much more 
selective.
[27 Jul 2009 16:06] saravanan krishnarajan
Hi,

I had problem while patching 5.1.36 with sql_select.cc alone.

[root@my_server mysql-5.1.36]# patch -p1 -i bug-46119.patch 
patching file mysql-test/include/mix1.inc
patching file mysql-test/r/innodb_mysql.result
patching file mysql-test/t/innodb_mysql.test
patching file sql/sql_select.cc
Hunk #1 succeeded at 13131 with fuzz 2 (offset -1 lines).
Hunk #2 FAILED at 13222.

sql_select.cc.rej:

***************
*** 13214,13220 ****
          */
            index_scan_time= select_limit/rec_per_key *
                           min(rec_per_key, table->file->scan_time());
-           if (is_covering ||
                (ref_key < 0 && (group || table->force_index)) ||
                index_scan_time < read_time)
            {
--- 13222,13228 ----
          */
            index_scan_time= select_limit/rec_per_key *
                           min(rec_per_key, table->file->scan_time());
+           if ((ref_key < 0 && is_covering) ||
                (ref_key < 0 && (group || table->force_index)) ||
                index_scan_time < read_time)
            {
[5 Aug 2009 19:57] James Day
Docs, please add the performance tag to the changelog entry for this bug fix.
[6 Aug 2009 15:01] Paul Dubois
Done.
[12 Aug 2009 21:47] Paul Dubois
Noted in 5.4.2 changelog because next 5.4 version will be 5.4.2 and not 5.4.4.
[14 Aug 2009 22:43] Paul Dubois
Ignore previous comment about 5.4.2.
[26 Aug 2009 13:46] Bugs System
Pushed into 5.1.37-ndb-7.0.8 (revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (version source revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (merge vers: 5.1.37-ndb-7.0.8) (pib:11)
[26 Aug 2009 13:46] Bugs System
Pushed into 5.1.37-ndb-6.3.27 (revid:jonas@mysql.com-20090826105955-bkj027t47gfbamnc) (version source revid:jonas@mysql.com-20090826105955-bkj027t47gfbamnc) (merge vers: 5.1.37-ndb-6.3.27) (pib:11)
[26 Aug 2009 13:48] Bugs System
Pushed into 5.1.37-ndb-6.2.19 (revid:jonas@mysql.com-20090825194404-37rtosk049t9koc4) (version source revid:jonas@mysql.com-20090825194404-37rtosk049t9koc4) (merge vers: 5.1.37-ndb-6.2.19) (pib:11)
[27 Aug 2009 16:33] Bugs System
Pushed into 5.1.35-ndb-7.1.0 (revid:magnus.blaudd@sun.com-20090827163030-6o3kk6r2oua159hr) (version source revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (merge vers: 5.1.37-ndb-7.0.8) (pib:11)
[7 Oct 2009 1:20] Paul Dubois
The 5.4 fix has been pushed into 5.4.2.
[11 Dec 2009 11:03] Gleb Shchepa
Bug #44969 is a duplicate of this bug.