MySQL Bugs: #48093: 6.0 Server not processing equivalent IN clauses properly with Innodb tables

Bug #48093	6.0 Server not processing equivalent IN clauses properly with Innodb tables
Submitted:	15 Oct 20:36	Modified:	24 Nov 10:22
Reporter:	Patrick Crews
Status:	In progress
Category:	Server: Optimizer	Severity:	S3 (Non-critical)
Version:	6.0	OS:	Any
Assigned to:	Jorgen Loland	Target Version:
Tags:	IN, innodb, regression, mrr
Triage:	Triaged: D2 (Serious)

Description:
The 6.0 server is not processing equivalent IN clauses properly when using Innodb
tables.
This bug is not present in 5.1, nor is it affected by engine_condition_pushdown or
join_cache_level settings.
This bug is not present when using MEMORY or MyISAM tables.

Query2 is the equivalent of Query1 below (it explicitly lists the varchar_nokey values
from table C rather than using a subquery).  However, Query2 misses one row from the
proper result set:
diff:
   2001-04-14
 -2006-08-28

Query1:
SELECT `date_key`  
FROM C  
WHERE `varchar_key`  IN (  
SELECT `varchar_nokey`  
FROM C  )  AND `int_key`  =  8   ;

Query2:
SELECT `date_key`  
FROM C  
WHERE `varchar_key`  IN  ( 'w', 'm', 'm', 'k', 'r', 't', 'j', 'u', 'h', 'o', NULL, 'k',
'e', 'n', 't', 'c', 'm', 'y', 'f', 'd' )   AND `int_key`  =  8 

How to repeat:
MTR test case.
Currently set up for use with 6.0, comment out the SET SESSION statements except for
engine_condition_pushdown for use with 5.0
Make sure to use --mysqld=--loose-innodb to have Innodb tables accessible:
#/* Server0: MySQL 6.0.14-alpha-debug-log */

/*!50400 SET SESSION optimizer_switch =
'firstmatch=off,index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,loosescan=off,materialization=off,semijoin=off'
*/;
/*!50400 SET SESSION optimizer_use_mrr = 'disable' */;
/*!50400 SET SESSION engine_condition_pushdown = 1 */;
/*!50400 SET SESSION join_cache_level = 1 */;
/*!50400 SET SESSION debug = '+d,optimizer_no_icp' */;

#/* Begin test case for query 0 */

--disable_warnings
DROP TABLE /*! IF EXISTS */ C;
--enable_warnings

CREATE TABLE `C` (
  `int_key` int(11) DEFAULT NULL,
  `date_key` date DEFAULT NULL,
  `varchar_key` varchar(1) DEFAULT NULL,
  `varchar_nokey` varchar(1) DEFAULT NULL,
  KEY `int_key` (`int_key`),
  KEY `date_key` (`date_key`),
  KEY `varchar_key` (`varchar_key`,`int_key`)
) ENGINE=Innodb DEFAULT CHARSET=latin1;
INSERT INTO `C` VALUES (2,NULL,'w','w');
INSERT INTO `C` VALUES (9,'2001-09-19','m','m');
INSERT INTO `C` VALUES (3,'2004-09-12','m','m');
INSERT INTO `C` VALUES (9,NULL,'k','k');
INSERT INTO `C` VALUES (NULL,'2002-07-19','r','r');
INSERT INTO `C` VALUES (9,'2002-12-16','t','t');
INSERT INTO `C` VALUES (3,'2006-02-08','j','j');
INSERT INTO `C` VALUES (8,'2006-08-28','u','u');
INSERT INTO `C` VALUES (8,'2001-04-14','h','h');
INSERT INTO `C` VALUES (53,'2000-01-05','o','o');
INSERT INTO `C` VALUES (0,'2003-12-06',NULL,NULL);
INSERT INTO `C` VALUES (5,'1900-01-01','k','k');
INSERT INTO `C` VALUES (166,'2002-11-27','e','e');
INSERT INTO `C` VALUES (3,NULL,'n','n');
INSERT INTO `C` VALUES (0,'2003-05-27','t','t');
INSERT INTO `C` VALUES (1,'2005-05-03','c','c');
INSERT INTO `C` VALUES (9,'2001-04-18','m','m');
INSERT INTO `C` VALUES (5,'2005-12-27','y','y');
INSERT INTO `C` VALUES (6,'2004-08-20','f','f');
INSERT INTO `C` VALUES (2,'1900-01-01','d','d');

 
SELECT `date_key`  
FROM C  
WHERE `varchar_key`  IN (  
SELECT `varchar_nokey`  
FROM C  )  AND `int_key`  =  8   ;

