[MDEV-32724] Segmentation fault due to Deep Recursion in table.cc and sql_lex.cc Created: 2023-11-07  Updated: 2024-01-27

Status: Confirmed
Project: MariaDB Server
Component/s: Optimizer - CTE, Server
Affects Version/s: 10.4, 10.5, 10.6, 10.9, 10.10, 10.11, 11.0, 11.1, 11.2, 11.3.0
Fix Version/s: 10.4, 10.5, 10.6, 10.11, 11.0, 11.1, 11.2

Type: Bug Priority: Critical
Reporter: Xin Wen Assignee: Igor Babaev
Resolution: Unresolved Votes: 0
Labels: None
Environment:

Ubuntu 20.04

Issue Links:
Relates
relates to MDEV-32723 Segmentation fault at /mariadb-11.3.0... Confirmed

 Description   

Run these queries in debug build:

CREATE TABLE x ( x INT ) ;
INSERT INTO x ( x ) VALUES ( 1 ) ;
UPDATE x SET x = 1 WHERE x = 1 ;
INSERT INTO x ( x ) VALUES ( 1 ) , ( 1 ) ;
WITH RECURSIVE x ( x ) AS ( WITH x ( x ) AS ( SELECT 1 EXCEPT SELECT x ^ 1 FROM x ) SELECT 1 FROM x AS x EXCEPT SELECT x + 1 FROM x ) SELECT - x , x FROM x ;

Will trigger Segmentation fault.
GDB info:
#0 0x00005555575ce774 in TABLE_LIST::handle_derived (this=0x0, lex=0x0, phases=0) at /home/wx/mariadb-11.3.0/sql/table.cc:9638
#1 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001e45f8, table_list=0x629000164f58, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#2 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001619e8, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#3 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x62900015e758, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#4 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001e45f8, table_list=0x62900015e758, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#5 0x0000555557143da1 in st_select_lex::handle_derived (this=0x62900015e2a8, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#6 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x629000164f58, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#7 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001e45f8, table_list=0x629000164f58, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#8 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001619e8, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#9 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x62900015e758, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#10 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001e45f8, table_list=0x62900015e758, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#11 0x0000555557143da1 in st_select_lex::handle_derived (this=0x62900015e2a8, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#12 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x629000164f58, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#13 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001e45f8, table_list=0x629000164f58, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#14 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001619e8, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#15 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x62900015e758, lex=0x62c0001e45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
.....................................................................
#8806 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001d45f8, table_list=0x629000136758, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#8807 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001362a8, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#8808 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x62900015ff58, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#8809 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001d45f8, table_list=0x62900015ff58, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#8810 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001399e8, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#8811 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x629000136758, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#8812 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001d45f8, table_list=0x629000136758, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#8813 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001362a8, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#8814 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x62900015ff58, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#8815 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001d45f8, table_list=0x62900015ff58, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#8816 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001399e8, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#8817 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x629000136758, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#8818 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001d45f8, table_list=0x629000136758, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#8819 0x0000555557143da1 in st_select_lex::handle_derived (this=0x6290001362a8, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#8820 0x00005555575ce8d7 in TABLE_LIST::handle_derived (this=0x629000137c48, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/table.cc:9648
#8821 0x000055555711d7d6 in LEX::handle_list_of_derived (this=0x62c0001d45f8, table_list=0x629000137c48, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.h:4579
#8822 0x0000555557143da1 in st_select_lex::handle_derived (this=0x629000137438, lex=0x62c0001d45f8, phases=2) at /home/wx/mariadb-11.3.0/sql/sql_lex.cc:4989
#8823 0x00005555572b563d in JOIN::prepare (this=0x629000160ba8, tables_init=0x629000137c48, conds_init=0x0, og_num=0, order_init=0x0, skip_order_by=false, group_init=0x0,
having_init=0x0, proc_param_init=0x0, select_lex_arg=0x629000137438, unit_arg=0x62c0001d46d8) at /home/wx/mariadb-11.3.0/sql/sql_select.cc:1439
#8824 0x00005555572dd916 in mysql_select (thd=0x62c0001d0288, tables=0x629000137c48, fields=..., conds=0x0, og_num=0, order=0x0, group=0x0, having=0x0, proc_param=0x0,
select_options=2164525824, result=0x62900013a238, unit=0x62c0001d46d8, select_lex=0x629000137438) at /home/wx/mariadb-11.3.0/sql/sql_select.cc:5224
#8825 0x00005555572ad18a in handle_select (thd=0x62c0001d0288, lex=0x62c0001d45f8, result=0x62900013a238, setup_tables_done_option=0) at /home/wx/mariadb-11.3.0/sql/sql_select.cc:628
#8826 0x00005555571ce583 in execute_sqlcom_select (thd=0x62c0001d0288, all_tables=0x629000137c48) at /home/wx/mariadb-11.3.0/sql/sql_parse.cc:6013
#8827 0x00005555571becf6 in mysql_execute_command (thd=0x62c0001d0288, is_called_from_prepared_stmt=false) at /home/wx/mariadb-11.3.0/sql/sql_parse.cc:3912
#8828 0x00005555571d95e2 in mysql_parse (thd=0x62c0001d0288,
rawbuf=0x6290000f52a8 "WITH RECURSIVE x ( x ) AS ( WITH x ( x ) AS ( SELECT 1 EXCEPT SELECT x ^ 1 FROM x ) SELECT 1 FROM x AS x EXCEPT SELECT x + 1 FROM x ) SELECT - x , x FROM x", length=155, parser_state=0x7fffd2e91870) at /home/wx/mariadb-11.3.0/sql/sql_parse.cc:7734
#8829 0x00005555571b1237 in dispatch_command (command=COM_QUERY, thd=0x62c0001d0288,
packet=0x6290000eb289 "WITH RECURSIVE x ( x ) AS ( WITH x ( x ) AS ( SELECT 1 EXCEPT SELECT x ^ 1 FROM x ) SELECT 1 FROM x AS x EXCEPT SELECT x + 1 FROM x ) SELECT - x , x FROM x", packet_length=155, blocking=true) at /home/wx/mariadb-11.3.0/sql/sql_parse.cc:1893
#8830 0x00005555571adf7c in do_command (thd=0x62c0001d0288, blocking=true) at /home/wx/mariadb-11.3.0/sql/sql_parse.cc:1406
#8831 0x000055555768e557 in do_handle_one_connection (connect=0x6110000447c8, put_in_cache=true) at /home/wx/mariadb-11.3.0/sql/sql_connect.cc:1445
#8832 0x000055555768deb4 in handle_one_connection (arg=0x6110000447c8) at /home/wx/mariadb-11.3.0/sql/sql_connect.cc:1347
#8833 0x00005555582fa350 in pfs_spawn_thread (arg=0x618000006508) at /home/wx/mariadb-11.3.0/storage/perfschema/pfs.cc:2201
#8834 0x00007ffff7115609 in start_thread () from /lib/x86_64-linux-gnu/libpthread.so.0
#8835 0x00007ffff6ce8133 in clone () from /lib/x86_64-linux-gnu/libc.so.6

 Comments   
