MySQL Bugs: #35931: List partition MyISAM table returns erroneous results

Bug #35931	List partition MyISAM table returns erroneous results
Submitted:	9 Apr 12:44	Modified:	23 Jul 14:48
Reporter:	George Vitek
Status:	Closed
Category:	Server: Partition	Severity:	S2 (Serious)
Version:	5.1.23, 5.1.25	OS:	Linux
Assigned to:	Mattias Jonsson	Target Version:	5.1.27
Triage:	D2 (Serious) / R2 (Low) / E2 (Low)

Description:
A List partitioned MyISAM table returns erroneous results when an index is present on a
column and NOT IN is used on that column in the WHERE clause. 

If the index is dropped, correct results are returned.

On larger tables, it is also clear that searches using the index are approximately an
order of magnitude slower then if the index is not present.

This appears to be a regression because it doesn't occur on 5.1.22.

Example:

On a greatly reduced version of the original problem table,
 
SELECT count(*) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 )

returns 168. The correct result is 24. If we then do a

ALTER TABLE t DROP INDEX b

and repeat the query, we get 24. If we then do a

ALTER TABLE t ADD INDEX ( b )

we get 168 again. If we try what is the logical equivalent given the data in the table,

SELECT count(*) FROM t WHERE b IN ( 14,15,16,17,19 );

we get 24.

How to repeat:
CREATE TABLE t (
  a int NOT NULL,   
  b mediumint NOT NULL,   
  c int NOT NULL,
  KEY b (b)
) ENGINE=MyISAM 
PARTITION BY LIST (a) (
	PARTITION p0 VALUES IN (1) 
);