DROP TABLE C;
#/* End of test case for query 0 */

#/* Begin test case for query 1 */

--disable_warnings
DROP TABLE /*! IF EXISTS */ C;
--enable_warnings

CREATE TABLE `C` (
  `int_key` int(11) DEFAULT NULL,
  `date_key` date DEFAULT NULL,
  `varchar_key` varchar(1) DEFAULT NULL,
  KEY `int_key` (`int_key`),
  KEY `date_key` (`date_key`),
  KEY `varchar_key` (`varchar_key`,`int_key`)
) ENGINE=Innodb DEFAULT CHARSET=latin1;
INSERT INTO `C` VALUES (2,NULL,'w');
INSERT INTO `C` VALUES (9,'2001-09-19','m');
INSERT INTO `C` VALUES (3,'2004-09-12','m');
INSERT INTO `C` VALUES (9,NULL,'k');
INSERT INTO `C` VALUES (NULL,'2002-07-19','r');
INSERT INTO `C` VALUES (9,'2002-12-16','t');
INSERT INTO `C` VALUES (3,'2006-02-08','j');
INSERT INTO `C` VALUES (8,'2006-08-28','u');
INSERT INTO `C` VALUES (8,'2001-04-14','h');
INSERT INTO `C` VALUES (53,'2000-01-05','o');
INSERT INTO `C` VALUES (0,'2003-12-06',NULL);
INSERT INTO `C` VALUES (5,'1900-01-01','k');
INSERT INTO `C` VALUES (166,'2002-11-27','e');
INSERT INTO `C` VALUES (3,NULL,'n');
INSERT INTO `C` VALUES (0,'2003-05-27','t');
INSERT INTO `C` VALUES (1,'2005-05-03','c');
INSERT INTO `C` VALUES (9,'2001-04-18','m');
INSERT INTO `C` VALUES (5,'2005-12-27','y');
INSERT INTO `C` VALUES (6,'2004-08-20','f');
INSERT INTO `C` VALUES (2,'1900-01-01','d');

 
SELECT `date_key`  
FROM C  
WHERE `varchar_key`  IN  ( 'w', 'm', 'm', 'k', 'r', 't', 'j', 'u', 'h', 'o', NULL, 'k',
'e', 'n', 't', 'c', 'm', 'y', 'f', 'd' )   AND `int_key`  =  8    /*
TRANSFORM_OUTCOME_UNORDERED_MATCH */;

DROP TABLE C;
#/* End of test case for query 1 */

Suggested fix:
Ensure correct query processing.

EXPLAIN output:

Query 1:
EXPLAIN SELECT `date_key`  
FROM C  
WHERE `varchar_key`  IN (  
SELECT `varchar_nokey`  
FROM C  )  AND `int_key`  =  8   ;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	C	ref	int_key	int_key	5	const	2	Using where
2	DEPENDENT SUBQUERY	C	ALL	NULL	NULL	NULL	NULL	20	Using where

Query 2:
EXPLAIN SELECT `date_key`  
FROM C  
WHERE `varchar_key`  IN  ( 'w', 'm', 'm', 'k', 'r', 't', 'j', 'u', 'h', 'o', NULL, 'k',
'e', 'n', 't', 'c', 'm', 'y', 'f', 'd' )   AND `int_key`  =  8    /*
TRANSFORM_OUTCOME_UNORDERED_MATCH */;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	C	index_merge	int_key,varchar_key	int_key,varchar_key	5,9	NULL	1	Using
intersect(int_key,varchar_key); Using where

I simplified the test case. Notice that there is a difference between having a total of 3
and 4 records in the table

/*!50400 SET SESSION engine_condition_pushdown = 0 */;
CREATE TABLE t1 (
i int(11) DEFAULT NULL,
v1 varchar(1) DEFAULT NULL,
v2 varchar(20) DEFAULT NULL,
KEY i (i),
KEY v (v1,i)
) ENGINE=innodb DEFAULT CHARSET=latin1;
INSERT INTO t1 VALUES (1,'f','no');
INSERT INTO t1 VALUES (2,'u','yes');
INSERT INTO t1 VALUES (2,'h','yes');

# 3 records in the table - CORRECT result

