MySQL Bugs: #21302: Result not properly sorted when using an ORDER BY on a second table in a join

Bug #21302	Result not properly sorted when using an ORDER BY on a second table in a join
Submitted:	26 Jul 2006 16:44	Modified:	25 Sep 2006 19:44
Reporter:	jocelyn fournier (Silver Quality Contributor)	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0.25-BK, 5.0.22	OS:	Any (ALL)
Assigned to:	Georgi Kodinov	CPU Architecture:	Any

Description:
Hi,

I've the following issue :

How to repeat:
CREATE TABLE `test_ligne` (

	`id` tinyint(4) NOT NULL,

	`colonne` varchar(50) NOT NULL,

	PRIMARY KEY  (`id`)

) ENGINE=MyISAM DEFAULT CHARSET=latin1;

INSERT INTO `test_ligne` VALUES (1, 'label_1');

INSERT INTO `test_ligne` VALUES (2, 'label_2');

INSERT INTO `test_ligne` VALUES (3, 'label_3');

INSERT INTO `test_ligne` VALUES (4, 'label_4');

SELECT t1.colonne as a, t2.colonne as b

FROM test_ligne t1 

LEFT JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2)
ORDER BY b;

+---------+---------+
| a       | b       |
+---------+---------+
| label_1 | NULL    | 
| label_2 | label_2 | 
| label_3 | NULL    | 
| label_4 | NULL    | 
+---------+---------+
4 rows in set (0.00 sec)

> The order by in not taken into account

EXPLAIN SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b;
+----+-------------+-------+-------+---------------+------+---------+-------+------+-------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref   | rows | Extra |
+----+-------------+-------+-------+---------------+------+---------+-------+------+-------+
|  1 | SIMPLE      | t1    | ALL   | NULL          | NULL | NULL    | NULL  |    4 |       | 
|  1 | SIMPLE      | t2    | const | id            | id   | 1       | const |    1 |       | 
+----+-------------+-------+-------+---------------+------+---------+-------+------+-------+

SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b IS NULL;
+---------+---------+
| a       | b       |
+---------+---------+
| label_1 | NULL    | 
| label_2 | label_2 | 
| label_3 | NULL    | 
| label_4 | NULL    | 
+---------+---------+
4 rows in set (0.00 sec)

> Same issue here

ALTER TABLE test_ligne DROP PRIMARY KEY, ADD KEY (id);

SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b;
+---------+---------+
| a       | b       |
+---------+---------+
| label_1 | NULL    | 
| label_4 | NULL    | 
| label_3 | NULL    | 
| label_2 | label_2 | 
+---------+---------+
4 rows in set (0.00 sec)

> This is now working properly, and mysql is properly using a temp table + file sort instead of the const optimisation.

EXPLAIN SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b;
+----+-------------+-------+------+---------------+------+---------+-------+------+---------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref   | rows | Extra                           |
+----+-------------+-------+------+---------------+------+---------+-------+------+---------------------------------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL  |    4 | Using temporary; Using filesort | 
|  1 | SIMPLE      | t2    | ref  | id_2          | id_2 | 1       | const |    1 |                                 | 
+----+-------------+-------+------+---------------+------+---------+-------+------+---------------------------------+

Regards,
  Jocelyn

Thank you for a bug report. Verified just as described with 5.0.25-BK on Linux:

mysql> select version();
+-----------+
| version() |
+-----------+
| 5.0.25    |
+-----------+
1 row in set (0.00 sec)

mysql> CREATE TABLE `test_ligne` (
    -> `id` tinyint(4) NOT NULL,
    -> `colonne` varchar(50) NOT NULL,
    -> PRIMARY KEY  (`id`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.01 sec)

mysql> INSERT INTO `test_ligne` VALUES (1, 'label_1');
Query OK, 1 row affected (0.02 sec)

mysql> INSERT INTO `test_ligne` VALUES (2, 'label_2');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `test_ligne` VALUES (3, 'label_3');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO `test_ligne` VALUES (4, 'label_4');
Query OK, 1 row affected (0.00 sec)

mysql> SELECT t1.colonne as a, t2.colonne as b
    -> FROM test_ligne t1
    -> LEFT JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2)
    -> ORDER BY b;
