100% CPU loop in find_field_in_tables on 2nd execution of a prepared statement

[Philip Stoev]

When after executing the following queries:

                    7 Query /* GenTest::Transform::ExecuteAsPreparedTwice */ PREPARE prep_stmt_12942 FROM ' SELECT table1 . `pk` AS field1 , table1 . `pk` AS field2 , table2 . `col_int` AS field3 , MIN( table1 . `pk` ) AS field4 FROM AA AS table1 LEFT JOIN D AS table2 ON table1 . `pk` = table2 . `col_int_key` RIGHT JOIN I AS table3 ON table1 . `col_int_key` = table3 . `col_int_key` WHERE ( table2 . `col_int` IS NULL OR table3 . `pk` IS NULL ) GROUP BY field1, field2, field3 ORDER BY field1, field2, field3, field4 LIMIT 2 '
                    7 Prepare SELECT table1 . `pk` AS field1 , table1 . `pk` AS field2 , table2 . `col_int` AS field3 , MIN( table1 . `pk` ) AS field4 FROM AA AS table1 LEFT JOIN D AS table2 ON table1 . `pk` = table2 . `col_int_key` RIGHT JOIN I AS table3 ON table1 . `col_int_key` = table3 . `col_int_key` WHERE ( table2 . `col_int` IS NULL OR table3 . `pk` IS NULL ) GROUP BY field1, field2, field3 ORDER BY field1, field2, field3, field4 LIMIT 2
                    7 Query EXECUTE prep_stmt_12942 /* TRANSFORM_OUTCOME_UNORDERED_MATCH */
                    7 Execute SELECT table1 . `pk` AS field1 , table1 . `pk` AS field2 , table2 . `col_int` AS field3 , MIN( table1 . `pk` ) AS field4 FROM AA AS table1 LEFT JOIN D AS table2 ON table1 . `pk` = table2 . `col_int_key` RIGHT JOIN I AS table3 ON table1 . `col_int_key` = table3 . `col_int_key` WHERE ( table2 . `col_int` IS NULL OR table3 . `pk` IS NULL ) GROUP BY field1, field2, field3 ORDER BY field1, field2, field3, field4 LIMIT 2
                    7 Query EXECUTE prep_stmt_12942 /* TRANSFORM_OUTCOME_UNORDERED_MATCH */

the server entered into a 100% CPU loop with the following backtrace:

#0 find_field_in_tables (thd=0xadf6e90, item=0x99be4980, first_table=0xaec871e0, last_table=0x0, ref=0x9a0dc24c, report_error=IGNORE_ERRORS,
    check_privileges=true, register_tree_change=false) at sql_base.cc:6373
#1 0x08327d2b in find_order_in_list (thd=0xadf6e90, ref_pointer_array=0x999a8fc0, tables=0xaec871e0, order=0x99be4a30, fields=..., all_fields=...,
    is_group_field=true) at sql_select.cc:16413
#2 0x0832803d in setup_group (thd=0xadf6e90, ref_pointer_array=0x999a8fc0, tables=0xaec871e0, fields=..., all_fields=..., order=0x99be4a30,
    hidden_group_fields=0x9960840f) at sql_select.cc:16549
#3 0x08331816 in setup_without_group (thd=0xadf6e90, ref_pointer_array=0x999a8fc0, tables=0xaec871e0, leaves=0xaec871e0, fields=..., all_fields=...,
    conds=0x996084c0, order=0x9993d3c8, group=0x99be4a30, hidden_group_fields=0x9960840f) at sql_select.cc:450
#4 0x082fe3f7 in JOIN::prepare (this=0x996036c0, rref_pointer_array=0x9993cb88, tables_init=0xaec871e0, wild_num=0, conds_init=0xaecfac18, og_num=7,
    order_init=0x9993d3c8, group_init=0x99be4a30, having_init=0x0, proc_param_init=0x0, select_lex_arg=0x9993ca6c, unit_arg=0x9993c7cc) at sql_select.cc:521
#5 0x08305569 in mysql_select (thd=0xadf6e90, rref_pointer_array=0x9993cb88, tables=0xaec871e0, wild_num=0, fields=..., conds=0xaecfac18, og_num=7,
    order=0x9993d3c8, group=0x99be4a30, having=0x0, proc_param=0x0, select_options=2416200192, result=0x99917df8, unit=0x9993c7cc, select_lex=0x9993ca6c)
    at sql_select.cc:2534
