MySQL Bugs: #45828: Optimizer won't use partial primary key if another index can prevent filesort

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

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.

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.

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

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

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.

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.

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.

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.

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)

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)

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.

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)
            {

Docs, please add the performance tag to the changelog entry for this bug fix.

Done.

Noted in 5.4.2 changelog because next 5.4 version will be 5.4.2 and not 5.4.4.

Ignore previous comment about 5.4.2.

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)

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)

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)

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)

The 5.4 fix has been pushed into 5.4.2.