Bug #50389 Using intersect does not return all rows
Submitted: 16 Jan 2010 4:14 Modified: 14 Oct 2010 14:05
Reporter: Devananda van der Veen Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.0.90, 5.1.34, 5.1.42, 5.1.43-bzr OS:Linux
Assigned to: Sergei Glukhov CPU Architecture:Any
Tags: index merge, innodb, intersect

[16 Jan 2010 4:14] Devananda van der Veen
Description:
InnoDB is returning an incorrect (incomplete) result set when it chooses to use Index Merge (intersect) between three indexes. I have verified this on 5.1.34 and 5.1.42 community editions, both x86_64 and i686.

The correct number of rows are returned in the following cases:

* storage engine is MyISAM
* query includes USE INDEX (PRIMARY)
* query is SELECT COUNT(*) instead of SELECT *
* length of data in column 'c1' is short

I have attached sample file, table create statement, as well as example of different queries which illustrate the problem. With this particular data set and query, the result *should* contain 10 rows. In some of the queries, it contains only 8. Each of these "bad" queries has the following in it's EXPLAIN output

"Using intersect(i2_2,i2,PRIMARY); Using where"

How to repeat:
CREATE TABLE `p` (
  `i1` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `i2` int(10) unsigned DEFAULT NULL,
  `i3` int(10) unsigned DEFAULT NULL,
  `t1` tinyint(4) DEFAULT '0',
  `c1` varchar(50) DEFAULT NULL,
  PRIMARY KEY (`i1`),
  KEY `i2` (`i2`,`c1`,`t1`),
  KEY `i2_2` (`i2`,`t1`)
) ENGINE=InnoDB AUTO_INCREMENT=4617752 DEFAULT CHARSET=latin1;

LOAD DATA INFILE 'intersect-bug.tsv' INTO TABLE p;

mysql [localhost] {msandbox} (test) > explain SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
| id | select_type | table | type        | possible_keys   | key             | key_len | ref  | rows | Extra                                         |
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
|  1 | SIMPLE      | p     | index_merge | PRIMARY,i2,i2_2 | i2_2,i2,PRIMARY | 7,60,4  | NULL |    1 | Using intersect(i2_2,i2,PRIMARY); Using where |
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
1 row in set (0.00 sec)

mysql [localhost] {msandbox} (test) > explain SELECT * FROM p FORCE INDEX (PRIMARY) WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | p     | range | PRIMARY       | PRIMARY | 4       | NULL |   18 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql [localhost] {msandbox} (test) > \P >/dev/null
PAGER set to '>/dev/null'
mysql [localhost] {msandbox} (test) > SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;
8 rows in set (0.00 sec)

mysql [localhost] {msandbox} (test) > SELECT * FROM p FORCE INDEX (PRIMARY) WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;
10 rows in set (0.00 sec)

--------------------
Decrease the length of 'c1' column sometimes yields good results
--------------------

mysql [localhost] {msandbox} (test) > update p set c1='bar'; update p set c1='foo' where floor(rand()*10) < 5;Query OK, 441 rows affected (0.09 sec)
Rows matched: 441  Changed: 441  Warnings: 0

Query OK, 202 rows affected (0.05 sec)
Rows matched: 202  Changed: 202  Warnings: 0

mysql [localhost] {msandbox} (test) > explain SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'foo' AND i2 = 1221457 AND t1 = 0 ;
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+-------------+
| id | select_type | table | type | possible_keys   | key  | key_len | ref               | rows | Extra       |
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+-------------+
|  1 | SIMPLE      | p     | ref  | PRIMARY,i2,i2_2 | i2   | 60      | const,const,const |   16 | Using where |
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+-------------+
1 row in set (0.00 sec)

---------------------
Increasing the length of 'c1' again and the problem returns!
---------------------

mysql [localhost] {msandbox} (test) > update p set c1='abcdefghijklmnopwrst'; update p set c1='asdfghjklzxcvbnm' where floor(rand()*10) < 5;
Query OK, 441 rows affected (0.09 sec)
Rows matched: 441  Changed: 441  Warnings: 0

Query OK, 205 rows affected (0.06 sec)
Rows matched: 205  Changed: 205  Warnings: 0

mysql [localhost] {msandbox} (test) > explain SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
| id | select_type | table | type        | possible_keys   | key             | key_len | ref  | rows | Extra                                         |
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
|  1 | SIMPLE      | p     | index_merge | PRIMARY,i2,i2_2 | i2_2,i2,PRIMARY | 7,60,4  | NULL |    1 | Using intersect(i2_2,i2,PRIMARY); Using where |
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
1 row in set (0.00 sec)

Suggested fix:
Intersect should always yield the same results as any other execution plan
[16 Jan 2010 4:15] Devananda van der Veen
sample data for LOAD DATA INFILE

Attachment: intersect-bug.tsv (text/tab-separated-values), 17.22 KiB.

[16 Jan 2010 15:02] Valeriy Kravchuk
Verified just as described with recent 5.1.43 from bzr:

