Valgrind warnings 'Invalid read' in subselect_engine::calc_const_tables with SELECT and IN subqueries, GROUP BY, HAVING, materialization+semijoin

[Elena Stepanova]

==16653== Invalid read of size 1
==16653== at 0x6867D7: subselect_engine::calc_const_tables(List<TABLE_LIST>&) (item_subselect.cc:3643)
==16653== by 0x686850: subselect_single_select_engine::upper_select_const_tables() (item_subselect.cc:3652)
==16653== by 0x67E7A0: Item_subselect::update_used_tables() (item_subselect.cc:786)
==16653== by 0x6034AA: Item_ref::update_used_tables() (item.cc:9153)
==16653== by 0x61D959: Item_func::update_used_tables() (item_func.cc:423)
==16653== by 0x779094: JOIN::exec() (sql_select.cc:2592)
==16653== by 0x77A30C: 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:2963)
==16653== by 0x770E14: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:286)
==16653== by 0x6FF3E8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5152)
==16653== by 0x6F64A5: mysql_execute_command(THD*) (sql_parse.cc:2285)
==16653== by 0x701DC3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6153)
==16653== by 0x6F3C43: dispatch_command(enum_server_command, THD*, char*, unsigned int) (sql_parse.cc:1228)
==16653== by 0x6F2F77: do_command(THD*) (sql_parse.cc:923)
==16653== by 0x6EFDC5: handle_one_connection (sql_connect.cc:1218)
==16653== by 0x58B6A4E: start_thread (in /lib64/libpthread-2.11.2.so)
==16653== by 0x651D82C: clone (in /lib64/libc-2.11.2.so)
==16653== Address 0xfbaf89f is 2,143 bytes inside a block of size 4,164 free'd
==16653== at 0x4C25F7B: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==16653== by 0xC4082F: _myfree (safemalloc.c:337)
==16653== by 0xC3FB13: free_root (my_alloc.c:366)
==16653== by 0x7983F0: free_tmp_table(THD*, st_table*) (sql_select.cc:15185)
==16653== by 0x6883B8: subselect_hash_sj_engine::cleanup() (item_subselect.cc:4474)
==16653== by 0x67CD65: Item_subselect::cleanup() (item_subselect.cc:130)
==16653== by 0x67CF40: Item_in_subselect::cleanup() (item_subselect.cc:167)
==16653== by 0x78BE1B: st_join_table::cleanup() (sql_select.cc:10077)
==16653== by 0x78C8C7: JOIN::cleanup(bool) (sql_select.cc:10383)
==16653== by 0x78C5C4: JOIN::join_free() (sql_select.cc:10303)
==16653== by 0x778A91: JOIN::exec() (sql_select.cc:2514)
==16653== by 0x77A30C: 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:2963)
==16653== by 0x770E14: handle_select(THD*, st_lex*, select_result*, unsigned long) (sql_select.cc:286)
==16653== by 0x6FF3E8: execute_sqlcom_select(THD*, TABLE_LIST*) (sql_parse.cc:5152)
==16653== by 0x6F64A5: mysql_execute_command(THD*) (sql_parse.cc:2285)
==16653== by 0x701DC3: mysql_parse(THD*, char*, unsigned int, char const**) (sql_parse.cc:6153)

bzr version-info
revision-id: <email address hidden>
date: 2012-05-21 19:37:46 +0500
revno: 3527

Also reproducible on maria/5.5 revno 3413.
Reproducible with MyISAM, Aria, InnoDB.

Minimal optimizer_switch:
materialization=on,semijoin=on

Full optimizer_switch (default):
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 with default optimizer_switch:

id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY <subquery3> const distinct_key distinct_key 8 const,const 1 100.00 Using temporary; Using filesort
1 PRIMARY t2 ALL NULL NULL NULL NULL 2 100.00 Using join buffer (flat, BNL join)
3 MATERIALIZED t1 ALL NULL NULL NULL NULL 2 100.00
2 SUBQUERY t1 ALL NULL NULL NULL NULL 2 100.00
Warnings:
Note 1003 select (select sum(`test`.`t1`.`a`) from `test`.`t1`) AS `t1sum`,`test`.`t2`.`b` AS `b` from <materialize> (select max(`test`.`t1`.`a`),min(`test`.`t1`.`a`) from `test`.`t1`) join `test`.`t2` where ((`<subquery3>`.`MIN(a)` = 1) and (`<subquery3>`.`MAX(a)` = 1)) group by `test`.`t2`.`b` having (`t1sum` <> 1)

# Test case:

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

CREATE TABLE t1 (a INT);
INSERT INTO t1 VALUES (1),(7);

CREATE TABLE t2 (b INT);
INSERT INTO t2 VALUES (4),(6);

SELECT ( SELECT SUM(a) FROM t1 ) AS t1sum, b
FROM t2
WHERE (1,1) IN ( SELECT MAX(a), MIN(a) FROM t1 )
GROUP BY b
HAVING t1sum <> 1;

# End of test case

[Sergey Petrunia (sergefp)]

The problem caused by the following:

When a JOIN is run with temporary-table-based grouping, it will:
   (i) Run the actual JOIN, piping its results to the temporary table
   (ii) Run JOIN::cleanup(), and then make_simple_join() to read from the temp.table.
   (iii) Run a "pseudo-join" which is a 1-table join which reads from temp.table.

right before the (iii) step, item->update_used_tables() call for all items in HAVING clause. In our particular case, the HAVING clause is:

  HAVING t1sum <> 1

where t1sum is from

  SELECT ( SELECT SUM(a) FROM t1a ) AS t1sum,

This causes us to arrive here:
  #0 subselect_engine::calc_const_tables (list=...) at item_subselect.cc:3646
  #1 0x000000000065c44f in subselect_single_select_engine::upper_select_const_tables (this=0x7ffefc00a698) at item_subselect.cc:3662
  #2 0x00000000006543f4 in Item_subselect::update_used_tables (this=0x7ffefc00a508) at item_subselect.cc:786
  #3 0x00000000005dadbf in Item_ref::update_used_tables (this=0x7ffefc00cb88) at item.cc:9153
  #4 0x00000000005f4ce8 in Item_func::update_used_tables (this=0x7ffefc00cd78) at item_func.cc:423
  #5 0x000000000074afa2 in JOIN::exec (this=0x7ffefc03fd58) at sql_select.cc:2592

subselect_engine::calc_const_tables() walks over upper query's leaf_tables. EXPLAIN for the upper query is:

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+--------------+-------------+-------+---------------+--------------+---------+-------------+------+------------------------------------+
| 1 | PRIMARY | <subquery3> | const | distinct_key | distinct_key | 8 | const,const | 1 | Using temporary; Using filesort |
| 1 | PRIMARY | t2 | ALL | NULL | NULL | NULL | NULL | 2 | Using join buffer (flat, BNL join) |

the problem here is that TABLE* for <subquery3> was a temporary table, and it has already been deleted on step (ii) mentioned above.

[Elena Stepanova (elenst)]

Fix released in 5.5.25 and will be in 5.3.8 when it is out