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

[25 Jul 2006 18:57] [ name withheld ]
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
[25 Jul 2006 18:57] [ name withheld ]
Demostrating creatint table and selecting incorrectly

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

[25 Jul 2006 19:29] MySQL Verification Team
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>
[25 Jul 2006 19:34] Jeff Kilpatrick
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.
[25 Jul 2006 20:41] MySQL Verification Team
Thank you for the feedback and additional comments regarding this bug.
[15 Aug 2006 12:56] Sergey Petrunya
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.
[16 Aug 2006 14:09] Sergey Petrunya
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
[29 Aug 2006 13:24] Evgeny Potemkin
Fixed in 5.0.25
[31 Aug 2006 16:01] Chad MILLER
Available in 5.0.25.
[4 Sep 2006 11:34] Evgeny Potemkin
Fixed in 5.1.12
[13 Sep 2006 2:36] Paul DuBois
Noted in 5.0.25, 5.1.12 changelogs.
[1 Oct 2006 14:34] Eric Dexter
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.
[3 Oct 2006 12:52] Martin Andersen
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.