LP:920713 - Wrong result (missing rows) with firstmatch+BNL, IN subquery, MyISAM or InnoDB, given join order

The following query

SELECT * FROM t1 alias1, t2 alias2
WHERE alias2.c IN (
SELECT alias4.c FROM t1 alias3, t2 alias4
);

on test data returns two or 14 rows depending on the table join order. 14 is correct.

bzr version-info
revision-id: <email address hidden>
date: 2012-01-23 15:14:13 +0200
build-date: 2012-01-24 02:51:18 +0400
revno: 3393
branch-nick: maria-5.3

The test case also requires debug_optimizer_prefer_join_prefix.
Initially a similar problem was observed on 5.3-extended_keys, on a more complicated dataset and query, without debug_optimizer_prefer_join_prefix, a different join order was chosen with and without extended_keys.

EXPLAIN with debug_optimizer_prefer_join_prefix=alias2,alias4,alias1,alias3 (wrong result):

id select_type table type possible_keys key key_len ref rowsfiltered Extra
1 PRIMARY alias2 ALL NULL NULL NULL NULL 2 100.00
1 PRIMARY alias4 ALL NULL NULL NULL NULL 2 100.00 Using where; FirstMatch(alias2); Using join buffer (flat, BNL join)
1 PRIMARY alias1 ALL NULL NULL NULL NULL 7 100.00 Using join buffer (incremental, BNL join)
1 PRIMARY alias3 ALL NULL NULL NULL NULL 7 100.00 FirstMatch(alias1); Using join buffer (incremental, BNL join)
Warnings:
Note 1003 select `test`.`alias1`.`a` AS `a`,`test`.`alias2`.`b` AS `b`,`test`.`alias2`.`c` AS `c` from `test`.`t1` `alias1` semi join (`test`.`t1` `alias3` join `test`.`t2` `alias4`) join `test`.`t2` `alias2` where (`test`.`alias4`.`c` = `test`.`alias2`.`c`)

EXPLAIN without specified join order:

id select_type table type possible_keys key key_len ref rowsfiltered Extra
1 PRIMARY alias2 ALL NULL NULL NULL NULL 2 100.00
1 PRIMARY alias4 ALL NULL NULL NULL NULL 2 100.00 Using where; Using join buffer (flat, BNL join)
1 PRIMARY alias3 ALL NULL NULL NULL NULL 7 100.00 FirstMatch(alias2); Using join buffer (incremental, BNL join)
1 PRIMARY alias1 ALL NULL NULL NULL NULL 7 100.00 Using join buffer (incremental, BNL join)
Warnings:
Note 1003 select `test`.`alias1`.`a` AS `a`,`test`.`alias2`.`b` AS `b`,`test`.`alias2`.`c` AS `c` from `test`.`t1` `alias1` semi join (`test`.`t1` `alias3` join `test`.`t2` `alias4`) join `test`.`t2` `alias2` where (`test`.`alias4`.`c` = `test`.`alias2`.`c`)

Minimal optimizer_switch: semijoin=on,firstmatch=on,join_cache_incremental=on,semijoin_with_cache=on
Full optimizer_switch: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off,index_condition_pushdown=on,derived_merge=on,derived_with_keys=on,firstmatch=on,loosescan=on,materialization=on,in_to_exists=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr=off,mrr_cost_based=off,mrr_sort_keys=off,outer_join_with_cache=on,semijoin_with_cache=on,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on,optimize_join_buffer_size=off,table_elimination=on

Test case:

SET optimizer_switch = 'semijoin=on,firstmatch=on,join_cache_incremental=on,semijoin_with_cache=on';

1. t1 should be MyISAM or InnoDB
   CREATE TABLE t1 ( a VARCHAR(1) ) ENGINE=MyISAM;
   INSERT INTO t1 VALUES
   ('e'),('w'),('a'),('h'),('x'),('k'),('g');
   CREATE TABLE t2 ( b INT, c VARCHAR(1) );
   INSERT INTO t2 VALUES (0,'j'),(8,'v');

SET debug_optimizer_prefer_join_prefix=
'alias2,alias4,alias1,alias3';

SELECT * FROM t1 alias1, t2 alias2
WHERE alias2.c IN (
SELECT alias4.c FROM t1 alias3, t2 alias4
);

1. End of test case

1. Expected test result:

a b c
e 0 j
e 8 v
w 0 j
w 8 v
a 0 j
a 8 v
h 0 j
h 8 v
x 0 j
x 8 v
k 0 j
k 8 v
g 0 j
g 8 v

1. Actual test result:

a b c
e 0 j
e 8 v