Assertion failure or valgrind errors at best_access_path with firstmatch + materialization + semijoin + semijoin_with_cache, GROUP BY

[Elena Stepanova]

==28721== Thread 4:
==28721== Conditional jump or move depends on uninitialised value(s)
==28721== at 0x8360467: best_access_path(JOIN*, st_join_table*, unsigned long long, unsigned int, bool, double, st_position*, st_position*) (sql_select.cc:5451)
==28721== by 0x8424C43: fix_semijoin_strategies_for_picked_join_order(JOIN*) (opt_subselect.cc:3303)
==28721== by 0x8363D66: get_best_combination(JOIN*) (sql_select.cc:7326)
==28721== by 0x835C0DC: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3641)
==28721== by 0x8353BF8: JOIN::optimize() (sql_select.cc:1150)
==28721== by 0x8359B2B: mysql_select(THD*, Item***, TABLE_LIST*, unsigned int, List<Item>&, Item*, unsigned int, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (sql_select.cc:2949)
==28721== by 0x8351776: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:285)
==28721== by 0x82EC6B8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5151)
==28721== by 0x82E3A94: mysql_execute_command(THD*) (sql_parse.cc:2284)
==28721== by 0x82EECF3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6152)
==28721== by 0x82E16D4: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1228)
==28721== by 0x82E0B7E: do_command(THD*) (sql_parse.cc:923)
==28721== by 0x82DDA74: handle_one_connection (sql_connect.cc:1218)
==28721== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==28721== by 0x42F538D: clone (in /lib/libc-2.11.2.so)
==28721== Conditional jump or move depends on uninitialised value(s)
==28721== at 0x8360493: best_access_path(JOIN*, st_join_table*, unsigned long long, unsigned int, bool, double, st_position*, st_position*) (sql_select.cc:5451)
==28721== by 0x8424C43: fix_semijoin_strategies_for_picked_join_order(JOIN*) (opt_subselect.cc:3303)
==28721== by 0x8363D66: get_best_combination(JOIN*) (sql_select.cc:7326)
==28721== by 0x835C0DC: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3641)
==28721== by 0x8353BF8: JOIN::optimize() (sql_select.cc:1150)
==28721== by 0x8359B2B: mysql_select(THD*, Item***, TABLE_LIST*, unsigned int, List<Item>&, Item*, unsigned int, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (sql_select.cc:2949)
==28721== by 0x8351776: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:285)
==28721== by 0x82EC6B8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5151)
==28721== by 0x82E3A94: mysql_execute_command(THD*) (sql_parse.cc:2284)
==28721== by 0x82EECF3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6152)
==28721== by 0x82E16D4: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1228)
==28721== by 0x82E0B7E: do_command(THD*) (sql_parse.cc:923)
==28721== by 0x82DDA74: handle_one_connection (sql_connect.cc:1218)
==28721== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==28721== by 0x42F538D: clone (in /lib/libc-2.11.2.so)
==28721== Conditional jump or move depends on uninitialised value(s)
==28721== at 0x836051F: best_access_path(JOIN*, st_join_table*, unsigned long long, unsigned int, bool, double, st_position*, st_position*) (sql_select.cc:5455)
==28721== by 0x8424C43: fix_semijoin_strategies_for_picked_join_order(JOIN*) (opt_subselect.cc:3303)
==28721== by 0x8363D66: get_best_combination(JOIN*) (sql_select.cc:7326)
==28721== by 0x835C0DC: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3641)
==28721== by 0x8353BF8: JOIN::optimize() (sql_select.cc:1150)
==28721== by 0x8359B2B: mysql_select(THD*, Item***, TABLE_LIST*, unsigned int, List<Item>&, Item*, unsigned int, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (sql_select.cc:2949)
==28721== by 0x8351776: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:285)
==28721== by 0x82EC6B8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5151)
==28721== by 0x82E3A94: mysql_execute_command(THD*) (sql_parse.cc:2284)
==28721== by 0x82EECF3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6152)
==28721== by 0x82E16D4: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1228)
==28721== by 0x82E0B7E: do_command(THD*) (sql_parse.cc:923)
==28721== by 0x82DDA74: handle_one_connection (sql_connect.cc:1218)
==28721== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==28721== by 0x42F538D: clone (in /lib/libc-2.11.2.so)
==28721== Conditional jump or move depends on uninitialised value(s)
==28721== at 0x8360B75: best_access_path(JOIN*, st_join_table*, unsigned long long, unsigned int, bool, double, st_position*, st_position*) (sql_select.cc:5609)
==28721== by 0x8424C43: fix_semijoin_strategies_for_picked_join_order(JOIN*) (opt_subselect.cc:3303)
==28721== by 0x8363D66: get_best_combination(JOIN*) (sql_select.cc:7326)
==28721== by 0x835C0DC: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3641)
==28721== by 0x8353BF8: JOIN::optimize() (sql_select.cc:1150)
==28721== by 0x8359B2B: mysql_select(THD*, Item***, TABLE_LIST*, unsigned int, List<Item>&, Item*, unsigned int, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (sql_select.cc:2949)
==28721== by 0x8351776: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:285)
==28721== by 0x82EC6B8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5151)
==28721== by 0x82E3A94: mysql_execute_command(THD*) (sql_parse.cc:2284)
==28721== by 0x82EECF3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6152)
==28721== by 0x82E16D4: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1228)
==28721== by 0x82E0B7E: do_command(THD*) (sql_parse.cc:923)
==28721== by 0x82DDA74: handle_one_connection (sql_connect.cc:1218)
==28721== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==28721== by 0x42F538D: clone (in /lib/libc-2.11.2.so)
==28721== Conditional jump or move depends on uninitialised value(s)
==28721== at 0x8360B85: best_access_path(JOIN*, st_join_table*, unsigned long long, unsigned int, bool, double, st_position*, st_position*) (sql_select.cc:5609)
==28721== by 0x8424C43: fix_semijoin_strategies_for_picked_join_order(JOIN*) (opt_subselect.cc:3303)
==28721== by 0x8363D66: get_best_combination(JOIN*) (sql_select.cc:7326)
==28721== by 0x835C0DC: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3641)
==28721== by 0x8353BF8: JOIN::optimize() (sql_select.cc:1150)
==28721== by 0x8359B2B: mysql_select(THD*, Item***, TABLE_LIST*, unsigned int, List<Item>&, Item*, unsigned int, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (sql_select.cc:2949)
==28721== by 0x8351776: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:285)
==28721== by 0x82EC6B8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5151)
==28721== by 0x82E3A94: mysql_execute_command(THD*) (sql_parse.cc:2284)
==28721== by 0x82EECF3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6152)
==28721== by 0x82E16D4: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1228)
==28721== by 0x82E0B7E: do_command(THD*) (sql_parse.cc:923)
==28721== by 0x82DDA74: handle_one_connection (sql_connect.cc:1218)
==28721== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==28721== by 0x42F538D: clone (in /lib/libc-2.11.2.so)
==28721== Conditional jump or move depends on uninitialised value(s)
==28721== at 0x8360BFD: best_access_path(JOIN*, st_join_table*, unsigned long long, unsigned int, bool, double, st_position*, st_position*) (sql_select.cc:5609)
==28721== by 0x8424C43: fix_semijoin_strategies_for_picked_join_order(JOIN*) (opt_subselect.cc:3303)
==28721== by 0x8363D66: get_best_combination(JOIN*) (sql_select.cc:7326)
==28721== by 0x835C0DC: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3641)
==28721== by 0x8353BF8: JOIN::optimize() (sql_select.cc:1150)
==28721== by 0x8359B2B: mysql_select(THD*, Item***, TABLE_LIST*, unsigned int, List<Item>&, Item*, unsigned int, st_order*, st_order*, Item*, st_order*, unsigned long long, select_result*, st_select_lex_unit*, st_select_lex*) (sql_select.cc:2949)
==28721== by 0x8351776: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:285)
==28721== by 0x82EC6B8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5151)
==28721== by 0x82E3A94: mysql_execute_command(THD*) (sql_parse.cc:2284)
==28721== by 0x82EECF3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6152)
==28721== by 0x82E16D4: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1228)
==28721== by 0x82E0B7E: do_command(THD*) (sql_parse.cc:923)
==28721== by 0x82DDA74: handle_one_connection (sql_connect.cc:1218)
==28721== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==28721== by 0x42F538D: clone (in /lib/libc-2.11.2.so)