Comment by HeShan [ 2023-12-12 ] 

 
 
CREATE TABLE x ( x INT ) ;
 
 
 
WITH RECURSIVE x ( x ) AS (
 
     WITH x ( x ) AS (  SELECT 1 FROM x ) 
        SELECT 1 FROM x  EXCEPT SELECT 1 FROM x )
 
SELECT x FROM x ;

Could you please confirm whether the simplification process we applied has been helpful for developers in diagnosing and addressing this issue?

Comment by Igor Babaev [ 2024-01-22 ]

The query 

WITH RECURSIVE x(a) AS
 
(WITH x AS (SELECT a FROM x) SELECT 1 FROM x UNION SELECT a FROM x)
 
SELECT a FROM x;

cannot be considered as a valid one because the specification of the top level recursive CTE does not have any anchor part.
A similar problem we see for the query

WITH RECURSIVE x(a) AS
 
(WITH x AS (SELECT a FROM x) SELECT 1 FROM x UNION SELECT a+1 FROM x WHERE a < 10)
 
SELECT a FROM x;

At the same time the query

WITH RECURSIVE x(a) AS
 
(WITH x AS (SELECT a FROM x) SELECT 1 UNION SELECT a+1 FROM x WHERE a < 10)
 
SELECT a FROM x;

could be executed, but it returns a bogus error message:

MariaDB [test]> WITH RECURSIVE x(a) AS
 
    -> (WITH x AS (SELECT a FROM x) SELECT 1 UNION SELECT a+1 FROM x WHERE a < 10)
 
    -> SELECT a FROM x;
 
ERROR 1054 (42S22): Unknown column 'a' in 'field list'

Comment by Igor Babaev [ 2024-01-26 ]

We see the same problem if we change the name of the embedded CTE and execute the query

WITH RECURSIVE x(a) AS
 
(WITH y AS (SELECT a FROM x) SELECT 1 FROM y UNION SELECT a+1 FROM y WHERE a < 10)
 
SELECT a FROM x;

We see the same problem if we change the name of the embedded CTE and execute the query

WITH RECURSIVE x(a) AS
 
(WITH y AS (SELECT a FROM x) SELECT 1 FROM y UNION SELECT a+1 FROM y WHERE a < 10)
 
SELECT a FROM x;

Let's execute the query

WITH RECURSIVE x(a) AS
 
(WITH y AS (SELECT a FROM x) SELECT 1 FROM y UNION SELECT a+1 FROM y r WHERE a < 10)
 
SELECT a FROM x r;

Let's check detection of anchors for CTE x.

  • "select 1 AS `1` from y" is correctly detected as not anchor
  • ""select a + 1 AS `a+1` from y t where a < 10" erroneously detected as anchor.

Note that there are two selects for CTE y, each with its own
with_internal_reference_map for reference to x.

Let's see how the query is processed at the prepare phase in debugger.

  • JOIN::prepare() is called for 'select a AS a from x r'
  • st_select_lex::handle_derived() is called for "select a AS a from x r" with parameter DT_PREPARE
  • TABLE_LIST::handle_derived is called for r
  • unit for derived r is 

    "with y as (select a AS a from x)select a + 1 AS `a+1` from y t where a < 10 union select 1 AS `1` from y"

  • as s is not a recursive reference st_select_lex::handle_derived() is called for 

    "select a + 1 AS `a+1` from y t where a < 10"

  • TABLE_LIST::handle_derived is called for 't'
  • unit for derived t is "select a AS a from x"
  • as t was not detected as recursive reference st_select_lex::handle_derived() is called for 

    "select a AS a from x"

  • TABLE_LIST::handle_derived is called for 'x'
  • unit for derived x is 

    "with y as (select a AS a from x)select a + 1 AS `a+1` from y t where a < 10 union select 1 AS `1` from y"

  • as x is not detected as a recursive reference st_select_lex::handle_derived() is called for 

    "select a + 1 AS `a+1` from y t where a < 10"

  • TABLE_LIST::handle_derived is called for 't'

Here we can see that we have entered a chain of infinite recursion calls.

Generated at Thu Feb 08 10:33:31 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.