Valgrind warnings or server crash in best_access_path with extended_keys+derived_with_keys, STRAIGHT_JOIN, view or FROM subquery

[Elena Stepanova]

The simplified test case causes valgrind warnings:

==5385== Thread 4:
==5385== Conditional jump or move depends on uninitialised value(s)
==5385== at 0x858B2E7: Bitmap<64u>::is_prefix(unsigned int) const (sql_bitmap.h:163)
==5385== by 0x853081B: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3385)
==5385== by 0x8521C44: JOIN::optimize() (sql_select.cc:1145)
==5385== by 0x852DBEE: 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:2911)
==5385== by 0x851CF74: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:283)
==5385== by 0x843BDB9: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5148)
==5385== by 0x842943E: mysql_execute_command(THD*) (sql_parse.cc:2281)
==5385== by 0x8440E1F: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6149)
==5385== by 0x8424838: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1227)
==5385== by 0x8422EDE: do_command(THD*) (sql_parse.cc:922)
==5385== by 0x841C3D1: handle_one_connection (sql_connect.cc:1193)
==5385== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==5385== by 0x42F534D: clone (in /lib/libc-2.11.2.so)
==5385==
==5385== Conditional jump or move depends on uninitialised value(s)
==5385== at 0x853081E: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3385)
==5385== by 0x8521C44: JOIN::optimize() (sql_select.cc:1145)
==5385== by 0x852DBEE: 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:2911)
==5385== by 0x851CF74: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:283)
==5385== by 0x843BDB9: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5148)
==5385== by 0x842943E: mysql_execute_command(THD*) (sql_parse.cc:2281)
==5385== by 0x8440E1F: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6149)
==5385== by 0x8424838: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1227)
==5385== by 0x8422EDE: do_command(THD*) (sql_parse.cc:922)
==5385== by 0x841C3D1: handle_one_connection (sql_connect.cc:1193)
==5385== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==5385== by 0x42F534D: clone (in /lib/libc-2.11.2.so)
==5385==
==5385== Conditional jump or move depends on uninitialised value(s)
==5385== at 0x85393E2: best_access_path(JOIN*, st_join_table*, unsigned long long, unsigned int, bool, double, st_position*, st_position*) (sql_select.cc:5156)
==5385== by 0x853DBB7: best_extension_by_limited_search(JOIN*, unsigned long long, unsigned int, double, double, unsigned int, unsigned int) (sql_select.cc:6404)
==5385== by 0x853E23C: best_extension_by_limited_search(JOIN*, unsigned long long, unsigned int, double, double, unsigned int, unsigned int) (sql_select.cc:6465)
==5385== by 0x853CA1F: greedy_search(JOIN*, unsigned long long, unsigned int, unsigned int) (sql_select.cc:6021)
==5385== by 0x853BC2B: choose_plan(JOIN*, unsigned long long) (sql_select.cc:5682)
==5385== by 0x8531BEA: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3562)
==5385== by 0x8521C44: JOIN::optimize() (sql_select.cc:1145)
==5385== by 0x852DBEE: 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:2911)
==5385== by 0x851CF74: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:283)
==5385== by 0x843BDB9: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5148)
==5385== by 0x842943E: mysql_execute_command(THD*) (sql_parse.cc:2281)
==5385== by 0x8440E1F: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6149)
==5385== by 0x8424838: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1227)
==5385== by 0x8422EDE: do_command(THD*) (sql_parse.cc:922)
==5385== by 0x841C3D1: handle_one_connection (sql_connect.cc:1193)
==5385== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==5385==
==5385== Conditional jump or move depends on uninitialised value(s)
==5385== at 0x8542E36: create_ref_for_key(JOIN*, st_join_table*, keyuse_t*, bool, unsigned long long) (sql_select.cc:7507)
==5385== by 0x8540EF4: get_best_combination(JOIN*) (sql_select.cc:7176)
==5385== by 0x8532007: make_join_statistics(JOIN*, List<TABLE_LIST>&, Item*, st_dynamic_array*) (sql_select.cc:3591)
==5385== by 0x8521C44: JOIN::optimize() (sql_select.cc:1145)
==5385== by 0x852DBEE: 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:2911)
==5385== by 0x851CF74: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:283)
==5385== by 0x843BDB9: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5148)
==5385== by 0x842943E: mysql_execute_command(THD*) (sql_parse.cc:2281)
==5385== by 0x8440E1F: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6149)
==5385== by 0x8424838: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1227)
==5385== by 0x8422EDE: do_command(THD*) (sql_parse.cc:922)
==5385== by 0x841C3D1: handle_one_connection (sql_connect.cc:1193)
==5385== by 0x40C9B24: start_thread (in /lib/libpthread-2.11.2.so)
==5385== by 0x42F534D: clone (in /lib/libc-2.11.2.so)

A more complicated scenario, including a sequence of several statements, causes a server crash:

#4 <signal handler called>
#5 0x08539601 in best_access_path (join=0x9eb85b8, s=0x9ed99b4, remaining_tables=2, idx=1, disable_jbuf=false, record_count=10,
    pos=0x9ebb888, loose_scan_pos=0xae994754) at sql_select.cc:5197
