Bug #38397 select distinct + order by desc is executed inefficiently
Submitted: 27 Jul 2008 20:13 Modified: 28 Jul 2008 3:18
Reporter: Vladimir Kolesnikov Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.1.26, 5.0.62 OS:Any
Assigned to: CPU Architecture:Any
Tags: DESC, distinct, order by, parser, performance, regression, SELECT
Triage: Triaged: D2 (Serious) / R4 (High) / E3 (Medium)

[27 Jul 2008 20:13] Vladimir Kolesnikov
Description:
SELECT DISTINCT + ORDER BY DESC causes unnecessary filesort

How to repeat:
mysql> show create table t3 \G
*************************** 1. row ****
       Table: t3
Create Table: CREATE TABLE `t3` (
  `col1` int(11) DEFAULT NULL,
  `col2` int(11) DEFAULT NULL,
  `col3` int(11) DEFAULT NULL,
  `col4` int(11) DEFAULT NULL,
  KEY `ix1` (`col1`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

the following plan is ok

mysql> explain select distinct col1 from t3 order by col1 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t3
         type: range
possible_keys: NULL
          key: ix1
      key_len: 5
          ref: NULL
         rows: 10
        Extra: Using index for group-by
1 row in set (0.00 sec)

the following plan unexpectedly switches to filesort
(differs from the above only with DESC in ORDER BY)

mysql> explain select distinct col1 from t3 order by col1 desc \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t3
         type: range
possible_keys: NULL
          key: ix1
      key_len: 5
          ref: NULL
         rows: 10
        Extra: Using index for group-by; Using temporary; Using filesort
1 row in set (0.01 sec)
[28 Jul 2008 3:18] Valeriy Kravchuk
Thank you for a problem report. Verified just as described:

C:\Program Files\MySQL\MySQL Server 5.0\bin>mysql -uroot -proot -P3310 test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.1.26-rc-community MySQL Community Server (GPL)

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

mysql> CREATE TABLE `t3` (
    ->   `col1` int(11) DEFAULT NULL,
    ->   `col2` int(11) DEFAULT NULL,
    ->   `col3` int(11) DEFAULT NULL,
    ->   `col4` int(11) DEFAULT NULL,
    ->   KEY `ix1` (`col1`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.09 sec)

mysql> insert into t3 values(1,1,1,1), (1,2,2,2), (2,1,1,1), (3,1,1,1);
Query OK, 4 rows affected (0.03 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> explain select distinct col1 from t3 order by col1 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t3
         type: index
possible_keys: NULL
          key: ix1
      key_len: 5
          ref: NULL
         rows: 4
        Extra: Using index
1 row in set (0.02 sec)

mysql> explain select distinct col1 from t3 order by col1 DESC\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t3
         type: index
possible_keys: NULL
          key: ix1
      key_len: 5
          ref: NULL
         rows: 4
        Extra: Using index
1 row in set (0.00 sec)

Note that while index access method is used plan for DESC case is NOT different. Now, let's add more rows:

mysql> insert into t3 values(3,1,1,1), (4,2,2,2), (5,1,1,1), (6,1,1,1);
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> insert into t3 values(13,1,1,1), (12,2,2,2), (9,1,1,1), (6,2,1,1);
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> explain select distinct col1 from t3 order by col1 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t3
         type: range
possible_keys: NULL
          key: ix1
      key_len: 5
          ref: NULL
         rows: 7
        Extra: Using index for group-by
1 row in set (0.00 sec)

mysql> explain select distinct col1 from t3 order by col1 DESC\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t3
         type: range
possible_keys: NULL
          key: ix1
      key_len: 5
          ref: NULL
         rows: 7
        Extra: Using index for group-by; Using temporary; Using filesort
1 row in set (0.00 sec)

Range method seems inappropriate here, as entire index should be scanned (no WHERE clause at all). 

Note also that we had no problem like this in 4.1.22, so it is a regression.
[15 Apr 2009 23:23] Omer Barnir
triage: setting to SR60BETA as e/r values were not provided and therefor risk is assumed to be high