[MDEV-7485]  ORDER BY DESC and LIMIT produces wrong results Created: 2015-01-21  Updated: 2015-01-28  Resolved: 2015-01-28

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.0.9, 10.0.15, 10.1.2
Fix Version/s: N/A

Type: Bug Priority: Major
Reporter: Zhixin Zhang Assignee: Sergei Petrunia
Resolution: Not a Bug Votes: 0
Labels: optimizer
Environment:

ubuntu 12.04 x64, ubuntu 10.04 x64


 Description   

When SELECT using ORDER BY DESC and LIMIT if the sorting column has the same value would produce unexpected results on MariaDB 10.0 and 10.1 series;

Reproducible on MariaDB version: 10.0.15, 10.1.2.
Was NOT able to reproduce on MariaDB
versions: 5.5.33a.

I just tested on the above versions.

How to reproduce:
1. on MariaDB version: 10.1.2, 10.0.15, 10.0.9(unexpected results)

-- create table 
CREATE TABLE `zzz` (
 
  `a` int(11) DEFAULT NULL,
 
  `b` int(11) DEFAULT NULL
 
) ENGINE=InnoDB
 
 
 
-- insert some data
 
insert into zzz(a,b) values
 
(101679,1395219593),
 
(103040,1395219593),
 
(12375542,1395219593),
 
(29263588,1395219593),
 
(30408843,1395219593),
 
(50000010,1395219593),
 
(55555544,1395219593),
 
(10000,1395219593);
 
(75188381,1395219593),
 
(85651228,1395219593);
 
 
 
-- query and results set
 
> select * from zzz order by b desc ;
 
+----------+------------+
 
| a        | b          |
 
+----------+------------+
 
| 85651228 | 1395219593 |
 
| 75188381 | 1395219593 |
 
| 55555544 | 1395219593 |
 
| 50000010 | 1395219593 |
 
| 30408843 | 1395219593 |
 
| 29263588 | 1395219593 |
 
| 12375542 | 1395219593 |
 
|   103040 | 1395219593 |
 
|   101679 | 1395219593 |
 
|    10000 | 1395219593 |
 
+----------+------------+
 
 
 
> select * from zzz order by b desc limit 0,6;
 
+----------+------------+
 
| a        | b          |
 
+----------+------------+
 
|    10000 | 1395219593 |
 
|   101679 | 1395219593 |
 
|   103040 | 1395219593 |
 
| 12375542 | 1395219593 |
 
| 29263588 | 1395219593 |
 
| 30408843 | 1395219593 |
 
+----------+------------+
 
 
 
> select * from zzz order by b desc limit 6,6;
 
+----------+------------+
 
| a        | b          |
 
+----------+------------+
 
| 12375542 | 1395219593 |
 
|   103040 | 1395219593 |
 
|   101679 | 1395219593 |
 
|    10000 | 1395219593 |
 
+----------+------------+
 
 
 
Here the last two query produce some duplicate data.

2. do the same on MariaDB 5.5.33a( expected results)

-- query and results set
 
>  select * from zzz order by b desc ;
 
+----------+------------+
 
| a        | b          |
 
+----------+------------+
 
| 85651228 | 1395219593 |
 
| 75188381 | 1395219593 |
 
| 55555544 | 1395219593 |
 
| 50000010 | 1395219593 |
 
| 30408843 | 1395219593 |
 
| 29263588 | 1395219593 |
 
| 12375542 | 1395219593 |
 
|   103040 | 1395219593 |
 
|   101679 | 1395219593 |
 
|    10000 | 1395219593 |
 
+----------+------------+
 
 
 
> select * from zzz order by b desc limit 0,6;
 
+----------+------------+
 
| a        | b          |
 
+----------+------------+
 
| 85651228 | 1395219593 |
 
| 75188381 | 1395219593 |
 
| 55555544 | 1395219593 |
 
| 50000010 | 1395219593 |
 
| 30408843 | 1395219593 |
 
| 29263588 | 1395219593 |
 
+----------+------------+
 
 
 
> select * from zzz order by b desc limit 6,6;
 
+----------+------------+
 
| a        | b          |
 
+----------+------------+
 
| 12375542 | 1395219593 |
 
|   103040 | 1395219593 |
 
|   101679 | 1395219593 |
 
|    10000 | 1395219593 |
 
+----------+------------+
 
result is as expected.



 Comments   
Comment by Elena Stepanova [ 2015-01-23 ]

Same in MySQL 5.6 and current MariaDB 5.5 tree.

Comment by Sergei Petrunia [ 2015-01-28 ]

The output of each individual query is correct. The ordering of rows that have the same value of ORDER BY column is not defined.

If you desire that "...LIMIT 0,6" and "... LIMIT 6,6" queries provided a consistent view of data table zzz, include column a in the ORDER BY list:

select * from zzz order by b desc, a limit 0,6;
 
select * from zzz order by b desc, a limit 6,6;

Comment by Sergei Petrunia [ 2015-01-28 ]

I've also debugged to see why it happens.

Older versions of MySQL/MariaDB resolve the ORDER BY query using "filesort" strategy. That's basically a quicksort which overflows to disk.

Newer versions of MySQL/MariaDB use a Priority Queue for optimizing queries with ORDER BY ... LIMIT: https://mariadb.com/kb/en/mariadb/filesort-with-small-limit-optimization/.
When a query needs only first N rows, we use priority queue of size N. Priority queues of different sizes will make different comparisons, if there are multiple rows with the same sort value, different rows may be discarded. Queries with "LIMIT n" and "LIMIT m" may produce results which do not agree with each other (but both are correct).

If I force priority queue not to be used (this can only be done in debugger), the output becomes consistent again.

Comment by Sergei Petrunia [ 2015-01-28 ]

Because of the above, I think this is not a bug.

Generated at Thu Feb 08 07:19:57 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.