Bug #17212 results not sorted correctly by ORDER BY when using index
Submitted: 7 Feb 2006 23:09 Modified: 24 Apr 2007 16:40
Reporter: Timothy Smith Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S1 (Critical)
Version:4.1.18, 5.0.18, 4.0.26 OS:Linux (linux)
Assigned to: Georgi Kodinov

[7 Feb 2006 23:09] Timothy Smith
Description:
A query with ORDER BY returns results in the wrong order when reading from a key.

I tried this on MySQL 4.1.18-nightly, 5.0.18-release, and 4.0.26-release (not broken).

The same query fails on 4.1.18 and 5.0.18, but returns correct results (but slow) on 4.0.26.

The results, when the query is run on MySQL 5.0.18, returns rows in *mostly* sorted order, but there are some chunks out of order.  I mean, the results include these:

+---------------------+-------+
| created             | a_id  |
+---------------------+-------+
| 2005-06-11 20:57:46 |   460 |
| 2005-06-27 14:32:21 |   827 |
| 2005-06-29 15:01:35 |   861 |
... rows in order ...
| 2005-11-25 19:09:40 | 10475 |
| 2005-11-25 19:22:19 | 10476 |
| 2005-02-24 09:34:57 |    12 |
| 2005-02-24 09:34:58 |    13 |
... rows in order ...
| 2006-02-04 01:16:06 | 39111 |
| 2006-02-04 01:16:47 | 39112 |
| 2006-01-23 17:01:38 | 30918 |
| 2006-01-23 22:05:52 | 31151 |
... rows in order ...

How to repeat:

Full SQL dump will be mentioned in private comment (it uses private data).

The basic query which doesn't sort properly is this:

select
    a.created, a.a_id
from
    a
    join
    a_has_b ahb1
    on (ahb1.a_id = a.a_id)
    join
    a_b ab1
    on (ab1.a_b_id = ahb1.a_b_id)
where
    a.s1 = 1
    and a.s2 = 0
    and a.s3 = 0
    and a.s4 = 0
    and a.s5 = 0

    and ab1.label = 'label1'
    and ab1.value in ('Value 1', 'Value 2')
order by
    a.created
;

Here is the schema involved:

CREATE TABLE `a` (
  `a_id` int(10) unsigned NOT NULL default '0',
  `created` datetime NOT NULL default '0000-00-00 00:00:00',
  `s2` tinyint(4) NOT NULL default '0',
  `s5` tinyint(4) NOT NULL default '0',
  `s1` tinyint(4) NOT NULL default '0',
  `s4` tinyint(4) NOT NULL default '0',
  `s3` tinyint(4) NOT NULL default '0',
  PRIMARY KEY  (`a_id`),
  KEY `created` (`created`),
  KEY `s1` (`s1`),
  KEY `s2` (`s2`),
  KEY `s3` (`s3`),
  KEY `s4` (`s4`),
  KEY `s5` (`s5`),
  KEY `status` (`s1`,`s2`,`s3`,`s4`,`s5`,`created`)
) TYPE=InnoDB;

CREATE TABLE `a_has_b` (
  `a_id` int(10) unsigned NOT NULL default '0',
  `a_b_id` int(10) unsigned NOT NULL default '0',
  PRIMARY KEY  (`a_b_id`,`a_id`)
) ENGINE=InnoDB;

CREATE TABLE `a_b` (
  `a_b_id` smallint(6) unsigned NOT NULL default '0',
  `label` varchar(50) NOT NULL default '',
  `value` varchar(50) NOT NULL default '',
  PRIMARY KEY  (`a_b_id`),
  UNIQUE KEY `label` (`label`,`value`),
  KEY `a_b_id` (`a_b_id`,`label`,`value`)
) ENGINE=InnoDB;

Note that I tried removing the a_b table from the join, using this query, but it returned the results in correct sorted order:

select
    a.created, a.a_id
from
    a
    join
    a_has_b ahb1
    on (ahb1.a_id = a.a_id)
where
    a.s1 = 1
    and a.s2 = 0
    and a.s3 = 0
    and a.s4 = 0
    and a.s5 = 0

    and ahb1.a_b_id in (1, 2)
order by
    a.created
;

============================
EXPLAIN on 5.0
============================

mysql> explain select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where a.s1 = 1 and a.s2 = 0 and a.s3 = 0 and a.s4 = 0 and a.s5 = 0 and ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: a
         type: ref
possible_keys: PRIMARY,s1,s2,s3,s4,s5,status
          key: status
      key_len: 5
          ref: const,const,const,const,const
         rows: 24444
        Extra: Using where; Using index
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: ab1
         type: range
possible_keys: PRIMARY,label,a_b_id
          key: label
      key_len: 104
          ref: NULL
         rows: 2
        Extra: Using where; Using index
*************************** 3. row ***************************
           id: 1
  select_type: SIMPLE
        table: ahb1
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: bug.ab1.a_b_id,bug.a.a_id
         rows: 1
        Extra: Using where; Using index