#6 0x082fdbff in handle_select (thd=0xadf6e90, lex=0x9993c770, result=0x99917df8, setup_tables_done_option=0) at sql_select.cc:276
#7 0x0829c1a4 in execute_sqlcom_select (thd=0xadf6e90, all_tables=0xaec871e0) at sql_parse.cc:5081
#8 0x08292b7c in mysql_execute_command (thd=0xadf6e90) at sql_parse.cc:2265
#9 0x08344bcb in Prepared_statement::execute (this=0x99be46a8, expanded_query=0x9a0dd410, open_cursor=false) at sql_prepare.cc:3588
#10 0x083440ca in Prepared_statement::execute_loop (this=0x99be46a8, expanded_query=0x9a0dd410, open_cursor=false, packet=0x0, packet_end=0x0)
    at sql_prepare.cc:3263
#11 0x08342ab6 in mysql_sql_stmt_execute (thd=0xadf6e90) at sql_prepare.cc:2533
#12 0x08292ba6 in mysql_execute_command (thd=0xadf6e90) at sql_parse.cc:2274
#13 0x0829e365 in mysql_parse (thd=0xadf6e90, inBuf=0x99a896d8 "EXECUTE prep_stmt_12942 /* TRANSFORM_OUTCOME_UNORDERED_MATCH */", length=63,
    found_semicolon=0x9a0de230) at sql_parse.cc:6027
#14 0x08290632 in dispatch_command (command=COM_QUERY, thd=0xadf6e90, packet=0xadfd1e9 "EXECUTE prep_stmt_12942 /* TRANSFORM_OUTCOME_UNORDERED_MATCH */",
    packet_length=63) at sql_parse.cc:1184
#15 0x0828fb20 in do_command (thd=0xadf6e90) at sql_parse.cc:890
#16 0x0828cb58 in handle_one_connection (arg=0xadf6e90) at sql_connect.cc:1153
#17 0x00bea919 in start_thread () from /lib/libpthread.so.0
#18 0x00b2ccbe in clone () from /lib/libc.so.6

bzr version-info:

revision-id: <email address hidden>
date: 2010-08-19 19:52:58 +0200
build-date: 2010-08-31 15:01:03 +0300
revno: 2821
branch-nick: maria-5.3-dsmrr-cpk

[Philip Stoev (pstoev-askmonty)]

This bug is also present in maria-5.1 and mysql-next-mr, so appears to be a legacy issue around the second execution of a prepared statement:

Test case:

CREATE TABLE `AA` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int_key` int(11) DEFAULT NULL,
  `col_int` int(11) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_int_key` (`col_int_key`)
) ENGINE=MyISAM AUTO_INCREMENT=25 DEFAULT CHARSET=latin1;
INSERT INTO `AA` VALUES (1,6,2);
INSERT INTO `AA` VALUES (2,9,0);
INSERT INTO `AA` VALUES (3,-1240072192,2);
INSERT INTO `AA` VALUES (4,-221380608,-390332416);
INSERT INTO `AA` VALUES (5,255328256,9);
INSERT INTO `AA` VALUES (6,1167392768,-1272053760);
INSERT INTO `AA` VALUES (7,3,-125960192);
INSERT INTO `AA` VALUES (8,-950403072,9);
INSERT INTO `AA` VALUES (9,2,-1546649600);
INSERT INTO `AA` VALUES (10,23789568,8);
INSERT INTO `AA` VALUES (11,8,3);
INSERT INTO `AA` VALUES (12,-1638400000,5);
INSERT INTO `AA` VALUES (13,-245235712,1);
INSERT INTO `AA` VALUES (14,5,1200160768);
INSERT INTO `AA` VALUES (15,4,-1131675648);
INSERT INTO `AA` VALUES (16,3,6);
INSERT INTO `AA` VALUES (17,6,-1137836032);
INSERT INTO `AA` VALUES (18,1114701824,4);
INSERT INTO `AA` VALUES (19,27721728,-1256194048);
INSERT INTO `AA` VALUES (20,-644415488,1646657536);
INSERT INTO `AA` VALUES (21,-1060896768,8);
INSERT INTO `AA` VALUES (22,-1074724864,1298071552);
INSERT INTO `AA` VALUES (23,-1069547520,3);
INSERT INTO `AA` VALUES (24,3,569573376);
CREATE TABLE `D` (
  `col_int` int(11) DEFAULT NULL,
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int_key` int(11) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_int_key` (`col_int_key`)
) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=latin1;
INSERT INTO `D` VALUES (6,1,-506134528);
CREATE TABLE `I` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int` int(11) DEFAULT NULL,
  `col_int_key` int(11) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_int_key` (`col_int_key`)
) ENGINE=MyISAM AUTO_INCREMENT=7 DEFAULT CHARSET=latin1;
INSERT INTO `I` VALUES (1,2037514240,-971046912);
INSERT INTO `I` VALUES (2,819331072,7);
INSERT INTO `I` VALUES (3,-2099249152,-1953824768);
INSERT INTO `I` VALUES (4,-400621568,8);
INSERT INTO `I` VALUES (5,-1273102336,-1452474368);
INSERT INTO `I` VALUES (6,7,-111607808);