INSERT INTO t VALUES (1,1,0), (1,1,1), (1,1,2), (1,1,53), (1,1,4), (1,1,5), (1,1,6),
(1,1,7), (1,1,8), (1,1,9), (1,1,10), (1,1,11), (1,1,12), (1,1,13), (1,1,14), (1,1,15),
(1,1,16), (1,1,67), (1,1,18), (1,1,19), (1,1,20), (1,1,21), (1,1,22), (1,1,23), (1,1,24),
(1,1,75), (1,1,26), (1,1,27), (1,1,128), (1,1,79), (1,1,30), (1,1,31), (1,1,32), (1,1,33),
(1,1,34), (1,1,85), (1,1,36), (1,1,37), (1,1,38), (1,1,39), (1,1,40), (1,1,241), (1,1,42),
(1,1,43), (1,1,44), (1,1,45), (1,1,46), (1,1,147), (1,1,48), (1,1,49), (1,2,0), (1,2,1),
(1,2,2), (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,2,7), (1,2,8), (1,2,9), (1,2,10),
(1,2,11), (1,2,12), (1,2,13), (1,2,14), (1,2,15), (1,2,16), (1,2,17), (1,2,18), (1,2,19),
(1,2,20), (1,2,21), (1,2,22), (1,2,23), (1,2,24), (1,2,25), (1,2,26), (1,2,27), (1,2,28),
(1,2,29), (1,2,30), (1,2,31), (1,2,32), (1,2,33), (1,2,34), (1,2,35), (1,2,36), (1,2,37),
(1,2,38), (1,2,39), (1,2,40), (1,2,41), (1,2,42), (1,2,43), (1,2,44), (1,2,45), (1,2,46),
(1,2,47), (1,2,48), (1,2,49), (1,6,0), (1,6,1), (1,6,2), (1,6,3), (1,6,4), (1,6,5),
(1,6,6), (1,6,7), (1,6,8), (1,6,9), (1,6,10), (1,6,11), (1,6,12), (1,6,13), (1,6,14),
(1,6,15), (1,6,16), (1,6,17), (1,6,18), (1,6,19), (1,6,20), (1,6,21), (1,6,22), (1,6,23),
(1,6,24), (1,6,25), (1,6,26), (1,6,27), (1,6,28), (1,6,29), (1,6,30), (1,6,31), (1,6,32),
(1,6,33), (1,6,34), (1,6,35), (1,6,36), (1,6,37), (1,6,38), (1,6,39), (1,6,40), (1,6,41),
(1,6,42), (1,6,43), (1,6,44), (1,6,45), (1,6,46), (1,6,47), (1,6,48), (1,6,49), (1,7,0),
(1,7,1), (1,7,2), (1,7,3), (1,7,4), (1,7,5), (1,7,6), (1,7,7), (1,7,8), (1,7,9), (1,7,10),
(1,7,11), (1,7,12), (1,7,13), (1,7,14), (1,7,15), (1,7,16), (1,7,17), (1,7,18), (1,7,19),
(1,7,20), (1,7,21), (1,7,22), (1,7,23), (1,7,24), (1,7,25), (1,7,26), (1,7,27), (1,7,28),
(1,7,29), (1,7,30), (1,7,31), (1,7,32), (1,7,33), (1,7,34), (1,7,35), (1,7,38), (1,7,39),
(1,7,90), (1,7,41), (1,7,43), (1,7,48), (1,7,49), (1,9,0), (1,9,1), (1,9,2), (1,9,3),
(1,9,4), (1,9,5), (1,9,6), (1,9,7), (1,9,8), (1,9,9), (1,9,10), (1,9,11), (1,9,12),
(1,9,13), (1,9,14), (1,9,15), (1,9,16), (1,9,17), (1,9,18), (1,9,19), (1,9,20), (1,9,21),
(1,9,22), (1,9,23), (1,9,24), (1,9,25), (1,9,26), (1,9,29), (1,9,32), (1,9,35), (1,9,38),
(1,10,0), (1,10,1), (1,10,2), (1,10,3), (1,10,4), (1,10,5), (1,10,6), (1,10,7), (1,10,8),
(1,10,9), (1,10,10), (1,10,11), (1,10,13), (1,10,14), (1,10,15), (1,10,16), (1,10,17),
(1,10,18), (1,10,22), (1,10,24), (1,10,25), (1,10,26), (1,10,28), (1,10,131), (1,10,33),
(1,10,84), (1,10,35), (1,10,40), (1,10,42), (1,10,49), (1,11,0), (1,11,1), (1,11,2),
(1,11,3), (1,11,4), (1,11,5), (1,11,6), (1,11,7), (1,11,8), (1,11,9), (1,11,10),
(1,11,11), (1,11,12), (1,11,13), (1,11,14), (1,11,15), (1,11,16), (1,11,17), (1,11,18),
(1,11,19), (1,11,20), (1,11,21), (1,11,22), (1,11,23), (1,11,24), (1,11,25), (1,11,26),
(1,11,27), (1,11,28), (1,11,30), (1,11,31), (1,11,32), (1,11,33), (1,11,34), (1,11,35),
(1,11,37), (1,11,39), (1,11,40), (1,11,42), (1,11,44), (1,11,45), (1,11,47), (1,11,48),
(1,14,104), (1,14,58), (1,14,12), (1,14,13), (1,14,15), (1,14,16), (1,14,17), (1,14,34),
(1,15,0), (1,15,1), (1,15,2), (1,15,3), (1,15,4), (1,15,5), (1,15,7), (1,15,9), (1,15,15),
(1,15,27), (1,15,49), (1,16,0), (1,16,1), (1,16,3), (1,17,4), (1,19,1);

SELECT count(*) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+----------+
| count(*) |
+----------+
|      168 | 
+----------+

SELECT sum(c) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+--------+
| sum(c) |
+--------+
|   2800 |
+--------+

ALTER TABLE t DROP INDEX b;

SELECT count(*) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+----------+
| count(*) |
+----------+
|       24 | 
+----------+

SELECT sum(c) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+--------+
| sum(c) |
+--------+
|   400  |
+--------+

Thank you for a bug report. Verified just as described on latest 5.1.25:

openxs@suse:~/dbs/5.1> bin/mysql -uroot test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.1.25-rc Source distribution

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

mysql> drop table t;
ERROR 1051 (42S02): Unknown table 't'
mysql> CREATE TABLE t (
    ->   a int NOT NULL,
    ->   b mediumint NOT NULL,
    ->   c int NOT NULL,
    ->   KEY b (b)
    -> ) ENGINE=MyISAM
    -> PARTITION BY LIST (a) (
    -> PARTITION p0 VALUES IN (1)
    -> );
