MySQL Bugs: #50389: Using intersect does not return all rows

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

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

sample data for LOAD DATA INFILE

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

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.

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.

Bug #50402 was marked as a duplicate of this one.

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.

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.

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.

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)

Noted in 5.1.49 changelog.

Index Merge between three indexes could return incorrect results.

Setting report to Need Merge pending further pushes.

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)

Pushed into mysql-next-mr (revid:alik@sun.com-20100723121929-90e9zemk3jkr2ocy) (version source revid:vasil.dimov@oracle.com-20100531152341-x2d4hma644icamh1) (pib:18)

Noted in 5.5.6 changelog.

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)

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)

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)

Already documented in the 5.1.49 changelog; no additional changelog entries required. Set back to Closed state.