PREPARE st1 FROM 'SELECT table1 . `pk` AS field1 , table1 .`pk` AS field2 , table2 . `col_int` AS field3 , MIN( table1 . `pk` ) AS field4
FROM AA AS table1 LEFT JOIN D AS table2 ON table1 . `pk` = table2 . `col_int_key` RIGHT JOIN I AS table3 ON table1 . `col_int_key` = table3 . `col_int_key`
WHERE ( table2 . `col_int` IS NULL OR table3 . `pk` IS NULL )
GROUP BY field1, field2, field3
ORDER BY field1, field2, field3, field4
LIMIT 2';

EXECUTE st1;
EXECUTE st1;

[Philip Stoev (pstoev-askmonty)]

Asssigned to Sanja since it involves GROUP BY / ORDER BY

[Oleksandr "Sanja" Byelkin (sanja-byelkin)]

I can't repeat this bug any more.

[Oleksandr "Sanja" Byelkin (sanja-byelkin)]

EXECUTE st1;
field1 field2 field3 field4
NULL NULL NULL NULL
11 11 NULL 11
EXECUTE st1;
field1 field2 field3 field4
NULL NULL NULL NULL
11 11 NULL 11
EXECUTE st1;
field1 field2 field3 field4
NULL NULL NULL NULL
11 11 NULL 11
drop table AA,D,I;

[Philip Stoev (pstoev-askmonty)]

A new, unsimplified test case.

[Oleksandr "Sanja" Byelkin (sanja-byelkin)]

The problem is that on the first execution simplify_joins() in the try to flatten joins makes looped list of tables via next_name_resolution_table: table 'D' with alias 'alias5' refers table 'D' with alias1 (the very beginning of the list).

[Oleksandr "Sanja" Byelkin (sanja-byelkin)]

I am not sure that it is the same bug, but trying to simplify above problem I got this test case with crash:

create table t1 (a int, b int);
insert into t1 values (1,1),(2,2);
create table t2 (a int, b int);
insert into t2 values (1,1),(2,2);

select t1.b, t2.b from t1 right join t2 on (t2.a=t1.a) where t1.a > 5;

drop table t1, t2;

[Oleksandr "Sanja" Byelkin (sanja-byelkin)]

above reported as https://bugs.launchpad.net/maria/+bug/965950

[Oleksandr "Sanja" Byelkin (sanja-byelkin)]

It is the query for better understanding it (the query is the same):

prepare st1 from 'SELECT alias1 . `pk` AS field1
  FROM
    D AS alias1 LEFT OUTER JOIN
    D AS alias2 ON alias1 . `col_int_key` = alias2 . `pk` RIGHT OUTER JOIN
    EE AS alias3 LEFT JOIN
    G AS alias4 ON alias3 . `col_varchar_10_latin1_key` = alias4 . `col_varchar_10_utf8` LEFT JOIN
    D AS alias5 ON alias3 . `col_varchar_10_utf8_key` = alias5 . `col_varchar_10_latin1` ON alias2 . `col_int_key` = alias3 . `pk` LEFT JOIN
    H AS alias6 ON alias5 . `col_int` = alias6 . `col_int_key` LEFT JOIN
    BB AS alias7 RIGHT JOIN
    CC AS alias8 ON alias7 . `col_int_key` = alias8 . `col_int_key` LEFT JOIN
    GG AS alias9 ON alias7 . `col_varchar_1024_latin1` = alias9 . `col_varchar_1024_utf8_key` ON alias4 . `col_varchar_1024_latin1` = alias8 . `col_varchar_1024_utf8`
  WHERE alias9 . `col_int_key` >= alias7 . `pk`
  GROUP BY field1
  HAVING field1 > 6
  ORDER BY field1
  LIMIT 2 OFFSET 3';

[Oleksandr "Sanja" Byelkin (sanja-byelkin)]

To catch it in debugger set breakpoint on mysql_sql_stmt_execute then mysql_execute_command and then watchpoint on changing next_name_resolution_table of table with alias5, it will be place where the list looped.

[Timour Katchaounov (timour)]

Checked all test cases above with
- mariadb 5.1, 5.2, 5.5
- mysql 5.5
and couldn't reproduce the bug.

[Timour Katchaounov (timour)]

The bug has been fixed by the following patch:

                revno: 2661.806.1
                committer: Martin Hansson <email address hidden>
                branch nick: mysql-5.1-security
                timestamp: Tue 2012-02-07 14:16:09 +0100
                message:
                  Bug #11765810 58813: SERVER THREAD HANGS WHEN JOIN + WHERE + GROUP BY
                  IS EXECUTED TWICE FROM P

                  This bug is a duplicate of bug 12567331, which was pushed to the
                  optimizer backporting tree on 2011-06-11. This is just a back-port of
                  the fix. Both test cases are included as they differ somewhat.