3 rows in set (0.00 sec)

============================
EXPLAIN on 4.1
============================

mysql> explain select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where a.s1 = 1 and a.s2 = 0 and a.s3 = 0 and a.s4 = 0 and a.s5 = 0 and ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: a
         type: ref
possible_keys: PRIMARY,s1,s2,s3,s4,s5,status
          key: status
      key_len: 5
          ref: const,const,const,const,const
         rows: 16182
        Extra: Using where; Using index
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: ab1
         type: range
possible_keys: PRIMARY,label,a_b_id
          key: label
      key_len: 100
          ref: NULL
         rows: 2
        Extra: Using where; Using index
*************************** 3. row ***************************
           id: 1
  select_type: SIMPLE
        table: ahb1
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: bug.ab1.a_b_id,bug.a.a_id
         rows: 1
        Extra: Using where; Using index
3 rows in set (0.00 sec)

============================
EXPLAIN on 4.0
============================

mysql> explain select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where a.s1 = 1 and a.s2 = 0 and a.s3 = 0 and a.s4 = 0 and a.s5 = 0 and ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created\G
*************************** 1. row ***************************
        table: a
         type: ref
possible_keys: PRIMARY,s1,s2,s3,s4,s5,status
          key: status
      key_len: 5
          ref: const,const,const,const,const
         rows: 18305
        Extra: Using where; Using index
*************************** 2. row ***************************
        table: ab1
         type: range
possible_keys: PRIMARY,label,a_b_id
          key: label
      key_len: 100
          ref: NULL
         rows: 2
        Extra: Using where; Using index
*************************** 3. row ***************************
        table: ahb1
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: ab1.a_b_id,a.a_id
         rows: 1
        Extra: Using where; Using index
3 rows in set (0.00 sec)

Suggested fix:

unknown
[8 Feb 2006 0:49] Timothy Smith
I have pared the test case down a bit.  This is all on the 4.0.26 server.  It uses a different  plan, if I use a LIMIT clause (wrong results now) or without (correct results).  I've dropped all indexes from table a:

CREATE TABLE `a` (
  `a_id` int(10) unsigned NOT NULL default '0',
  `created` datetime NOT NULL default '0000-00-00 00:00:00'
) TYPE=InnoDB;

Here is the explain, and results, with the LIMIT clause:

mysql> explain select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created limit 10\G
*************************** 1. row ***************************
        table: a
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 36160
        Extra: Using filesort
*************************** 2. row ***************************
        table: ab1
         type: range
possible_keys: PRIMARY,label,a_b_id
          key: label
      key_len: 100
          ref: NULL
         rows: 2
        Extra: Using where; Using index
*************************** 3. row ***************************
        table: ahb1
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: ab1.a_b_id,a.a_id
         rows: 1
        Extra: Using where; Using index
3 rows in set (0.00 sec)

mysql> select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created limit 10; 
+---------------------+------+
| created             | a_id |
+---------------------+------+
| 2005-06-11 20:57:46 |  460 |
| 2005-06-27 14:32:21 |  827 |
| 2005-06-29 15:01:35 |  861 |
| 2005-06-29 15:16:26 |  863 |
| 2005-06-29 15:19:11 |  864 |
| 2005-06-29 15:21:37 |  865 |
| 2005-06-29 15:23:09 |  866 |
| 2005-06-29 16:03:13 |  867 |
| 2005-06-29 17:05:10 |  868 |
| 2005-06-29 17:20:54 |  869 |
+---------------------+------+
10 rows in set (0.71 sec)

And now, the EXPLAIN and results without the limit:

mysql> explain select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created\G
*************************** 1. row ***************************
        table: ab1
         type: range
possible_keys: PRIMARY,label,a_b_id
          key: label
      key_len: 100
          ref: NULL
         rows: 2
        Extra: Using where; Using index; Using temporary; Using filesort
*************************** 2. row ***************************
        table: a
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 36160
        Extra: 
*************************** 3. row ***************************
        table: ahb1
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: ab1.a_b_id,a.a_id
         rows: 1
        Extra: Using where; Using index
3 rows in set (0.00 sec)

mysql> pager head -20
PAGER set to head -20
mysql> select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created; 
+---------------------+-------+
| created             | a_id  |
+---------------------+-------+
| 2005-02-24 09:34:57 |    12 |
| 2005-02-24 09:34:58 |    13 |
| 2005-02-24 09:34:59 |    14 |
| 2005-02-24 09:35:00 |    15 |
| 2005-02-24 09:35:00 |    16 |
| 2005-02-24 09:35:01 |    17 |
| 2005-02-24 09:35:05 |    23 |
| 2005-02-24 09:35:06 |    24 |
| 2005-02-24 09:35:08 |    27 |
| 2005-02-24 09:35:09 |    28 |
| 2005-02-24 09:35:10 |    30 |
| 2005-02-24 09:35:10 |    29 |
| 2005-02-24 09:35:13 |    33 |
| 2005-02-24 09:35:13 |    34 |
| 2005-02-24 09:35:14 |    35 |
| 2005-02-24 09:35:15 |    37 |
| 2005-02-24 09:35:17 |    38 |
41770 rows in set (3.30 sec)

