"order by" gives unordered results

[Patric Stout (Fox-IT)]

Take the following table structure:

CREATE TABLE `sorting` (
  `id` int(11) unsigned NOT NULL,
  `data` varchar(10) DEFAULT NULL,
  KEY `data_idx` (`data`(2),`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
/*!50100 PARTITION BY RANGE (`id`)
(PARTITION p10 VALUES LESS THAN (10) ENGINE = InnoDB,
 PARTITION p20 VALUES LESS THAN (20) ENGINE = InnoDB) */;

In them, introduce the following values:

INSERT INTO `sorting` VALUES
 (9,'aa2'),
 (11,'aa2'),
 (12,'aa2')
;

At this point, everything is as expected. Now introduce the following value:

INSERT INTO `sorting` VALUES (13,'aa1');

And query the table:

SELECT id FROM sorting WHERE data = 'aa2' ORDER BY id DESC;

You would expect an ordered list. But in result you get:

+----+
| id |
+----+
| 9 |
| 12 |
| 11 |
+----+

Observations / things to note:

- The INDEX is a combination of two fields
- The INDEX has a field which is a part of the full field
- The table uses partitions
- The bug does not happen if you insert in only one partition
- The bug does not happen if the part of the 'data' that is in the index is different; it only happens if that part is the same, but the remaining is different ('aa1' vs 'aa2')
- Restarting MySQL resolves the issue for the current values (but new values get the same error)
- Happens on 5.6.32, 5.6.34, 5.7.16
- ORDER BY ASC works as expected
- With more data, it can also happen dat ORDER BY DESC shows only 2 results, where ORDER BY ASC shows 40 results, for example (in other words, ORDER BY DESC gives partial results).

[Jackie Xu (aeveus)]

I was able to break the ascending order by using the same table:

CREATE TABLE `sorting` (
  `id` int(11) unsigned NOT NULL,
  `data` varchar(10) DEFAULT NULL,
  KEY `data_idx` (`data`(2),`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8
/*!50100 PARTITION BY RANGE (`id`)
(PARTITION p10 VALUES LESS THAN (10) ENGINE = InnoDB,
 PARTITION p20 VALUES LESS THAN (20) ENGINE = InnoDB) */;

and the same initial inserts:

INSERT INTO `sorting` VALUES
 (9,'aa2'),
 (11,'aa2'),
 (12,'aa2')
;

but a different final insert:

INSERT INTO `sorting` VALUES (9,'aa3');

Now query the table:

SELECT id FROM sorting WHERE data = 'aa2' ORDER BY id ASC;

The following result shows up:

+----+
| id |
+----+
| 11 |
| 12 |
| 9 |
+----+

Strangely enough, removing the order by actually gives the correctly ordered result:

SELECT id FROM sorting WHERE data = `aa2`;

+----+
| id |
+----+
| 9 |
| 11 |
| 12 |
+----+

[Jackie Xu (aeveus)]

Slight change to the above comment. The final insert should be:

INSERT INTO `sorting` VALUES (8,'aa3');

[Jackie Xu (aeveus)]

Some additional observations:
- Problem appears to persist after restart (on my local VM running 5.7.11).
- Results are ordered correctly if the index columns are swapped (i.e. (`id`, `data`(2)) instead of (`data`(2), `id`).
- Looks like the values sorted in a partition are cut off at the part where a row appears with a different `data` value (but with the same part in the index).

Test values:
INSERT INTO `sorting` VALUES
 /* p10 */
 (1,'aa2'),
 (2,'aa2'),
 (3,'aa2'),
 /* p20 */
 (11,'aa2'),
 (12,'aa2'),
 (13,'aa2')
;

Introduce the following 'splitting point' values:
INSERT INTO `sorting` VALUES
 /* Break ASC order */
 (2,'aa3'),
 /* Break DESC order */
 (12,'aa1')
;

For the ascending order, MySQL sorts both partitions, and then appends the sorted p456 to p123. Insert a row in between the values of p123 with a greater alphabetical value will result in the rest of the partition being ordered by that greater alphabetical value.

Add an insert to make ordering more clear:
INSERT INTO `sorting` VALUES (4,'aa2'), (5, 'aa2');

+----+-----+
| 1 | aa2 |
| 2 | aa2 |
| 2 | aa3 | <-- Partition order splits here, all greater id values will be appended below p20
| 3 | aa2 |
| 4 | aa2 |
| 5 | aa2 |
+----+-----+
| 11 | aa2 |
| 12 | aa2 |
| 13 | aa2 |
+----+-----+

Resulting rows:

mysql> SELECT id FROM sorting WHERE data = 'aa2' ORDER BY id;
+----+
| id |
+----+
| 1 |
| 2 |
| 11 |
| 12 |
| 13 |
| 3 |
| 4 |
| 5 |
+----+

Same thing works for descending order and alphabetical ordering reversed.

[Jackie Xu (aeveus)]

Also added to the MySQL bug tracker: http://bugs.mysql.com/bug.php?id=84070

[Shahriyar Rzayev (rzayev-sehriyar)]

Percona now uses JIRA for bug reports so this bug report is migrated to: https://jira.percona.com/browse/PS-1035