Query OK, 0 rows affected (0.07 sec)

mysql> INSERT INTO t VALUES (1,1,0), (1,1,1), (1,1,2), (1,1,53), (1,1,4), (1,1,5),
(1,1,6),

...

    -> (1,15,27), (1,15,49), (1,16,0), (1,16,1), (1,16,3), (1,17,4), (1,19,1);
Query OK, 321 rows affected (0.01 sec)
Records: 321  Duplicates: 0  Warnings: 0

mysql> SELECT count(*) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+----------+
| count(*) |
+----------+
|      168 |
+----------+
1 row in set (0.01 sec)

mysql> SELECT sum(c) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+--------+
| sum(c) |
+--------+
|   2800 |
+--------+
1 row in set (0.01 sec)

mysql> ALTER TABLE t DROP INDEX b;
Query OK, 321 rows affected (0.00 sec)
Records: 321  Duplicates: 0  Warnings: 0

mysql> SELECT count(*) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+----------+
| count(*) |
+----------+
|       24 |
+----------+
1 row in set (0.00 sec)

mysql> SELECT sum(c) FROM t WHERE b NOT IN ( 1,2,6,7,9,10,11 );
+--------+
| sum(c) |
+--------+
|    400 |
+--------+
1 row in set (0.00 sec)

Hmm, does not seem to exist in 6.0

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

ChangeSet@1.2576, 2008-04-12 10:22:07+02:00, mattiasj@witty. +3 -0
  Bug#35931: List partition MyISAM table returns erroneous results
  
  Used the wrong function when fixing bug 30480 which lead to
  no stop on end_key resulting in duplicate results from index scan

Marked Bug#37327 and Bug#37329 as duplicate of this.

The problem is that there is no stop when reading the index, which results in it scans the
index from the specified start to the very end. This results in both a big performance
hit, as well of duplicate rows.

Code wise was the bug introduced by me by using the wrong flag function (table_flags
instead of index_flags) which never returned the correct flag and never breaking the scan
loop. This error was done in Bug#30480, which is now corrected with this patch.

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

2656 Mattias Jonsson	2008-06-16
      Bug#35931: Index search of partitioned MyISAM table
      returns erroneous results
      Used the wrong function when fixing bug 30480 which lead to
      no stop on end_key resulting in duplicate results from index scan
      
      (Includes test cases for the duplicate bugs 37327 and 37329,
      Duplicate rows and bad performance/High Handler_read_next values)

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

2664 Mattias Jonsson	2008-06-17
      Bug#35931 Index search of partitioned MyISAM table
      returns erroneous results
      
      Used the wrong function when fixing bug nr 30480 which lead to
      no stop on end_key resulting in duplicate results from index scan
      
      Includes test cases for the duplicate 37327 and 37329,
      Duplicate rows and bad performance/High Handler_read_next values
      
      Recommit from bugteam tree.

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

2665 Mattias Jonsson	2008-06-17
      Bug#35931 Index search of partitioned MyISAM table
      returns erroneous results
      
      Used the wrong function when fixing 30480 which lead to
      no stop on end_key resulting in duplicate results from index scan
      
      Includes test cases for the duplicates 37327 and 37329,
      Duplicate rows and bad performance/High Handler_read_next values
      
      Recommit after merge issues

Sorry for all the commits, had some trouble when merging...

Pushed into mysql-5.1-bugteam and mysql-6.0-bugteam

Marked Bug#37219 as a duplicate of this bug.

Marked bug#37235 a duplicate of this.

Pushed into 5.1.28 and 6.0.7-alpha

Documented bugfix in the 5.1.28 and 6.0.7 changelogs as follows:

        A LIST partitioned MyISAM table returned erroneous results when an index 
        was present on a column in the WHERE clause and NOT IN was used on that 
        column. 

        Searches using the index were also much slower then if the index were not 
        present.

Pushed into 5.1.27  (revid:joerg@mysql.com-20080626161101-h5hsaluwtf05xdr2) (version
source revid:joerg@mysql.com-20080626161101-h5hsaluwtf05xdr2) (pib:3)