I hope this is helpful.

Regards,

Timothy
[27 Jun 2006 10:09] Georgi Kodinov
Replayed the dump file and executed the query in question on 4.1.21 and 5.0.23.
On both platforms I got correctly sorted data.
[28 Jun 2006 16:19] Timothy Smith
I can still repeat this with a 4.1.21-bk build from < 12 hours ago.

Fetch the following test case SQL file:

/nfstmp1/tsmith/bug17212-2.sql.gz

See the below steps:

12:06 ~/m/41/bug17212$ ./runserver 
Running [ ./bin/mysqld_safe --no-defaults --basedir=$PWD --datadir=$PWD/data --language=$PWD/share/mysql/english --tmpdir=$PWD/tmp --log-error=$PWD/data/log.err --socket=mysql.sock --port=33410 --server-id=33410 --log-bin=binlog  & ]
Starting mysqld daemon with databases from /usr/home/tim/m/41/bug17212/data
12:06 ~/m/41/bug17212$ gzip -cd ../m/bug17212-2.sql.gz| mysql test
12:06 ~/m/41/bug17212$ mysql test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 2 to server version: 4.1.21-debug-log

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> pager head -20
PAGER set to 'head -20'
mysql> select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created limit 10;
+---------------------+------+
| created             | a_id |
+---------------------+------+
| 2005-06-11 20:57:46 |  460 |
| 2005-06-27 14:32:21 |  827 |
| 2005-06-29 15:01:35 |  861 |
| 2005-06-29 15:16:26 |  863 |
| 2005-06-29 15:19:11 |  864 |
| 2005-06-29 15:21:37 |  865 |
| 2005-06-29 15:23:09 |  866 |
| 2005-06-29 16:03:13 |  867 |
| 2005-06-29 17:05:10 |  868 |
| 2005-06-29 17:20:54 |  869 |
+---------------------+------+
10 rows in set (0.26 sec)

mysql> select a.created, a.a_id from a join a_has_b ahb1 on (ahb1.a_id = a.a_id) join a_b ab1 on (ab1.a_b_id = ahb1.a_b_id) where ab1.label = 'label1' and ab1.value in ('Value 1', 'Value 2') order by a.created;
+---------------------+-------+
| created             | a_id  |
+---------------------+-------+
| 2005-02-24 09:34:57 |    12 |
| 2005-02-24 09:34:58 |    13 |
| 2005-02-24 09:34:59 |    14 |
| 2005-02-24 09:35:00 |    15 |
| 2005-02-24 09:35:00 |    16 |
| 2005-02-24 09:35:01 |    17 |
| 2005-02-24 09:35:05 |    23 |
| 2005-02-24 09:35:06 |    24 |
| 2005-02-24 09:35:08 |    27 |
| 2005-02-24 09:35:09 |    28 |
| 2005-02-24 09:35:10 |    29 |
| 2005-02-24 09:35:10 |    30 |
| 2005-02-24 09:35:13 |    33 |
| 2005-02-24 09:35:13 |    34 |
| 2005-02-24 09:35:14 |    35 |
| 2005-02-24 09:35:15 |    37 |
| 2005-02-24 09:35:17 |    38 |
41770 rows in set (2.16 sec)

mysql> show variables like 'version%';
+-------------------------+-----------------------------------------------------
| Variable_name           | Value                                               
+-------------------------+-----------------------
| version                 | 4.1.21-debug-log      
| version_bdb             | Sleepycat Software: Be
| version_comment         | Source distribution   
| version_compile_machine | i386                  
| version_compile_os      | unknown-freebsd6.1    
+-------------------------+-----------------------

Notice that the first 10 results (with LIMIT) are sorted among themselves, but are NOT the first 10 results from the query without the LIMIT clause.

Please try it again with that SQL test data.  Thanks!
[7 Jul 2006 15:09] 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/8916
[12 Jul 2006 7:58] 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/9079
[18 Jul 2006 23:54] Evgeny Potemkin
Don't use join cache when the incoming data set is already ordered
for ORDER BY
This choice must be made because join cache will effectively
reverse the join order and the results will be sorted by the index
of the table that uses join cache.

Fixed in 4.1.22, 5.0.25
[20 Jul 2006 15:50] Paul Dubois
Noted in 4.1.22, 5.0.25 changelogs.

Use of the join cache in favor of an index for ORDER BY operations
could cause incorrect result sorting.
[21 Apr 2007 15:19] Bugs System
Pushed into 5.1.18-beta
[21 Apr 2007 15:20] Bugs System
Pushed into 5.0.42
[24 Apr 2007 16:40] Paul Dubois
Closing report. The last two push messages
are bogus.