#6 0x0853dbb8 in best_extension_by_limited_search (join=0x9eb85b8, remaining_tables=2, idx=1, record_count=10, read_time=4.1201171875,
    search_depth=61, prune_level=1) at sql_select.cc:6404
#7 0x0853e23d in best_extension_by_limited_search (join=0x9eb85b8, remaining_tables=3, idx=0, record_count=1, read_time=0,
    search_depth=62, prune_level=1) at sql_select.cc:6465
#8 0x0853ca20 in greedy_search (join=0x9eb85b8, remaining_tables=3, search_depth=62, prune_level=1) at sql_select.cc:6021
#9 0x0853bc2c in choose_plan (join=0x9eb85b8, join_tables=3) at sql_select.cc:5682
#10 0x08531beb in make_join_statistics (join=0x9eb85b8, tables_list=..., conds=0x9ed9478, keyuse_array=0x9ebea58) at sql_select.cc:3562
#11 0x08521c45 in JOIN::optimize (this=0x9eb85b8) at sql_select.cc:1145
#12 0x0852dbef in mysql_select (thd=0x9e61c68, rref_pointer_array=0x9e637dc, tables=0x9e6d8c8, wild_num=0, fields=..., conds=0x9ea3b48,
    og_num=3, order=0x9ea3df8, group=0x9ea3ce0, having=0x0, proc_param=0x0, select_options=2147764232, result=0x9ea3ff0, unit=0x9e633c0,
    select_lex=0x9e636a0) at sql_select.cc:2911
#13 0x0851cf75 in handle_select (thd=0x9e61c68, lex=0x9e63364, result=0x9ea3ff0, setup_tables_done_option=0) at sql_select.cc:283
#14 0x0843bdba in execute_sqlcom_select (thd=0x9e61c68, all_tables=0x9e6d8c8) at sql_parse.cc:5148
#15 0x0842943f in mysql_execute_command (thd=0x9e61c68) at sql_parse.cc:2281
#16 0x08440e20 in mysql_parse (thd=0x9e61c68,
    rawbuf=0x9e6cec8 "SELECT SQL_SMALL_RESULT alias1 . `col_int_key` AS field1 FROM ( C AS alias1 STRAIGHT_JOIN ( SELECT DISTINCT SQ1_alias1 . * FROM ( C AS SQ1_alias1 STRAIGHT_JOIN CC AS SQ1_alias2 ON (SQ1_alias2 . `c"..., length=761, found_semicolon=0xae996234)
    at sql_parse.cc:6149
#17 0x08424839 in dispatch_command (command=COM_QUERY, thd=0x9e61c68,
    packet=0x9e63de9 "SELECT SQL_SMALL_RESULT alias1 . `col_int_key` AS field1 FROM ( C AS alias1 STRAIGHT_JOIN ( SELECT DISTINCT SQ1_alias1 . * FROM ( C AS SQ1_alias1 STRAIGHT_JOIN CC AS SQ1_alias2 ON (SQ1_alias2 . `c"..., packet_length=761) at sql_parse.cc:1227
#18 0x08422edf in do_command (thd=0x9e61c68) at sql_parse.cc:922
#19 0x0841c3d2 in handle_one_connection (arg=0x9e61c68) at sql_connect.cc:1193
#20 0xb77f3b25 in start_thread () from /lib/libpthread.so.0

bzr version-info
revision-id: <email address hidden>
date: 2012-01-01 22:42:11 -0800
build-date: 2012-01-12 16:22:46 +0400
revno: 3379
branch-nick: lp-5.3-extended_keys

Could not reproduce with extended_keys=OFF.

EXPLAIN (causes the same warnings or crash as the query):

id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY t1 ALL NULL NULL NULL NULL 2 100.00 Using where
1 PRIMARY <derived2> ref key0 key0 5 test.t1.a 1 100.00
2 DERIVED t2 ALL NULL NULL NULL NULL 4 100.00 Using temporary
2 DERIVED t3 ALL NULL NULL NULL NULL 0 0.00 Using join buffer (flat, BNL join)
Warnings:
Note 1003 select `test`.`t1`.`a` AS `a`,`v`.`b` AS `b`,`v`.`c` AS `c` from `test`.`t1` join `test`.`v` where (`v`.`b` = `test`.`t1`.`a`)

Minimal optimizer_switch: derived_with_keys=on,extended_keys=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,extended_keys=on

# Test case:

SET optimizer_switch = 'derived_with_keys=on,extended_keys=on';

CREATE TABLE t1 ( a VARCHAR(1) );
INSERT INTO t1 VALUES ('j'),('v');

CREATE TABLE t2 ( b VARCHAR(1) );
INSERT INTO t2 VALUES ('j'),('v');

CREATE TABLE t3 ( c VARCHAR(1) );
INSERT INTO t2 VALUES ('m'),('n');

CREATE VIEW v
  AS SELECT DISTINCT * FROM t2 STRAIGHT_JOIN t3;

# Also reproducible with a subquery instead of a view

SELECT * FROM t1, v
 WHERE a = b;

[Igor Babaev (igorb-seattle)]

This bug was fixed by the patch for LP bug #914560. Added the test case for this bug into innodb_ext_key.test

[Elena Stepanova (elenst)]

Fix released with 5.5.21.