Bug #28591 MySQL need not sort the records in case of ORDER BY primary_key on InnoDB table
Submitted: 22 May 2007 12:55 Modified: 27 Jul 2007 16:20
Reporter: Vasil Dimov Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:5.0-BK, 5.1 OS:Any
Assigned to: Georgi Kodinov CPU Architecture:Any
Tags: bfsm_2007_05_31, bfsm_2007_06_21, bfsm_2007_06_28

[22 May 2007 12:55] Vasil Dimov
Description:
MySQL does not need to sort the records (Using filesort) when "ORDER BY primary_key" is specified because InnoDB returns the rows in the order of the primary key anyway.

How to repeat:
CREATE TABLE `t` (
  `a` int(11) NOT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`a`),
  KEY `bkey` (`b`)
) ENGINE=InnoDB;

mysql> EXPLAIN SELECT * FROM t WHERE b=10 ORDER BY a\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t
         type: ref
possible_keys: bkey
          key: bkey
      key_len: 5
          ref: const
         rows: 1
        Extra: Using where; Using index; Using filesort
1 row in set (0.01 sec)
[22 May 2007 12:57] Vasil Dimov
Bug#28570 may be related to this.
[22 May 2007 13:01] Heikki Tuuri
Please note that this only holds if we have a WHERE condition like this:

WHERE secondary_key = 12345 ORDER BY primary_key.

InnoDB internally orders secondary index records according to:

<secondary key value, primary key value>
[22 May 2007 13:09] Valeriy Kravchuk
Thank you for a problem report. Yes, I can confirm the EXPLAIN results you got, and they are natural (you ORDER BY PK but optimizer use another index to select rows)... 

If it is known for sure (and it looks so based on some tests I made) that, when accessed by secondary index, rows with the same key value in InnoDB table are returned in PK order, then this can be a useful optimization trick. 

Somebody has to review the InnoDB code carefully to say that, though :)
[16 Jul 2007 14: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/30965

ChangeSet@1.2530, 2007-07-16 17:11:32+03:00, gkodinov@magare.gmz +4 -0
  Bug #28591: MySQL need not sort the records in case of 
  ORDER BY primary_key on InnoDB table
  
  Queries that use an InnoDB secondary index to retrieve
  data don't need to sort in case of ORDER BY primary key.
  This is because InnoDB returns the rows in order of the
  primary key.
  Fixed by preventing temp table sort for queries that use
  secondary index to access the qualifying table data and 
  are ordered on the primary key.
[18 Jul 2007 16:42] 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/31101

ChangeSet@1.2530, 2007-07-18 19:41:45+03:00, gkodinov@magare.gmz +4 -0
  Bug #28591: MySQL need not sort the records in case of 
  ORDER BY primary_key on InnoDB table
  
  Queries that use an InnoDB secondary index to retrieve
  data don't need to sort in case of ORDER BY primary key.
  This is because InnoDB returns the rows in order of the
  primary key.
  Fixed by preventing temp table sort for queries that use
  secondary index to access the qualifying table data and 
  are ordered on the primary key.
[19 Jul 2007 9:30] 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/31157

ChangeSet@1.2530, 2007-07-19 12:30:29+03:00, gkodinov@magare.gmz +4 -0
  Bug #28591: MySQL need not sort the records in case of 
  ORDER BY primary_key on InnoDB table
  
  Queries that use an InnoDB secondary index to retrieve
  data don't need to sort in case of ORDER BY primary key
  if the secondary index is compared to constant(s).
  This is because InnoDB returns the rows in order of the
  primary key.
  Fixed by preventing temp table sort for queries that use
  secondary index to access the qualifying table data and 
  are ordered on the primary key.
[20 Jul 2007 15:38] 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/31252

ChangeSet@1.2530, 2007-07-20 18:37:59+03:00, gkodinov@magare.gmz +4 -0
  Bug #28591: MySQL need not sort the records in case of 
  ORDER BY primary_key on InnoDB table
  
  Queries that use an InnoDB secondary index to retrieve
  data don't need to sort in case of ORDER BY primary key
  if the secondary index is compared to constant(s).
  This is because InnoDB returns the rows in order of the
  primary key.
  Fixed by preventing temp table sort for queries that use
  secondary index to access the qualifying table data and 
  are ordered on the primary key.
[20 Jul 2007 17:13] 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/31275

ChangeSet@1.2530, 2007-07-20 20:13:06+03:00, gkodinov@magare.gmz +4 -0
  Bug #28591: MySQL need not sort the records in case of 
  ORDER BY primary_key on InnoDB table
  
  Queries that use an InnoDB secondary index to retrieve
  data don't need to sort in case of ORDER BY primary key
  if the secondary index is compared to constant(s).
  They can also skip sorting if ORDER BY contains both the
  the secondary key parts and the primary key parts (in
  that order).
  This is because InnoDB returns the rows in order of the
  primary key for rows with the same values of the secondary
  key columns.
  Fixed by preventing temp table sort for the qualifying 
  queries.
[20 Jul 2007 18:05] 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/31280

ChangeSet@1.2530, 2007-07-20 21:05:29+03:00, gkodinov@magare.gmz +4 -0
  Bug #28591: MySQL need not sort the records in case of 
  ORDER BY primary_key on InnoDB table
  
  Queries that use an InnoDB secondary index to retrieve
  data don't need to sort in case of ORDER BY primary key
  if the secondary index is compared to constant(s).
  They can also skip sorting if ORDER BY contains both the
  the secondary key parts and the primary key parts (in
  that order).
  This is because InnoDB returns the rows in order of the
  primary key for rows with the same values of the secondary
  key columns.
  Fixed by preventing temp table sort for the qualifying 
  queries.
[26 Jul 2007 5:55] Bugs System
Pushed into 5.1.21-beta
[26 Jul 2007 5:56] Bugs System
Pushed into 5.0.48
[26 Jul 2007 16: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/31637

ChangeSet@1.2481, 2007-07-26 20:52:53+04:00, sergefp@mysql.com +4 -0
  BUG#28591: make the fix work for BDB tables too:
   - make ha_berkeley::cmp_ref() take into account that auto-generated PKs 
     are stored in LSB-first order. 
   - Remove the temporary code that made the bugfix work for innodb only
[27 Jul 2007 16:20] Paul DuBois
Noted in 5.0.48, 5.1.21 changelogs.

For InnoDB tables, MySQL unnecessarily sorted records in certain
cases when the records were retrieved by InnoDB in the proper order
already.
[2 Aug 2007 19:13] Bugs System
Pushed into 5.1.21-beta
[2 Aug 2007 19:15] Bugs System
Pushed into 5.0.48
[14 Sep 2007 3:27] James Day
See bug  #31001 apparently introduced by this performance improvement:

select * from test where nr=2 order by id asc;
select * from test where nr=2 order by id desc;

now ignore the order direction.