MySQL Bugs: #32933: missing results with order by and limit in subquery in combination with indexes

Bug #32933	missing results with order by and limit in subquery in combination with indexes
Submitted:	3 Dec 2007 15:13	Modified:	11 Jan 2008 17:04
Reporter:	Timo Boehme	Email Updates:
Status:	Can't repeat	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0.52, 5.1.22-rc-community	OS:	Windows
Assigned to:	Georgi Kodinov	CPU Architecture:	Any
Tags:	INDEX, limit, order by, result, size, subquery

Description:
MySQL returns wrong results (empty result set) for a query containing a subquery which has order-by clause and limit clause. To trigger the error an index must be defined and the table must be filled with a minimum amount of data.

Since the bug depends on some complexity (data size or number of sort columns) it is hard to find in test scenarios but might happen in production use.

Here is a short description of a minimal test case:
We have a table which contains hierarchical structured data. The hierarchy is defined using a parent-column pointing to the id of the parent entry.

Table:
test (
  id INT PRIMARY KEY,
  parent int,
  INDEX pIdx (parent)) TYPE myisam;

The following query returns the 5-th child of a specified parent:
SELECT c.id
FROM test p, test c
WHERE p.id=2 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORDER BY c2.id LIMIT 4,1);

If we have an index on parent column and a minimum number of child entries of the specified parent entry (approx. 10,000-30,000) and there are further entries pointing to other parent entries (at least 1,000) we get an empty result set whereas we should get one result row.

Decreasing the number of child entries helps to get the correct result.
If we use DESC in the ORDER BY clause the bug shows up with a smaller number of child entries.

See the complete test case in 'How to repeat'.

The bug shows up with MySQL 5.1.22 and 5.0.45 on Windows(XP), 1GB.

How to repeat:
Create a table for hierarchical data:
CREATE TABLE test (id INT PRIMARY KEY, parent int, INDEX pIdx (parent)) TYPE myisam;

Fill table with 3 root entries
INSERT INTO test VALUES (1, null);
INSERT INTO test VALUES (2, null);
INSERT INTO test VALUES (3, null);

Now insert child entries (10,000 for entry 1, 20,000 for entry 2 and 50,000 for entry 3):
INSERT INTO test VALUES(4, 1); ... INSERT INTO test VALUES(10000, 1);
INSERT INTO test VALUES(10001, 2); ... INSERT INTO test VALUES(30000, 2);
INSERT INTO test VALUES(30001, 3); ... INSERT INTO test VALUES(80000, 3);

(I will add a DOS batch file which produces the test data)

Now run the following query - you have to alter X={1,2,3} and either use or don't use DESC:
SELECT c.id
FROM test p, test c
WHERE p.id=X AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORDER BY c2.id [DESC] LIMIT 0,1);

My results are:
X=1, without DESC: 1 row - OK
X=1, with DESC:    1 row - OK
X=2, without DESC: 1 row - OK
X=2, with DESC:    empty set - ERROR (should be 1 row)
X=3, without DESC: empty set - ERROR (should be 1 row)
X=3, with DESC:    empty set - ERROR (should be 1 row)

So with increasing complexity (here using DESC) and increasing data size we have a higher probability for the bug to appear.

DOS batch to create test case

Attachment: mysql-bug_subq_orderby_limit.bat (application/octet-stream, text), 834 bytes.

Thank you for a bug report. Verified just as described. Indeed, after dropping index all the results are correct.

Re-verified with 5.0.52 again. I've downloaded archive, got test table's .frm, .MYI and .MYD files from it, put them in test database's directory. Then:

C:\Program Files\MySQL\MySQL Server 5.0\bin>mysql -uroot -proot test -P3308
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 5
Server version: 5.0.52-enterprise-gpl-nt MySQL Enterprise Server (GPL)

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

mysql> show create table test\G
*************************** 1. row ***************************
       Table: test
Create Table: CREATE TABLE `test` (
  `id` int(11) NOT NULL,
  `parent` int(11) default NULL,
  PRIMARY KEY  (`id`),
  KEY `pIdx` (`parent`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

mysql> SELECT c.id
    -> FROM test p, test c
    -> WHERE p.id=1 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORD
ER BY c2.id LIMIT 0,1);
+----+
| id |
+----+
|  4 |
+----+
1 row in set (0.47 sec)

mysql> SELECT c.id
    -> FROM test p, test c
    -> WHERE p.id=1 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORD
ER BY c2.id DESC LIMIT 0,1);
+-------+
| id    |
+-------+
| 10000 |
+-------+
1 row in set (0.09 sec)

mysql> SELECT c.id
    -> FROM test p, test c
    -> WHERE p.id=2 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORD
ER BY c2.id LIMIT 0,1);
+-------+
| id    |
+-------+
| 10001 |
+-------+
1 row in set (0.19 sec)

mysql> SELECT c.id
    -> FROM test p, test c
    -> WHERE p.id=2 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORD
ER BY c2.id DESC LIMIT 0,1);
Empty set (0.13 sec)

mysql> SELECT c.id
    -> FROM test p, test c
    -> WHERE p.id=3 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORD
ER BY c2.id LIMIT 0,1);
Empty set (0.30 sec)

mysql> SELECT c.id
    -> FROM test p, test c
    -> WHERE p.id=3 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORD
ER BY c2.id DESC LIMIT 0,1);
Empty set (0.31 sec)

mysql> alter table test drop key `pIdx`;
Query OK, 80000 rows affected (0.33 sec)
Records: 80000  Duplicates: 0  Warnings: 0

mysql> SELECT c.id
    -> FROM test p, test c
    -> WHERE p.id=3 AND c.id=(SELECT c2.id FROM test c2 WHERE c2.parent=p.id ORD
ER BY c2.id DESC LIMIT 0,1);
+-------+
| id    |
+-------+
| 80000 |
+-------+
1 row in set (0.00 sec)

So, exactly the same bug as described initially is easily repeatable on 5.0.52 also.

I've tried both 5.0-BK and 5.1-BK on Windows and Linux FC8. The both don't exhibit the described problem.
Can you please retry with the latest BK versions ? And if they still exhibit the problem for you please reopen the bug.
The versions reported are "5.0.56-debug-log" and "5.1.23-rc-debug-log".