With a more complicated test case it turns into an assertion failure:
sql_select.cc:5451: void best_access_path(JOIN*, JOIN_TAB*, table_map, uint, bool, double, POSITION*, POSITION*): Assertion `tmp > 0 || record_count == 0' failed

bzr version-info
revision-id: <email address hidden>
date: 2012-05-08 20:58:41 +0300
revno: 3519

Also reproducible on maria/5.5 revno 3397.

Minimal optimizer_switch: firstmatch=on,materialization=on,semijoin=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

EXPLAIN:
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY B system NULL NULL NULL NULL 1 100.00 Using temporary; Using filesort
1 PRIMARY alias1 ref a1 a1 6 const 1 100.00 Using where; Using index
1 PRIMARY <subquery3> ALL distinct_key NULL NULL NULL 2 100.00 Using where
1 PRIMARY A ref a1 a1 6 test.alias1.a2 100 100.00 Using where; Using index; FirstMatch((sj-nest))
1 PRIMARY alias2 index a1 a1 44 NULL 100 75.00 Using where; Using index; Using join buffer (flat, BNL join)
3 MATERIALIZED C index PRIMARY PRIMARY 23 NULL 2 100.00 Using index
Warnings:
Note 1003 select `test`.`alias1`.`a1` AS `field1` from `test`.`A` `alias1` semi join (`test`.`A` join `test`.`B`) semi join (`test`.`C`) join `test`.`A` `alias2` where ((`test`.`C`.`c1` = `test`.`alias1`.`a1`) and (`test`.`alias2`.`a1` = `test`.`alias1`.`a1`) and isnull(`test`.`alias1`.`a1`) and (`test`.`alias1`.`a2` = `test`.`A`.`a1`)) group by `test`.`alias1`.`a1`

# Test case:

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

CREATE TABLE A (a1 VARCHAR(3), a2 VARCHAR(35), KEY(a1,a2)) ENGINE=MyISAM;
INSERT INTO A VALUES
('USA','Arvada'),('USA','Athens'),('USA','Atlanta'),('USA','Augusta'),
('USA','Aurora'),('USA','Aurora'),('USA','Austin'),('USA','Bakersfield'),
('USA','Baltimore'),('USA','Baton'),('USA','Beaumont'),('USA','Bellevue'),
('USA','Berkeley'),('USA','Billings'),('USA','Birmingham'),('USA','Boise'),
('USA','Boston'),('USA','Boulder'),('USA','Bridgeport'),('USA','Brockton'),
('USA','Brownsville'),('USA','Buffalo'),('USA','Burbank'),('USA','Cambridge'),
('USA','Cape'),('USA','Carrollton'),('USA','Carson'),('USA','Cary'),
('USA','Cedar'),('USA','Chandler'),('USA','Charleston'),('USA','Charlotte'),
('USA','Chattanooga'),('USA','Chesapeake'),('USA','Chicago'),('USA','Chula'),
('USA','Cincinnati'),('USA','Citrus'),('USA','Clarksville'),('USA','Clearwater'),
('USA','Cleveland'),('USA','Colorado'),('USA','Columbia'),('USA','Columbus'),
('USA','Columbus'),('USA','Compton'),('USA','Concord'),('USA','Coral'),
('USA','Corona'),('USA','Corpus'),('USA','Costa'),('USA','Dallas'),('USA','Daly'),
('USA','Davenport'),('USA','Dayton'),('USA','Denver'),('USA','DesMoines'),
('USA','Detroit'),('USA','Downey'),('USA','Durham'),('USA','East'),('USA','ElCajon'),
('USA','ElMonte'),('USA','ElPaso'),('USA','Elgin'),('USA','Elizabeth'),
('USA','Erie'),('USA','Escondido'),('USA','Eugene'),('USA','Evansville'),
('USA','Fairfield'),('USA','Fall'),('USA','Fayetteville'),('USA','Flint'),
('USA','Fontana'),('USA','FortCollins'),('USA','FortLauderdale'),('USA','FortWayne'),
('USA','FortWorth'),('USA','Fremont'),('USA','Fresno'),('USA','Fullerton'),
('USA','Gainesville'),('USA','GardenGrove'),('USA','Garland'),('USA','Gary'),
('USA','Gilbert'),('USA','Glendale'),('USA','Glendale'),('USA','GrandPrairie'),
('USA','GrandRapids'),('USA','Green Bay'),('USA','Greensboro'),('USA','Hampton'),
('USA','Hartford'),('USA','Hayward'),('USA','Henderson'),('USA','Hialeah'),
('USA','Inglewood'),('USA','Livonia');

CREATE TABLE C (c1 VARCHAR(3), c2 VARCHAR(16), PRIMARY KEY (c1,c2)) ENGINE=MyISAM;
INSERT INTO C VALUES ('USA','Chinese'), ('USA','English');

# Not reproducible with 2 rows
CREATE TABLE B (b1 INT) ENGINE=MyISAM;
INSERT INTO B VALUES (1);

SELECT alias1.a1 AS field1
FROM A AS alias1, A AS alias2
WHERE alias1.a2 IN ( SELECT a1 FROM A, B )
AND alias1.a1 IS NULL
AND ( alias1.a1, alias2.a1 ) IN ( SELECT c1, c1 FROM C )
GROUP BY field1;

# End of test case