MySQL Bugs: #21282: NOT IN, more than 1000 returns incorrect reults with INDEX

Bug #21282	NOT IN, more than 1000 returns incorrect reults with INDEX
Submitted:	25 Jul 2006 18:57	Modified:	13 Sep 2006 2:36
Reporter:	[ name withheld ]	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S1 (Critical)
Version:	5.0.22/5.0BK/5.1BK	OS:	FreeBSD (FreeBSD 6.1/Linux)
Assigned to:	Sergey Petrunya	CPU Architecture:	Any
Tags:	INDEX, NOT IN

Description:
Using a SELECT ... WHERE some_field NOT IN (...) and then 1000 or more values in the NOT IN part causes the server to return incorrect results if there is an INDEX/UNIQUE key on some_field. Less than 1000 criteria works correctly. This is similar to, but not the same as (perhaps it has something to do with the fix from) #15872

How to repeat:
See attached query file

Demostrating creatint table and selecting incorrectly

Attachment: borked_test.sql (application/octet-stream, text), 106.14 KiB.

Thank you for the bug report.

Query OK, 1 row affected (0.00 sec)

+-------------+
| total count |
+-------------+
|        2101 | 
+-------------+
1 row in set (0.01 sec)

+------------+
| 1002 count |
+------------+
|       1099 | 
+------------+
1 row in set (0.03 sec)

+-----------+
| 502 count |
+-----------+
|      1599 | 
+-----------+
1 row in set (0.01 sec)

Query OK, 2101 rows affected (0.07 sec)
Records: 2101  Duplicates: 0  Warnings: 0

+------------------------+
| total with index count |
+------------------------+
|                   2101 | 
+------------------------+
1 row in set (0.00 sec)

+-----------------------+
| 1002 with index count |
+-----------------------+
|                     0 | 
+-----------------------+
1 row in set (0.03 sec)

+----------------------+
| 502 with index count |
+----------------------+
|                 1599 | 
+----------------------+
1 row in set (0.07 sec)

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

mysql> 
------------------------------------------------------------------
Query OK, 1 row affected (0.00 sec)

+-------------+
| total count |
+-------------+
|        2101 | 
+-------------+
1 row in set (0.01 sec)

+------------+
| 1002 count |
+------------+
|       1099 | 
+------------+
1 row in set (0.02 sec)

+-----------+
| 502 count |
+-----------+
|      1599 | 
+-----------+
1 row in set (0.01 sec)

Query OK, 2101 rows affected (0.10 sec)
Records: 2101  Duplicates: 0  Warnings: 0

+------------------------+
| total with index count |
+------------------------+
|                   2101 | 
+------------------------+
1 row in set (0.01 sec)

+-----------------------+
| 1002 with index count |
+-----------------------+
|                     0 | 
+-----------------------+
1 row in set (0.02 sec)

+----------------------+
| 502 with index count |
+----------------------+
|                 1599 | 
+----------------------+
1 row in set (0.11 sec)

mysql> select version();
+-------------------+
| version()         |
+-------------------+
| 5.1.12-beta-debug | 
+-------------------+
1 row in set (0.01 sec)

mysql> 
----------------------------------------------------------------------
Query OK, 1 row affected (0.00 sec)

+-------------+
| total count |
+-------------+
|        2101 |
+-------------+
1 row in set (0.02 sec)

+------------+
| 1002 count |
+------------+
|       1099 |
+------------+
1 row in set (0.00 sec)

+-----------+
| 502 count |
+-----------+
|      1599 |
+-----------+
1 row in set (0.01 sec)

Query OK, 2101 rows affected (0.05 sec)
Records: 2101  Duplicates: 0  Warnings: 0

+------------------------+
| total with index count |
+------------------------+
|                   2101 |
+------------------------+
1 row in set (0.01 sec)

+-----------------------+
| 1002 with index count |
+-----------------------+
|                  1099 |
+-----------------------+
1 row in set (0.01 sec)

+----------------------+
| 502 with index count |
+----------------------+
|                 1599 |
+----------------------+
1 row in set (0.01 sec)

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

mysql>

Some notes on this bug:
1) It only occurs when there's an index on the field being tested.
2) It only occurs when the list of elements in NOT IN is longer than 999 elements and contains non-sequential or randomly ordered elements.
3) The issue appeared in 5.0.21.  Perhaps it's related to the fix of bug #15872.

I tossed together a perl script demonstrating this.  You can download it at http://lupus.omrf.org/~kilpatjr/not_in_wrong_results.perl

I've also seen the behavior on Mac OS 10.4.

Thank you for the feedback and additional comments regarding this bug.

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

ChangeSet@1.2274, 2006-08-15 16:54:02+04:00, sergefp@mysql.com +1 -0
  BUG#21282: Incorrect query results for "t.key NOT IN (<big const list>) 
  * In fix for BUG#15872, a condition of type "t.key NOT IN (c1, .... cN)"
    where N>1000, was incorrectly converted to
      (-inf < X < c_min) OR (c_max < X)
    which was not correct. Now this conversion is removed, we dont produce
    any range lists for such conditions.

Notes for the changelog:

The bug was that MySQL could return wrong query results if the WHERE clause contained  "t.keypart NOT IN (<list of more than 1000 constants>).
The bug was introduced in fix for BUG#15872

Fixed in 5.0.25

Available in 5.0.25.

Fixed in 5.1.12

Noted in 5.0.25, 5.1.12 changelogs.

I'm experiencing this bug in Fedora Core 5. I see that fixes were made to the 5.0.25 version, but that version has only been released to "commercial customers". When can I expect this "S1 (Critical)" fix to find it's way into the community version? Fedora is already aware of the problem, and will cut a new RPM as soon as you release a new version for the community (as will other distros I bet).

I've been hunting for a release schedule but unable to find one. I really need this bugfix.

For people having older versions of mysql with this bug, a workaround exists:
SELECT x FROM table WHERE x NOT IN (SELECT x FROM table WHERE x IN (....))

Maybe more efficient queries exist to work around this issue, but this helped me.