77-52-1-11:5.1 openxs$ 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 2
Server version: 5.1.43-debug Source distribution

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> CREATE TABLE `p` (
    ->   `i1` int(10) unsigned NOT NULL AUTO_INCREMENT,
    ->   `i2` int(10) unsigned DEFAULT NULL,
    ->   `i3` int(10) unsigned DEFAULT NULL,
    ->   `t1` tinyint(4) DEFAULT '0',
    ->   `c1` varchar(50) DEFAULT NULL,
    ->   PRIMARY KEY (`i1`),
    ->   KEY `i2` (`i2`,`c1`,`t1`),
    ->   KEY `i2_2` (`i2`,`t1`)
    -> ) ENGINE=InnoDB AUTO_INCREMENT=4617752 DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.05 sec)

mysql> LOAD DATA INFILE 'intersect-bug.tsv' INTO TABLE p;
ERROR 29 (HY000): File '/Users/openxs/dbs/5.1/var/test/intersect-bug.tsv' not found (Errcode: 2)
mysql> LOAD DATA INFILE '~/Downloads/intersect-bug.tsv' INTO TABLE p;
Query OK, 441 rows affected (0.43 sec)
Records: 441  Deleted: 0  Skipped: 0  Warnings: 0

mysql> explain SELECT * FROM p WHERE i1 IN
    -> (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153)
    -> AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
| id | select_type | table | type        | possible_keys   | key             | key_len | ref  | rows | Extra                                         |
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
|  1 | SIMPLE      | p     | index_merge | PRIMARY,i2,i2_2 | i2_2,i2,PRIMARY | 7,60,4  | NULL |    1 | Using intersect(i2_2,i2,PRIMARY); Using where |
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
1 row in set (0.01 sec)

mysql> \P >/dev/null
PAGER set to '>/dev/null'
mysql> SELECT * FROM p WHERE i1 IN
    -> (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153)
    -> AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;
8 rows in set (0.01 sec)

mysql> SELECT * FROM p FORCE INDEX(PRIMARY)WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0;
10 rows in set (0.00 sec)

mysql> alter table p engine=MyISAM;
Query OK, 441 rows affected (0.08 sec)
Records: 441  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0;
10 rows in set (0.00 sec)

mysql> explain SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0;
1 row in set (0.01 sec)

mysql> \P
Default pager wasn't set, using stdout.
mysql> explain SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0;
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+-------------+
| id | select_type | table | type | possible_keys   | key  | key_len | ref               | rows | Extra       |
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+-------------+
|  1 | SIMPLE      | p     | ref  | PRIMARY,i2,i2_2 | i2   | 60      | const,const,const |   32 | Using where |
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+-------------+
1 row in set (0.00 sec)

So, in case of MyISAM table index merge is NOT used by optimizer, hence correct results. This is an optimizer bug.
[16 Jan 2010 15:06] Valeriy Kravchuk
5.0.x is also affected:

77-52-1-11:5.0 openxs$ 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.0.90-debug Source distribution

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> CREATE TABLE `p` (   `i1` int(10) unsigned NOT NULL AUTO_INCREMENT,   `i2` int(10) unsigned DEFAULT NULL,   `i3` int(10) unsigned DEFAULT NULL,   `t1` tinyint(4) DEFAULT '0',   `c1` varchar(50) DEFAULT NULL,   PRIMARY KEY (`i1`),   KEY `i2` (`i2`,`c1`,`t1`),   KEY `i2_2` (`i2`,`t1`) ) ENGINE=InnoDB AUTO_INCREMENT=4617752 DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.01 sec)

mysql> LOAD DATA INFILE '~/Downloads/intersect-bug.tsv' INTO TABLE p;Query OK, 441 rows affected (0.10 sec)Records: 441  Deleted: 0  Skipped: 0  Warnings: 0mysql>  explain SELECT * FROM p WHERE i1 IN    -> (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153)    -> AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0 ;+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
| id | select_type | table | type        | possible_keys   | key             | key_len | ref  | rows | Extra                                         |
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
|  1 | SIMPLE      | p     | index_merge | PRIMARY,i2,i2_2 | i2_2,i2,PRIMARY | 7,60,4  | NULL |    1 | Using intersect(i2_2,i2,PRIMARY); Using where | 
+----+-------------+-------+-------------+-----------------+-----------------+---------+------+------+-----------------------------------------------+
1 row in set (0.01 sec)

mysql> SELECT * FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0;
+---------+---------+---------+------+----------------------+
| i1      | i2      | i3      | t1   | c1                   |
+---------+---------+---------+------+----------------------+
| 3305175 | 1221457 |       0 |    0 | abcdefghijklmnopwrst | 
| 3329875 | 1221457 | 1382427 |    0 | abcdefghijklmnopwrst | 
| 3336022 | 1221457 |       0 |    0 | abcdefghijklmnopwrst | 
| 3346860 | 1221457 |       0 |    0 | abcdefghijklmnopwrst | 
| 3772880 | 1221457 |       0 |    0 | abcdefghijklmnopwrst | 
| 3784744 | 1221457 | 1382427 |    0 | abcdefghijklmnopwrst | 
| 3796193 | 1221457 |       0 |    0 | abcdefghijklmnopwrst | 
| 4559596 | 1221457 |       0 |    0 | abcdefghijklmnopwrst | 
+---------+---------+---------+------+----------------------+
8 rows in set (0.00 sec)