+---------+---------+
| a       | b       |
+---------+---------+
| label_1 | NULL    |
| label_2 | label_2 |
| label_3 | NULL    |
| label_4 | NULL    |
+---------+---------+
4 rows in set (0.00 sec)

mysql> EXPLAIN SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT
 JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 4
        Extra:
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t2
         type: const
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 1
          ref: const
         rows: 1
        Extra:
2 rows in set (0.00 sec)

mysql> SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT JOIN te
st_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b IS NULL;
+---------+---------+
| a       | b       |
+---------+---------+
| label_1 | NULL    |
| label_2 | label_2 |
| label_3 | NULL    |
| label_4 | NULL    |
+---------+---------+
4 rows in set (0.01 sec)

mysql> SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT JOIN te
st_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY (b IS NULL);
+---------+---------+
| a       | b       |
+---------+---------+
| label_1 | NULL    |
| label_2 | label_2 |
| label_3 | NULL    |
| label_4 | NULL    |
+---------+---------+
4 rows in set (0.01 sec)

mysql> ALTER TABLE test_ligne DROP PRIMARY KEY, ADD KEY (id);
Query OK, 4 rows affected (0.03 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT JOIN te
st_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b IS NULL;
+---------+---------+
| a       | b       |
+---------+---------+
| label_2 | label_2 |
| label_1 | NULL    |
| label_4 | NULL    |
| label_3 | NULL    |
+---------+---------+
4 rows in set (0.01 sec)

mysql> EXPLAIN SELECT t1.colonne as a, t2.colonne as b FROM test_ligne t1  LEFT
 JOIN test_ligne t2 ON (t1.id = t2.id AND t2.id = 2) ORDER BY b IS NULL\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 4
        Extra: Using temporary; Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t2
         type: ref
possible_keys: id
          key: id
      key_len: 1
          ref: const
         rows: 1
        Extra:
2 rows in set (0.00 sec)

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/10195

ChangeSet@1.2235, 2006-08-09 14:19:10+03:00, gkodinov@macbook.gmz +4 -0
  Bug #21302: Result not properly sorted when using an ORDER BY on a second 
               table in a join
   The optimizer removes redundant columns in ORDER BY it is considering 
  redundant every reference to const table column, e.g b in :
  create table t1 (a int, b int, primary key(a)); select 1 from t1 
    order by b where a = 1
  
  But it must not remove references to const table columns if the 
  const table is an outer table because there still can be 2 values :
  the const value and NULL. e.g.:
  create table t1 (a int, b int, primary key(a));
  select t2.b c from t1 left join t1 t2 on (t1.a = t2.a and t2.a = 5) 
    order by c;

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/10359

ChangeSet@1.2235, 2006-08-14 15:45:48+03:00, gkodinov@macbook.gmz +4 -0
  Bug #21302: Result not properly sorted when using an ORDER BY on a second 
               table in a join
   The optimizer removes redundant columns in ORDER BY. It is considering 
  redundant every reference to const table column, e.g b in :
  create table t1 (a int, b int, primary key(a)); 
  select 1 from t1 order by b where a = 1
  
  But it must not remove references to const table columns if the 
  const table is an outer table because there still can be 2 values :
  the const value and NULL. e.g.:
  create table t1 (a int, b int, primary key(a));
  select t2.b c from t1 left join t1 t2 on (t1.a = t2.a and t2.a = 5) 
    order by c;

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/10437

ChangeSet@1.2255, 2006-08-15 13:01:04+03:00, gkodinov@rakia.(none) +2 -0
  Bug #21302: Result not properly sorted when using an ORDER BY 
              on a second table in a join
  - undeterministic output of the test case removed.

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/10470

ChangeSet@1.2256, 2006-08-15 15:48:49+03:00, gkodinov@macbook.gmz +2 -0
  Bug #21302: Result not properly sorted when using an ORDER BY on a second table in a join
   - undeterminstic tests fixed

Fixed in 5.0.25

Fixed in 5.1.12

Noted in 5.0.25, 5.1.12 changelogs.