SELECT v2  
FROM t1  
WHERE v1  IN  ( 
'f', 
'd', 
'h', 
'u' )
AND i  =  2;
v2
yes
yes

EXPLAIN 
SELECT v2  
FROM t1  
WHERE v1  IN  ( 
'f', 
'd', 
'h', 
'u' )
AND i  =  2;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	ref	i,v	i	5	const	1	Using where
INSERT INTO t1 VALUES (3,'d','no');

# 4 records in the table - INCORRECT result

SELECT v2  
FROM t1  
WHERE v1  IN  ( 
'f', 
'd', 
'h', 
'u' )
AND i  =  2;
v2
yes

EXPLAIN 
SELECT v2  
FROM t1  
WHERE v1  IN  ( 
'f', 
'd', 
'h', 
'u' )
AND i  =  2;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	index_merge	i,v	i,v	5,9	NULL	1	Using intersect(i,v); Using where
DROP TABLE t1;

Does not fail on MyISAM, Memory or Falcon, but none of these engines perform the lookup
using the intersection.

Some observations:

 * The optimizer chooses to use index merge of index i and index v.

 * For index merge to work, index i and index v need to return 
   records in Rowid order (ROR)

 * AFAIK, only the primary key index of InnoDB is guaranteed to return
   records in Rowid order

 * Index i (QUICK_RANGE_SELECT) returns records in this order:
   [2,u,..],[2,h,..] (this happens to be rowid order, but probably only
   by coincidence)

 * Index v (QUICK_RANGE_SELECT) returns records in this order: 
   [2,h,..],[2,u,..] (this is not rowid order)

 * The following happens in QUICK_ROR_INTERSECT_SELECT:
   index(i)->get_next() => [2,u]
   index(v)->get_next() => [2,h]
   compare record ids: RID([2,h]) > RID([2,u])
   index(i)->get_next() => [2,h] 
   compare record ids: RID([2,h]) == RID([2,h]) => return record
   index(i)->get_next() => EOF, i.e., no more records to return

 * The optimizer decides to use index_merge because InnoDB claims
   that both indexes return records in rowid order. This is the
   relevant test in opt_range.cc#check_quick_select():

   param->is_ror_scan= TRUE;
   if (file->index_flags(keynr, 0, TRUE) & HA_KEY_SCAN_NOT_ROR)
      param->is_ror_scan= FALSE;

   HA_KEY_SCAN_NOT_ROR was introduced by WL#2474/WL#2475, but
   InnoDB's index_flags method was never updated (ha_innodb.h):

   ulong index_flags(uint idx, uint part, bool all_parts) const
   {
     ulong fl= (HA_READ_NEXT |
     HA_READ_PREV |
     HA_READ_ORDER |
     HA_READ_RANGE |
     HA_KEYREAD_ONLY);
     return fl;
   }

 * Under the assumption that only the primary key index in InnoDB
   is guaranteed to return records in rowid order (needs to be
   verified), the following should be added to InnoDB's index_flags():

   if (idx != primary) fl|= HA_KEY_SCAN_NOT_ROR;

Modifying index_flags() in ha_innodb.h as suggested above makes the query return correct
result. The new query plan is:

EXPLAIN extended
SELECT v2  
FROM t1
WHERE v1  IN  ( 
'f', 
'd', 
'h', 
'u' )
AND i  =  2;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	t1	ref	i,v	i	5	const	2	100.00	Using where
Warnings:
Note	1003	select `test`.`t1`.`v2` AS `v2` from `test`.`t1` where ((`test`.`t1`.`i` = 2)
and (`test`.`t1`.`v1` in ('f','d','h','u')))
DROP TABLE t1;

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

3691 Jorgen Loland	2009-10-30
      Bug#48093: 6.0 Server not processing equivalent IN clauses 
                 properly with Innodb tables
      
      InnoDB never appended the HA_KEY_SCAN_NOT_ROR flag in 
      index_flags(). This made the optimizer believe that all indexes
      returned records in ROR (Rowid Ordered Retrieval) order. However,
      only the primary key index returns records in order of row id. 
      
      Since the optimizer thought the indexes were ROR, it could 
      chose to use the index merge strategy on indexes that did not 
      preserve ROR order. This lead to missing records in the result 
      set.
      
      This patch makes index_flags return the HA_KEY_SCAN_NOT_ROR 
      flag unless the index is the primary key index.
     @ mysql-test/r/range.result
        Added test for BUG#48093
     @ mysql-test/t/range.test
        Added test for BUG#48093 and sourced have_innodb.inc so that the added test and
