Bug #68194 Wrong result (missing row) with index_merge
Submitted: 27 Jan 2013 22:50 Modified: 31 Jan 2013 16:03
Reporter: Elena Stepanova Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.1, 5.5, 5.6.9 OS:Any
Assigned to: CPU Architecture:Any
Triage: Needs Triage: D2 (Serious)

[27 Jan 2013 22:50] Elena Stepanova
Description:
With the structure and data provided in 'How to repeat' section, the following query returns an empty result set with index_merge=on (default) and 1 row with index_merge=off. The latter is the correct result, since the row satisfies the first condition on pk, and the big OR condition should be irrelevant.

set optimizer_switch='index_merge=on';
SELECT  * FROM t1 WHERE 
pk IN ( 255, 2, 193, 255, 106 )  
OR ( 
( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
AND 
( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 ) 
) 
AND ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' ) 
;
pk	f1	f2	f3	f4	f5
set optimizer_switch='index_merge=off';
SELECT  * FROM t1 WHERE 
pk IN ( 255, 2, 193, 255, 106 )  
OR ( 
( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
AND 
( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 ) 
) 
AND ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' ) 
;
pk	f1	f2	f3	f4	f5
2	345	123	h	M	w

EXPLAIN with index_merge:

select_type	SIMPLE
table	t1
type	index_merge
possible_keys	PRIMARY,f1,f4,f5
key	f4,f5,PRIMARY
key_len	13,67,4
ref	NULL
rows	5
filtered	100.00
Extra	Using sort_union(f4,f5,PRIMARY); Using where
Warnings:
Level	Note
Code	1003
Message	select `test`.`t1`.`pk` AS `pk`,`test`.`t1`.`f1` AS `f1`,`test`.`t1`.`f2` AS `f2`,`test`.`t1`.`f3` AS `f3`,`test`.`t1`.`f4` AS `f4`,`test`.`t1`.`f5` AS `f5` from `test`.`t1` where ((`test`.`t1`.`pk` in (255,2,193,255,106)) or (((`test`.`t1`.`f5` in ('why','uv')) or (`test`.`t1`.`f4` <> 'mm')) and ((`test`.`t1`.`pk` = 1) or (`test`.`t1`.`f1` not between 8 and <cache>((3 + 133)))) and ((`test`.`t1`.`f4` like 'Wyoming') or (`test`.`t1`.`f5` like 'Oregon'))))

How to repeat:
CREATE TABLE t1 (
  pk INT PRIMARY KEY,
  f1 INT,
  f2 INT,
  f3 VARCHAR(10),
  f4 VARCHAR(10),
  f5 VARCHAR(64),
  KEY (f1),
  key (f4),
  key (f5)
) ENGINE=MyISAM;

INSERT INTO t1 VALUES  
 (2, 345, 123, 'h', 'M', 'w') , 
 (3, 46,   61235, 'N', 'w', 'r') , 
 (4, 69,   0, 'why', 'Washington', 'itis') ,  
 (5, 7325, 0,  'z', 'n', 'm') ,
 (6, 297, 234, 'r', 'r', 'then') , 
 (7, 5352, 0, 'California', 'zp', 'pfkxceksatefqsdksjijcszxwbjj') , 
 (8, 102,  54729, 'a', 'r', 'f') ,  
 (9, 6623,  27839, 't', 'want', 'xceksatefqsdksjijcs') , 
 (10, 5189,  239, 'e', 'Illinois', 'say') , 
 (11, 16638, NULL, 's', 'Iowa', 'Alabama') , 
 (12, 343, 234, 'now', 'Oklahoma', 'now') , 
 (13, 3,   37398, 'tefqsdksji', 'Louisiana', 'Arkansas') ,  
 (14, 2620, 182, 'ef', 'f', 'Minnesota') ,  
 (15, 7778, 0, 'qs', 'mm', 'now') ,  
 (16, 454, 153, 'sdk', 'a', 'dksjijcszxwbjjvvk') ,  
 (17, 0,  353, 's', 'j', 'n') , 
 (18, 16406,  24, 'MA', 'i', 'r') , 
 (19, 60642,  75, 'l', 'California', 'ok') ,  
 (20, 6,   52133, 'm', 'New Jer', 'e') ,  
 (21, 8025, 3, 'zxwbjjvvk', 'did', 'h') , 
 (22, 575,  5, 'South Caro', 'w', 'bj') ,
 (23, 3,   37398, 'tefqsdksji', 'Louisiana', 'Arkansas') ,  
 (24, 2620, 182, 'ef', 'f', 'Minnesota') ,  
 (25, 7778, 0, 'qs', 'mm', 'now') ,  
 (26, 454, 153, 'sdk', 'a', 'dksjijcszxwbjjvvk') ,  
 (27, 0,  353, 's', 'j', 'n') , 
 (28, 16406,  24, 'MA', 'i', 'r') , 
 (29, 60642,  75, 'l', 'California', 'ok') ,  
 (30, 6,   52133, 'm', 'New Jer', 'e') 
;

set optimizer_switch='index_merge=on';

SELECT  * FROM t1 WHERE 
  pk IN ( 255, 2, 193, 255, 106 )  
  OR ( 
      ( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
        AND 
      ( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 ) 
    ) 
    AND ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' ) 
;

set optimizer_switch='index_merge=on';

SELECT  * FROM t1 WHERE 
  pk IN ( 255, 2, 193, 255, 106 )  
  OR ( 
      ( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
        AND 
      ( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 ) 
    ) 
    AND ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' ) 
;
[27 Jan 2013 22:54] Elena Stepanova
Sorry, the last fragment in the test is not needed, it's just a duplicate remained from an intermediate test case (starting from the second 'SET optimizer_switch').
[28 Jan 2013 12:02] Simon Martin
I think the bug on the reported test case is when index_merge is off.

The final "AND ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' )" is outside the OR so should be satisfied along with the PK condition, but in the returned result with  index_merge=off it is not.

However if you move the bracket to put the last AND inside the OR the bug seems to move, as now index_merge=on still returns no result (which it should I think). So the bug as stated by Elena is there too?

On 5.5:

mysql> set query_cache_type = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> set optimizer_switch='index_merge=on';
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT  * FROM t1 WHERE 
    ->   pk IN ( 255, 2, 193, 255, 106 )  
    ->   OR ( 
    ->       ( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
    ->         AND 
    ->       ( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 ) 
    ->     ) 
    ->     AND ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' ) 
    -> ;
Empty set (0.00 sec)

mysql> set optimizer_switch='index_merge=off';
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT  * FROM t1 WHERE 
    ->   pk IN ( 255, 2, 193, 255, 106 )  
    ->   OR ( 
    ->       ( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
    ->         AND 
    ->       ( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 ) 
    ->     ) 
    ->     AND ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' ) 
    -> ;
+----+------+------+------+------+------+
| pk | f1   | f2   | f3   | f4   | f5   |
+----+------+------+------+------+------+
|  2 |  345 |  123 | h    | M    | w    |
+----+------+------+------+------+------+
1 row in set (0.00 sec)

mysql> set optimizer_switch='index_merge=on';
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT sql_no_cache  * FROM t1 WHERE 
    ->   pk IN ( 255, 2, 193, 255, 106 )  
    ->   OR ( 
    ->       ( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
    ->         AND 
    ->       ( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 )  
    ->         AND 
    ->       ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' ) 
    ->     )
    -> ;
Empty set (0.00 sec)

mysql> 
mysql> set optimizer_switch='index_merge=off';
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT sql_no_cache * FROM t1 WHERE 
    ->   pk IN ( 255, 2, 193, 255, 106 )  
    ->   OR ( 
    ->       ( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) ) 
    ->         AND 
    ->       ( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 ) 
    ->         AND 
    ->       ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' )  
    ->     )
    -> ;
+----+------+------+------+------+------+
| pk | f1   | f2   | f3   | f4   | f5   |
+----+------+------+------+------+------+
|  2 |  345 |  123 | h    | M    | w    |
+----+------+------+------+------+------+
1 row in set (0.00 sec)
[28 Jan 2013 13:07] Miguel Solorzano
Thank you for the bug report.

mysql 5.5 > SELECT sql_no_cache * FROM t1 WHERE
    ->    pk IN ( 255, 2, 193, 255, 106 )
    ->    OR (
    ->        ( f5 IN ( 'why' , 'uv' ) OR NOT ( f4 = 'mm' ) )
    ->          AND
    ->      ( ( pk = 1 ) OR f1 NOT BETWEEN 8 AND 3 + 133 )
    ->          AND
    ->        ( f4 LIKE 'Wyoming' OR f5 LIKE 'Oregon' )
    ->      )
    ->  ;
+----+------+------+------+------+------+
| pk | f1   | f2   | f3   | f4   | f5   |
+----+------+------+------+------+------+
|  2 |  345 |  123 | h    | M    | w    |
+----+------+------+------+------+------+
1 row in set (0.00 sec)

mysql 5.5 >show variables like "%version%";
+-------------------------+---------------------+
| Variable_name           | Value               |
+-------------------------+---------------------+
| innodb_version          | 5.5.31              |
| protocol_version        | 10                  |
| slave_type_conversions  |                     |
| version                 | 5.5.31              |
| version_comment         | Source distribution |
| version_compile_machine | x86                 |
| version_compile_os      | Win64               |
+-------------------------+---------------------+
7 rows in set (0.00 sec)
[28 Jan 2013 13:36] Elena Stepanova
@Godofredo Miguel Solorzano

Hi,

I don't quite understand the verification comment -- do you consider the *non*-empty result set to be a bug? Not sure how you got it though, is it with index_merge ON or OFF? Or do you mean that it's been already fixed in 5.5.31 (why 'verified', then?)

@Simon Martin

Hi,

Given the order of precedence for OR and AND, your change does not make a difference. In an essence, we initially have

A || ( ( B || C ) && ( D || E ) ) && ( F || G ) 

so, A is self-sufficient. 

They all are equivalents

A || ( ( B || C ) && ( D || E ) ) && ( F || G ) 
A || ( B || C ) && ( D || E ) && ( F || G )
A || ( ( B || C ) && ( D || E ) && ( F || G ) )

The last of which is yours.
[28 Jan 2013 14:24] Simon Martin
@Elena Thanks, you're right of course. I missed that.
[28 Jan 2013 14:51] Jørgen Løland
@Elena: The bug is confirmed as described. Thank you for the bug report.
[28 Jan 2013 15:58] Miguel Solorzano
@Elena the bug was verified, sorry I pasted partial results. Thanks.
[31 Jan 2013 16:03] Paul Dubois
Noted in 5.6.11 changelog.

A bug in range optimization sometimes led to incorrect condition
calculation for index merge union. This could lead to missing rows.