MySQL Bugs: #38397: select distinct + order by desc is executed inefficiently

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

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)

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.

triage: setting to SR60BETA as e/r values were not provided and therefor risk is assumed to be high