existing tests in this file that actually require InnoDB can use this storage engine.
     @ storage/innobase/handler/ha_innodb.h
        Append HA_KEY_SCAN_NOT_ROR to flags returned from index_flags unless the index is
the primary key index.

The assumption that non-pk indexes do not return rowid ordered rows is only a half truth.
The meaning of HA_KEY_SCAN_NOT_ROR is to specify whether or not single-value lookups in
the index will return rowid ordered records. 

The reason for out of order records in the test case above is the MRR implementation that
looks at each of the values in the IN (...) list one at a time. Although the index will
return ROR records for each of these values (f,u,h,d), the MRR algorithm will not return
ROR for the set of values but rather {ROR for records with v1=f}, then {ROR for records
with v1=d} and so on.

The fix for this bug is to set the retrieval method's is_ror_scan variable to FALSE when
multiple values are used to do the index lookup.

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

3691 Jorgen Loland	2009-11-03
      Bug#48093: 6.0 Server not processing equivalent IN clauses 
                 properly with Innodb tables
      
      When MRR was used to lookup multiple values in an index that
      return ROR ordered records, it was assumed that the returned
      records from MRR were also ROR ordered. This is not true since
      MRR returns all records retrieved for the first value, then all 
      records for the second value and so on. Although the records are
      ROR ordered for each value, the end result is not ROR order.
      
      Since the optimizer thought multi-value lookups returned ROR
      ordered records, it tried to do index merge on the returned
      records. These turned out not to be ROR ordered, resulting in
      incorrect merging and in turn missing rows in the result set.
      
      The fix is to invalidate ROR ordering for index lookup 
      algorithms when looking up multiple key values.
     @ mysql-test/r/range.result
        Added test for BUG#48093
     @ mysql-test/t/range.test
        Added test for BUG#48093 and sourced have_innodb.inc so that the added test and
existing tests in this file (that actually try to use InnoDB) can use this storage
engine.
     @ sql/opt_range.cc
        Invalidate ROR ordering for index lookup algorithms when looking up multiple key
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/89553

3699 Jorgen Loland	2009-11-06
      Bug#48093: 6.0 Server not processing equivalent IN clauses 
                 properly with Innodb tables
            
      When MRR was used to lookup multiple values in an index that
      return ROR ordered records, it was assumed that the returned
      records from MRR were also ROR ordered. This is not true since
      MRR returns all records retrieved for the first value, then all
      records for the second value and so on. Although the records are
      ROR ordered for each value, the end result is not ROR order.
            
      Since the optimizer thought multi-value lookups returned ROR
      ordered records, it tried to do index merge on the returned
      records. These turned out not to be ROR ordered, resulting in
      incorrect merging and in turn missing rows in the result set.
            
      The fix is to invalidate ROR ordering for index lookup 
      algorithms when looking up multiple key values.
     @ mysql-test/r/innodb_mysql.result
        Added test for BUG#48093
     @ mysql-test/t/innodb_mysql.test
        Added test for BUG#48093
     @ sql/opt_range.cc
        Invalidate ROR ordering for index lookup algorithms when looking up multiple key
values.

Pushed to 6.0-codebase-bugfixing 2009-11-06

Jorgen,

For the mysql-6.0-codebase tree (without your patch) you can see in debugger that when
you come to this code for the second index from your test case

  else
  {
    /* Clustered PK scan is always a ROR scan (TODO: same as above) */
    if (param->table->s->primary_key == keynr && pk_is_clustered)
      param->is_ror_scan= TRUE;
  }

you have:

param->table->s->primary_key: 64
keynr: 1
pk_is_clustered: true

and, as a result of it, the assignment
  param->is_ror_scan= TRUE;
is skipped

This is absolutely correct because the index KEY v (v1,i) is not primary,

Yet, the initial setting for param->is_ror_scan is TRUE and remains TRUE.
This is the *actual* problem.

Your patch actually prohibits ROR-scans by primary indexes if there are more
than 1 range. This will effectively lead to performance regressions.

(BTW, this bug should be seen with MRR disabled as well)

Regards,
Igor.

Pushed into 6.0.14-alpha (revid:kostja@sun.com-20091120124947-yi6h2jbgw0kbciwm) (version
source revid:jorgen.loland@sun.com-20091106074019-cqoxr3hvmbgqcldt) (merge vers:
6.0.14-alpha) (pib:13)