mysql> SELECT count(*) FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0;
+----------+
| count(*) |
+----------+
|       10 | 
+----------+
1 row in set (0.01 sec)

mysql> explain SELECT count(*) FROM p WHERE i1 IN (3305028,3353871,3772880,3346860,4228206,3336022,3470988,3305175,3329875,3817277,3856380,3796193,3784744,4180925,4559596,3963734,3856391,4494153) AND c1 = 'abcdefghijklmnopwrst' AND i2 = 1221457 AND t1 = 0;
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+--------------------------+
| id | select_type | table | type | possible_keys   | key  | key_len | ref               | rows | Extra                    |
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+--------------------------+
|  1 | SIMPLE      | p     | ref  | PRIMARY,i2,i2_2 | i2   | 60      | const,const,const |   17 | Using where; Using index | 
+----+-------------+-------+------+-----------------+------+---------+-------------------+------+--------------------------+
1 row in set (0.00 sec)

Again, results are correct if index merge is NOT used, for whatever reason.
[18 Jan 2010 9:14] Valeriy Kravchuk
Bug #50402 was marked as a duplicate of this one.
[9 Jun 2010 14:44] Bugs System
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/110641

3421 Sergey Glukhov	2010-06-09
      Bug#50389 Using intersect does not return all rows
      In process of record search it is not taken into account
      that inital quick->file->ref value could be inapplicable
      to range interval. After proper row is found this value is
      stored into the record buffer and later the record is
      filtered out at condition evaluation stage.
      The fix is store a refernce of found row to the handler ref field.
     @ mysql-test/r/innodb_mysql.result
        test case
     @ mysql-test/std_data/intersect-bug.tsv
        test case
     @ mysql-test/t/innodb_mysql.test
        test case
     @ sql/opt_range.cc
        store a refernce of found row to the handler ref field.
[21 Jun 2010 9:27] Bugs System
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/111661

3438 Sergey Glukhov	2010-06-21
      Bug#50389 Using intersect does not return all rows
      In process of record search it is not taken into account
      that inital quick->file->ref value could be inapplicable
      to range interval. After proper row is found this value is
      stored into the record buffer and later the record is
      filtered out at condition evaluation stage.
      The fix is store a refernce of found row to the handler ref field.
     @ mysql-test/r/innodb_mysql.result
        test case
     @ mysql-test/std_data/intersect-bug50389.tsv
        test case
     @ mysql-test/t/innodb_mysql.test
        test case
     @ sql/opt_range.cc
        store a refernce of found row to the handler ref field.
[21 Jun 2010 11:07] Bugs System
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/111682

3437 Sergey Glukhov	2010-06-21
      Bug#50389 Using intersect does not return all rows
      In process of record search it is not taken into account
      that inital quick->file->ref value could be inapplicable
      to range interval. After proper row is found this value is
      stored into the record buffer and later the record is
      filtered out at condition evaluation stage.
      The fix is store a refernce of found row to the handler ref field.
     @ mysql-test/r/innodb_mysql.result
        test case
     @ mysql-test/std_data/intersect-bug50389.tsv
        test case
     @ mysql-test/t/innodb_mysql.test
        test case
     @ sql/opt_range.cc
        store a refernce of found row to the handler ref field.
[19 Jul 2010 14:35] Bugs System
Pushed into 5.1.49 (revid:build@mysql.com-20100719143034-omcma40sblwmay3x) (version source revid:sergey.glukhov@sun.com-20100621110958-t01pluyskwsc0w70) (merge vers: 5.1.48) (pib:16)
[20 Jul 2010 2:48] Paul DuBois
Noted in 5.1.49 changelog.

Index Merge between three indexes could return incorrect results.

Setting report to Need Merge pending further pushes.
[23 Jul 2010 12:28] Bugs System
Pushed into mysql-trunk 5.5.6-m3 (revid:alik@sun.com-20100723121820-jryu2fuw3pc53q9w) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:18)
[23 Jul 2010 12:35] Bugs System
Pushed into mysql-next-mr (revid:alik@sun.com-20100723121929-90e9zemk3jkr2ocy) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (pib:18)
[23 Jul 2010 17:14] Paul DuBois
Noted in 5.5.6 changelog.
[14 Oct 2010 8:37] Bugs System
Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.20 (revid:martin.skold@mysql.com-20101014082627-jrmy9xbfbtrebw3c) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 8:52] Bugs System
Pushed into mysql-5.1-telco-6.3 5.1.51-ndb-6.3.39 (revid:martin.skold@mysql.com-20101014083757-5qo48b86d69zjvzj) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 9:08] Bugs System
Pushed into mysql-5.1-telco-6.2 5.1.51-ndb-6.2.19 (revid:martin.skold@mysql.com-20101014084420-y54ecj85j5we27oa) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (merge vers: 5.5.5-m3) (pib:21)
[14 Oct 2010 14:05] Jon Stephens
Already documented in the 5.1.49 changelog; no additional changelog entries required. Set back to Closed state.