[MDEV-30248] Infinite sequence of recursive calls when processing embedded CTE - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Critical
Resolution: Fixed
Affects Version/s: 10.3(EOL), 10.4(EOL), 10.5, 10.6, 10.7(EOL), 10.8(EOL), 10.9(EOL), 10.10(EOL), 10.11
Fix Version/s: 10.11.2, 10.3.38, 10.4.28, 10.5.19, 10.6.12, 10.7.8, 10.8.7, 10.9.5, 10.10.3
Component/s: Optimizer - CTE
Labels:

Description

New regression caused by ~~MDEV-29361~~

CREATE TABLE x (c INT);

WITH x AS (((SELECT (WITH x AS (WITH x AS (SELECT 1 FROM x) SELECT 1) SELECT 1)))) SELECT 1;

Leads to:

10.11.2 c194db34d93d8d94bd52b17349063fa401e3f942 (Debug)
Core was generated by `/test/MD171222-mariadb-10.11.2-linux-x86_64-dbg/bin/mysqld --no-defaults --core'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x000055ec81a53b5e in st_select_lex_unit::set_unique_exclude (
this=0x149aa4015390) at /test/10.11_dbg/sql/sql_union.cc:2849
2849 {
[Current thread is 1 (Thread 0x149abfbfd700 (LWP 2438758))]
(gdb) bt
#0 0x000055ec81a53b5e in st_select_lex_unit::set_unique_exclude (this=0x149aa4015390) at /test/10.11_dbg/sql/sql_union.cc:2849
#1 0x000055ec81a53b93 in st_select_lex_unit::set_unique_exclude (this=<optimized out>) at /test/10.11_dbg/sql/sql_union.cc:2857
#2 0x000055ec81a53b93 in st_select_lex_unit::set_unique_exclude (this=<optimized out>) at /test/10.11_dbg/sql/sql_union.cc:2857
...
...
#992 0x000055ec81a53b93 in st_select_lex_unit::set_unique_exclude (this=<optimized out>) at /test/10.11_dbg/sql/sql_union.cc:2857
#993 0x000055ec81a53b93 in st_select_lex_unit::set_unique_exclude (this=<optimized out>) at /test/10.11_dbg/sql/sql_union.cc:2857

Bug confirmed present in:
MariaDB: 10.3.38 (dbg), 10.3.38 (opt), 10.4.28 (dbg), 10.4.28 (opt), 10.5.19 (dbg), 10.5.19 (opt), 10.6.12 (dbg), 10.6.12 (opt), 10.7.8 (dbg), 10.7.8 (opt), 10.8.7 (dbg), 10.8.7 (opt), 10.9.5 (dbg), 10.9.5 (opt), 10.10.3 (dbg), 10.10.3 (opt), 10.11.2 (dbg), 10.11.2 (opt)

Attachments

Issue Links

is caused by

MDEV-29361 Infinite recursive calls when detecting CTE dependencies

Closed

Activity

Ascending order - Click to sort in descending order

Roel Van de Paar added a comment - 2022-12-17 06:42

A hang can also be seen when using the following testcase:

CREATE TABLE x (c INT);

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

Leads to:

10.11.2 c194db34d93d8d94bd52b17349063fa401e3f942 (Debug)
10.11.2-dbg>SHOW FULL PROCESSLIST\G
************************* 1. row *************************
Id: 4
User: root
Host: localhost
db: test
Command: Query
Time: 17
State: starting
Info: WITH x AS (((SELECT (WITH x AS (WITH x AS (SELECT (x) FROM x UNION SELECT 1 AS x FROM x) SELECT 1) SELECT 1)))) SELECT 1
Progress: 0.000

Roel Van de Paar added a comment - 2022-12-17 06:42 A hang can also be seen when using the following testcase: CREATE TABLE x (c INT ); WITH x AS ((( SELECT ( WITH x AS ( WITH x AS ( SELECT (x) FROM x UNION SELECT 1 AS x FROM x) SELECT 1) SELECT 1)))) SELECT 1; Leads to: 10.11.2 c194db34d93d8d94bd52b17349063fa401e3f942 (Debug) 10.11.2-dbg>SHOW FULL PROCESSLIST\G *************************** 1. row *************************** Id: 4 User: root Host: localhost db: test Command: Query Time: 17 State: starting Info: WITH x AS (((SELECT (WITH x AS (WITH x AS (SELECT (x) FROM x UNION SELECT 1 AS x FROM x) SELECT 1) SELECT 1)))) SELECT 1 Progress: 0.000

Roel Van de Paar added a comment - 2022-12-17 06:51

I am adding two unsimplified testcases (one which was reduced by computer, then by hand to the above minimum), to test any patches with:

CREATE TABLE x ( x FLOAT ) ;

INSERT INTO x ( x ) VALUES ( 67 ) ;

UPDATE x SET x = -1 WHERE x = 33 ;

INSERT INTO x ( x ) VALUES ( -1 ) , ( 0 ) ;

WITH x AS ( WITH x AS ( WITH x AS ( SELECT ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT x FROM x AS x ) IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x WHERE x != 84 GROUP BY x ) AS x FROM x ) AS x WHERE x != 28 GROUP BY x ) ) SELECT x FROM ( SELECT x FROM x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT 1 IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) FROM ( SELECT 1 ) AS x GROUP BY 0 ) AS x FROM x ) AS x WHERE x != 28 GROUP BY x ) ;

SELECT 1 WHERE 1 IN ( SELECT 1 FROM ( SELECT 1 IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) AS x FROM ( SELECT 1 ) AS x ) AS x WHERE x = 1 GROUP BY x ) ;

CREATE TABLE x ( x FLOAT ) ;

WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT 1 FROM ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT 1 FROM ( SELECT 1 ) AS x NATURAL JOIN x AS x , x AS x NATURAL JOIN x ) AS x NATURAL JOIN x AS x WHERE x = 1 GROUP BY x ) AS x FROM x ) AS x WHERE x = 1 GROUP BY x ) ;

And

CREATE TABLE x ( x FLOAT ) ;

INSERT INTO x ( x ) VALUES ( 67 ) ;

UPDATE x SET x = -1 WHERE ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT 1 FROM ( WITH x AS ( WITH x AS ( WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT 1 WHERE x = 1 GROUP BY x ) AS x WHERE x != 28 GROUP BY x ) ) SELECT x % 52 != 50 FROM ( SELECT -128 , 51 , x FROM x WHERE x = 83 ) AS x GROUP BY x ) SELECT x FROM x ) AS x LIMIT 1 OFFSET 1 ) ;

INSERT INTO x ( x ) VALUES ( -1 ) , ( 0 ) ;

WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT DISTINCT x WHERE x != 84 GROUP BY x ) AS x FROM x ) AS x WHERE x != 28 GROUP BY x ) ;

SELECT 1 WHERE 1 IN ( SELECT 1 FROM ( SELECT 1 IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) AS x FROM ( SELECT 1 ) AS x ) AS x WHERE x = 1 GROUP BY x ) ;

CREATE TABLE x ( x FLOAT ) ;

WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT 1 FROM ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT 1 FROM ( SELECT 1 ) AS x NATURAL JOIN x AS x , x AS x NATURAL JOIN x ) AS x NATURAL JOIN x AS x WHERE x = 1 GROUP BY x ) AS x FROM x ) AS x WHERE x = 1 GROUP BY x ) ;

Roel Van de Paar added a comment - 2022-12-17 06:51 I am adding two unsimplified testcases (one which was reduced by computer, then by hand to the above minimum), to test any patches with: CREATE TABLE x ( x FLOAT ) ; INSERT INTO x ( x ) VALUES ( 67 ) ; UPDATE x SET x = -1 WHERE x = 33 ; INSERT INTO x ( x ) VALUES ( -1 ) , ( 0 ) ; WITH x AS ( WITH x AS ( WITH x AS ( SELECT ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT x FROM x AS x ) IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x WHERE x != 84 GROUP BY x ) AS x FROM x ) AS x WHERE x != 28 GROUP BY x ) ) SELECT x FROM ( SELECT x FROM x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT 1 IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) FROM ( SELECT 1 ) AS x GROUP BY 0 ) AS x FROM x ) AS x WHERE x != 28 GROUP BY x ) ; SELECT 1 WHERE 1 IN ( SELECT 1 FROM ( SELECT 1 IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) AS x FROM ( SELECT 1 ) AS x ) AS x WHERE x = 1 GROUP BY x ) ; CREATE TABLE x ( x FLOAT ) ; WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT 1 FROM ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT 1 FROM ( SELECT 1 ) AS x NATURAL JOIN x AS x , x AS x NATURAL JOIN x ) AS x NATURAL JOIN x AS x WHERE x = 1 GROUP BY x ) AS x FROM x ) AS x WHERE x = 1 GROUP BY x ) ; And CREATE TABLE x ( x FLOAT ) ; INSERT INTO x ( x ) VALUES ( 67 ) ; UPDATE x SET x = -1 WHERE ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT 1 FROM ( WITH x AS ( WITH x AS ( WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT 1 WHERE x = 1 GROUP BY x ) AS x WHERE x != 28 GROUP BY x ) ) SELECT x % 52 != 50 FROM ( SELECT -128 , 51 , x FROM x WHERE x = 83 ) AS x GROUP BY x ) SELECT x FROM x ) AS x LIMIT 1 OFFSET 1 ) ; INSERT INTO x ( x ) VALUES ( -1 ) , ( 0 ) ; WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT DISTINCT x WHERE x != 84 GROUP BY x ) AS x FROM x ) AS x WHERE x != 28 GROUP BY x ) ; SELECT 1 WHERE 1 IN ( SELECT 1 FROM ( SELECT 1 IN ( SELECT 1 FROM ( SELECT 1 ) AS x ) AS x FROM ( SELECT 1 ) AS x ) AS x WHERE x = 1 GROUP BY x ) ; CREATE TABLE x ( x FLOAT ) ; WITH x AS ( SELECT x FROM ( SELECT x FROM x GROUP BY x ) AS x ) SELECT x FROM x WHERE ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT x FROM ( SELECT x , ( SELECT x FROM x AS x LIMIT 1 OFFSET 1 ) IN ( SELECT 1 FROM ( WITH x AS ( SELECT 1 FROM ( SELECT * FROM x WHERE x = 1 ) AS x GROUP BY x ) SELECT 1 FROM ( SELECT 1 ) AS x NATURAL JOIN x AS x , x AS x NATURAL JOIN x ) AS x NATURAL JOIN x AS x WHERE x = 1 GROUP BY x ) AS x FROM x ) AS x WHERE x = 1 GROUP BY x ) ;

Igor Babaev (Inactive) added a comment - 2022-12-22 03:38 - edited

Processing of the following query also falls into an infinite loop:

WITH dt as (SELECT (WITH x AS (WITH x AS (SELECT a FROM x) SELECT 1 as b) SELECT b FROM x) as c) SELECT dt.c from dt

If there is no base table with name 'x' processing of the query should end up with the error message

ERROR 1146 (42S02): Table 'test.x' doesn't exist

Otherwise processing of the query should return:

MariaDB [test]> WITH dt as (SELECT (WITH x AS (WITH x AS (SELECT a FROM x) SELECT 1 as b) SELECT b FROM x) as c) SELECT dt.c from dt;

+------+

| c    |

+------+

|    1 |

+------+

Similar results are expected when processing the query:

WITH x as (SELECT (WITH x AS (WITH x AS (SELECT a FROM x) SELECT 1 as b) SELECT b FROM x) as c) SELECT x.c from x;

Igor Babaev (Inactive) added a comment - 2022-12-22 03:38 - edited Processing of the following query also falls into an infinite loop: WITH dt as ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x) SELECT 1 as b) SELECT b FROM x) as c) SELECT dt.c from dt If there is no base table with name 'x' processing of the query should end up with the error message ERROR 1146 (42S02): Table 'test.x' doesn't exist Otherwise processing of the query should return: MariaDB [test]> WITH dt as (SELECT (WITH x AS (WITH x AS (SELECT a FROM x) SELECT 1 as b) SELECT b FROM x) as c) SELECT dt.c from dt; +------+ | c | +------+ | 1 | +------+ Similar results are expected when processing the query: WITH x as ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x) SELECT 1 as b) SELECT b FROM x) as c) SELECT x.c from x;

Igor Babaev (Inactive) added a comment - 2022-12-22 03:49 - edited

After the following patch has been applied to the current 10.3 code the above queries do not cause any problems and return expected results:

diff --git a/sql/sql_cte.cc b/sql/sql_cte.cc

index d7e3eec..3453619 100644

--- a/sql/sql_cte.cc

+++ b/sql/sql_cte.cc

@@ -93,49 +93,6 @@ bool LEX::check_dependencies_in_with_clauses()

/**

   @brief

-    Resolve references to CTE in specification of hanging CTE

-  @details

-    A CTE to which there are no references in the query is called hanging CTE.

-    Although such CTE is not used for execution its specification must be

-    subject to context analysis. All errors concerning references to

-    non-existing tables or fields occurred in the specification must be

-    reported as well as all other errors caught at the prepare stage.

-    The specification of a hanging CTE might contain references to other

-    CTE outside of the specification and within it if the specification

-    contains a with clause. This function resolves all such references for

-    all hanging CTEs encountered in the processed query.

-  @retval

-    false   on success

-    true    on failure

-*/

-bool

-LEX::resolve_references_to_cte_in_hanging_cte()

-{

-  for (With_clause *with_clause= with_clauses_list;

-       with_clause; with_clause= with_clause->next_with_clause)

-  {

-    for (With_element *with_elem= with_clause->with_list.first;

-         with_elem; with_elem= with_elem->next)

-    {

-      if (!with_elem->is_referenced())

-      {

-        TABLE_LIST *first_tbl=

-                     with_elem->spec->first_select()->table_list.first;

-        TABLE_LIST **with_elem_end_pos= with_elem->head->tables_pos.end_pos;

-        if (first_tbl && resolve_references_to_cte(first_tbl, with_elem_end_pos))

-          return true;

-      }

-    }

-  }

-  return false;

-}

-/**

-  @brief

     Resolve table references to CTE from a sub-chain of table references

   @param tables      Points to the beginning of the sub-chain

@@ -279,8 +236,6 @@ LEX::check_cte_dependencies_and_resolve_references()

     return false;

   if (resolve_references_to_cte(query_tables, query_tables_last))

     return true;

-  if (resolve_references_to_cte_in_hanging_cte())

-    return true;

   return false;

@@ -454,6 +409,18 @@ With_element *With_clause::find_table_def(TABLE_LIST *table,

   return NULL;

+With_element *With_clause::find_with_element_by_spec(st_select_lex_unit *spec)

+{

+  for (With_element *with_elem= with_list.first;

+       with_elem;

+       with_elem= with_elem->next)

+  {

+    if (with_elem->spec == spec)

+      return with_elem;

+  }

+  return NULL;

+}

/**

   @brief

@@ -479,6 +446,7 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl,

                                              st_unit_ctxt_elem *ctxt)

   With_element *found= 0;

+  st_select_lex_unit *top_unit= 0;

   for (st_unit_ctxt_elem *unit_ctxt_elem= ctxt;

        unit_ctxt_elem;

        unit_ctxt_elem= unit_ctxt_elem->prev)

@@ -491,7 +459,10 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl,

*/

     if (with_clause)

-      found= with_clause->find_table_def(tbl, NULL);

+      With_element *barrier= 0;

+      if (top_unit && !with_clause->with_recursive)

+        barrier= with_clause->find_with_element_by_spec(top_unit);

+      found= with_clause->find_table_def(tbl, barrier);

       if (found)

         break;

@@ -504,6 +475,7 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl,

       if (!(unit_ctxt_elem= unit_ctxt_elem->prev))

         break;

+      top_unit= unit;

       unit= unit_ctxt_elem->unit;

     with_clause= unit->with_clause;

@@ -514,12 +486,16 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl,

*/

     if (with_clause)

+      With_element *barrier= 0;

+      if (top_unit && !with_clause->with_recursive)

+        barrier= with_clause->find_with_element_by_spec(top_unit);

       found= with_clause->find_table_def(tbl,

                                          with_clause->with_recursive ?

-			                 NULL : with_elem);

+			                 NULL : barrier);

       if (found)

 	break;

+    top_unit= unit;

   return found;

diff --git a/sql/sql_cte.h b/sql/sql_cte.h

index b270818..9bbe0c1 100644

--- a/sql/sql_cte.h

+++ b/sql/sql_cte.h

@@ -322,8 +322,6 @@ class With_element : public Sql_alloc

   friend

   bool LEX::resolve_references_to_cte(TABLE_LIST *tables,

                                       TABLE_LIST **tables_last);

-  friend

-  bool LEX::resolve_references_to_cte_in_hanging_cte();

};

 const uint max_number_of_elements_in_with_clause= sizeof(table_map)*8;

@@ -421,6 +419,8 @@ class With_clause : public Sql_alloc

   void move_anchors_ahead();

+  With_element *find_with_element_by_spec(st_select_lex_unit *spec);

   With_element *find_table_def(TABLE_LIST *table, With_element *barrier);

   With_element *find_table_def_in_with_clauses(TABLE_LIST *table);

@@ -435,9 +435,6 @@ class With_clause : public Sql_alloc

   friend

   bool LEX::check_dependencies_in_with_clauses();

-  friend

-  bool LEX::resolve_references_to_cte_in_hanging_cte();

};

 inline

diff --git a/sql/sql_lex.h b/sql/sql_lex.h

index bdc8b54..d594b8d 100644

--- a/sql/sql_lex.h

+++ b/sql/sql_lex.h

@@ -4053,7 +4053,6 @@ struct LEX: public Query_tables_list

   bool check_dependencies_in_with_clauses();

-  bool resolve_references_to_cte_in_hanging_cte();

   bool check_cte_dependencies_and_resolve_references();

   bool resolve_references_to_cte(TABLE_LIST *tables,

                                  TABLE_LIST **tables_last);

All tests from the 'main' test suite also finish as expected.
Note that with this patch the function LEX::resolve_references_to_cte_in_hanging_cte()
is not used anymore.

Igor Babaev (Inactive) added a comment - 2022-12-22 03:49 - edited After the following patch has been applied to the current 10.3 code the above queries do not cause any problems and return expected results: diff --git a/sql/sql_cte.cc b/sql/sql_cte.cc index d7e3eec..3453619 100644 --- a/sql/sql_cte.cc +++ b/sql/sql_cte.cc @@ -93,49 +93,6 @@ bool LEX::check_dependencies_in_with_clauses() /** @brief - Resolve references to CTE in specification of hanging CTE - - @details - A CTE to which there are no references in the query is called hanging CTE. - Although such CTE is not used for execution its specification must be - subject to context analysis. All errors concerning references to - non-existing tables or fields occurred in the specification must be - reported as well as all other errors caught at the prepare stage. - The specification of a hanging CTE might contain references to other - CTE outside of the specification and within it if the specification - contains a with clause. This function resolves all such references for - all hanging CTEs encountered in the processed query. - - @retval - false on success - true on failure -*/ - -bool -LEX::resolve_references_to_cte_in_hanging_cte() -{ - for (With_clause *with_clause= with_clauses_list; - with_clause; with_clause= with_clause->next_with_clause) - { - for (With_element *with_elem= with_clause->with_list.first; - with_elem; with_elem= with_elem->next) - { - if (!with_elem->is_referenced()) - { - TABLE_LIST *first_tbl= - with_elem->spec->first_select()->table_list.first; - TABLE_LIST **with_elem_end_pos= with_elem->head->tables_pos.end_pos; - if (first_tbl && resolve_references_to_cte(first_tbl, with_elem_end_pos)) - return true; - } - } - } - return false; -} - - -/** - @brief Resolve table references to CTE from a sub-chain of table references @param tables Points to the beginning of the sub-chain @@ -279,8 +236,6 @@ LEX::check_cte_dependencies_and_resolve_references() return false; if (resolve_references_to_cte(query_tables, query_tables_last)) return true; - if (resolve_references_to_cte_in_hanging_cte()) - return true; return false; } @@ -454,6 +409,18 @@ With_element *With_clause::find_table_def(TABLE_LIST *table, return NULL; } +With_element *With_clause::find_with_element_by_spec(st_select_lex_unit *spec) +{ + for (With_element *with_elem= with_list.first; + with_elem; + with_elem= with_elem->next) + { + if (with_elem->spec == spec) + return with_elem; + } + return NULL; +} + /** @brief @@ -479,6 +446,7 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl, st_unit_ctxt_elem *ctxt) { With_element *found= 0; + st_select_lex_unit *top_unit= 0; for (st_unit_ctxt_elem *unit_ctxt_elem= ctxt; unit_ctxt_elem; unit_ctxt_elem= unit_ctxt_elem->prev) @@ -491,7 +459,10 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl, */ if (with_clause) { - found= with_clause->find_table_def(tbl, NULL); + With_element *barrier= 0; + if (top_unit && !with_clause->with_recursive) + barrier= with_clause->find_with_element_by_spec(top_unit); + found= with_clause->find_table_def(tbl, barrier); if (found) break; } @@ -504,6 +475,7 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl, { if (!(unit_ctxt_elem= unit_ctxt_elem->prev)) break; + top_unit= unit; unit= unit_ctxt_elem->unit; } with_clause= unit->with_clause; @@ -514,12 +486,16 @@ With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl, */ if (with_clause) { + With_element *barrier= 0; + if (top_unit && !with_clause->with_recursive) + barrier= with_clause->find_with_element_by_spec(top_unit); found= with_clause->find_table_def(tbl, with_clause->with_recursive ? - NULL : with_elem); + NULL : barrier); if (found) break; } + top_unit= unit; } return found; } diff --git a/sql/sql_cte.h b/sql/sql_cte.h index b270818..9bbe0c1 100644 --- a/sql/sql_cte.h +++ b/sql/sql_cte.h @@ -322,8 +322,6 @@ class With_element : public Sql_alloc friend bool LEX::resolve_references_to_cte(TABLE_LIST *tables, TABLE_LIST **tables_last); - friend - bool LEX::resolve_references_to_cte_in_hanging_cte(); }; const uint max_number_of_elements_in_with_clause= sizeof(table_map)*8; @@ -421,6 +419,8 @@ class With_clause : public Sql_alloc void move_anchors_ahead(); + With_element *find_with_element_by_spec(st_select_lex_unit *spec); + With_element *find_table_def(TABLE_LIST *table, With_element *barrier); With_element *find_table_def_in_with_clauses(TABLE_LIST *table); @@ -435,9 +435,6 @@ class With_clause : public Sql_alloc friend bool LEX::check_dependencies_in_with_clauses(); - - friend - bool LEX::resolve_references_to_cte_in_hanging_cte(); }; inline diff --git a/sql/sql_lex.h b/sql/sql_lex.h index bdc8b54..d594b8d 100644 --- a/sql/sql_lex.h +++ b/sql/sql_lex.h @@ -4053,7 +4053,6 @@ struct LEX: public Query_tables_list } bool check_dependencies_in_with_clauses(); - bool resolve_references_to_cte_in_hanging_cte(); bool check_cte_dependencies_and_resolve_references(); bool resolve_references_to_cte(TABLE_LIST *tables, TABLE_LIST **tables_last); All tests from the 'main' test suite also finish as expected. Note that with this patch the function LEX::resolve_references_to_cte_in_hanging_cte() is not used anymore.

Igor Babaev (Inactive) added a comment - 2023-01-20 07:48 - edited

Let's figure out why we come to an infinite sequence recursive calls when resolving references to CTE for the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

      SELECT b FROM x AS r

    ) AS c

SELECT cte.c from cte;

Looking at the query we can easily see that the reference table x aliased with t cannot be resolved against any CTE comtained in the query because it is used within the defition of each CTE with name x and none of them is defined in a RECURSIVE with clause.
After the patch for the bug ~~MDEV-29361~~ we resolve references to CTEs used in CTE definitions starting from the definitions of the most inner with clauses. The most inner with clause for our query is:

WITH x AS (SELECT a FROM x AS t)

and we are going to resolve the reference to x aliased as t.
We call With_clause::check_dependencies() for this with clause and in this function we call With_element::check_dependencies_in_spec() for the specification of the with element x. . There we call With_element::check_dependencies_in_select() passing as parameters the first select of the definition unit SELECT_LEX::SELECT a FROM x AS t and of the

{NULL, spec} to this call where spec is the specification of the with element x SELECT_LEX_UNIT::SELECT a FROM x AS t'. The select belongs to a unit with attached with clause. So With_clause::find_table_def() is called for the with clause containing x AS (SELECT a FROM x AS t) and x as t is passed to it as the table reference and with element x AS (SELECT a FROM x) as passed as the barrier. The barrier is the first element of the with clause. So NULL is returned by the function. Then with the function With_element::check_dependencies_in_select() we call find_table_def_in_with_clauses() passing x as t and {NULL, spec}

to it. The function fails to resolve x as t. We return to the function With_clause::check_dependencies called for the with clause WITH x AS (SELECT a FROM x AS t). Note that the reference x as t has not been resolved so far.
Now we move to the call of With_clause::check_dependencies() for the with clause:

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

The only with element of this with clause is 'x AS (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)'.
We call With_element::check_dependencies_in_spec() for this with element and we call check_dependencies_in_select() for the select SELECT 1 AS b passing

{NULL, spec} where spec is the unit
'WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b'. The select SELECT 1 AS b does not contain any table references. So With_element::check_dependencies_in_unit() is called for the with element and the first inner unit SELECT a FROM x AS t is passed to it as parameter together {ctxt, unit}, where ctxt is pointer to {NULL, spec}

. The unit does not contain with clause attached to it, it contains only one select and With_element::check_dependencies_in_select() is called for it. Here find_table_def_in_with_clauses() is called for x as t again but now with

{ctxt, unit}

as parameter. 'unit' does not contain with clause attached to it. As it is a with element we consider the unit from

{NULL,spec}. It is 'select 1 AS b' there is a with clause attached to it. We call With_clause::find_table_def() passing x as t and with element with the spec
SELECT a AS a FROM x AS t
as the barrier. This is the only element in the with clause. So we return NULL. we return to LEX::check_dependencies_in_with_clauses() with x as t still unresolved.
Now we move to the with clause

WITH cte AS

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

      SELECT b FROM x AS r

    ) AS c

.
This with clause contains only one with element. With_element::check_dependencies_in_spec() is called for this element and then With_element::check_dependencies_in_select() is called for it with

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

      SELECT b FROM x AS r

    ) AS c

and {NULL,spec}

as parameters. With_element::check_dependencies_in_unit() called for the first inner unit of the above select and this is SELECT b FROM x AS r. A with clause is attached to it. With_element::check_dependencies_in_with_clause() is called for this with clause and then With_element::check_dependencies_in_unit() is called for the spec of the only with element of this with clause select 1 AS b. The with clause WITH x AS (SELECT a FROM x AS t) is attached to this unit. With_element::check_dependencies_in_unit() is called for the unit SELECT a FROM x AS t and then check_dependencies_in_select() is called for it. find_table_def_in_with_clauses() is called for x as t again.
Here the first unit that is considered is SELECT a FROM x AS t. No with clause is attached to it. We move to the unit select 1 AS b. There is a with clause attached to it. With_clause::find_table_def() is called with x as t and the with element with the spec SELECT a FROM x AS t as the barrier parameter. The function returns NULL. The unit is considered in the call of find_table_def_in_with_clauses(). The unit contains an attached with clause:

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

With_clause::find_table_def() is called with no barrier and x as t is resolved against CTE:

      x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

Resolution of x as t against the embedding CTE can lead to serious problems. This is not good.

Igor Babaev (Inactive) added a comment - 2023-01-20 07:48 - edited Let's figure out why we come to an infinite sequence recursive calls when resolving references to CTE for the query WITH cte AS ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) SELECT b FROM x AS r ) AS c ) SELECT cte.c from cte; Looking at the query we can easily see that the reference table x aliased with t cannot be resolved against any CTE comtained in the query because it is used within the defition of each CTE with name x and none of them is defined in a RECURSIVE with clause. After the patch for the bug MDEV-29361 we resolve references to CTEs used in CTE definitions starting from the definitions of the most inner with clauses. The most inner with clause for our query is: WITH x AS ( SELECT a FROM x AS t) and we are going to resolve the reference to x aliased as t. We call With_clause::check_dependencies() for this with clause and in this function we call With_element::check_dependencies_in_spec() for the specification of the with element x. . There we call With_element::check_dependencies_in_select() passing as parameters the first select of the definition unit SELECT_LEX::SELECT a FROM x AS t and of the {NULL, spec} to this call where spec is the specification of the with element x SELECT_LEX_UNIT::SELECT a FROM x AS t'. The select belongs to a unit with attached with clause. So With_clause::find_table_def() is called for the with clause containing x AS (SELECT a FROM x AS t) and x as t is passed to it as the table reference and with element x AS (SELECT a FROM x) as passed as the barrier. The barrier is the first element of the with clause. So NULL is returned by the function. Then with the function With_element::check_dependencies_in_select() we call find_table_def_in_with_clauses() passing x as t and {NULL, spec} to it. The function fails to resolve x as t. We return to the function With_clause::check_dependencies called for the with clause WITH x AS (SELECT a FROM x AS t). Note that the reference x as t has not been resolved so far. Now we move to the call of With_clause::check_dependencies() for the with clause: WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) The only with element of this with clause is 'x AS (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)'. We call With_element::check_dependencies_in_spec() for this with element and we call check_dependencies_in_select() for the select SELECT 1 AS b passing {NULL, spec} where spec is the unit 'WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b'. The select SELECT 1 AS b does not contain any table references. So With_element::check_dependencies_in_unit() is called for the with element and the first inner unit SELECT a FROM x AS t is passed to it as parameter together {ctxt, unit}, where ctxt is pointer to {NULL, spec} . The unit does not contain with clause attached to it, it contains only one select and With_element::check_dependencies_in_select() is called for it. Here find_table_def_in_with_clauses() is called for x as t again but now with {ctxt, unit} as parameter. 'unit' does not contain with clause attached to it. As it is a with element we consider the unit from {NULL,spec}. It is 'select 1 AS b' there is a with clause attached to it. We call With_clause::find_table_def() passing x as t and with element with the spec SELECT a AS a FROM x AS t as the barrier. This is the only element in the with clause. So we return NULL. we return to LEX::check_dependencies_in_with_clauses() with x as t still unresolved. Now we move to the with clause WITH cte AS ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) SELECT b FROM x AS r ) AS c ) . This with clause contains only one with element. With_element::check_dependencies_in_spec() is called for this element and then With_element::check_dependencies_in_select() is called for it with SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) SELECT b FROM x AS r ) AS c and {NULL,spec} as parameters. With_element::check_dependencies_in_unit() called for the first inner unit of the above select and this is SELECT b FROM x AS r. A with clause is attached to it. With_element::check_dependencies_in_with_clause() is called for this with clause and then With_element::check_dependencies_in_unit() is called for the spec of the only with element of this with clause select 1 AS b. The with clause WITH x AS (SELECT a FROM x AS t) is attached to this unit. With_element::check_dependencies_in_unit() is called for the unit SELECT a FROM x AS t and then check_dependencies_in_select() is called for it. find_table_def_in_with_clauses() is called for x as t again. Here the first unit that is considered is SELECT a FROM x AS t. No with clause is attached to it. We move to the unit select 1 AS b. There is a with clause attached to it. With_clause::find_table_def() is called with x as t and the with element with the spec SELECT a FROM x AS t as the barrier parameter. The function returns NULL. The unit is considered in the call of find_table_def_in_with_clauses(). The unit contains an attached with clause: WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) With_clause::find_table_def() is called with no barrier and x as t is resolved against CTE: x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) Resolution of x as t against the embedding CTE can lead to serious problems. This is not good.

Igor Babaev (Inactive) added a comment - 2023-01-21 04:59 - edited

As a result of the resolution of table reference x as t against the CTE

      x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

we have

SELECT a FROM x AS t

to be the inner unit for the unit

WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b

and vice versa.
For the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

      SELECT b FROM x AS r

    ) AS c

SELECT cte.c FROM cte;

it brings us to an infinite sequence of recursive calls in st_select_lex_unit::set_unique_exclude().
For the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH y AS (SELECT a FROM x AS t) SELECT b FROM t1)

      SELECT b FROM x AS r

    ) AS c

SELECT cte.c FROM cte;

where t1 is defined as

CREATE TABLE t1(b int);

it brings us to an infinite loop in the function st_select_lex::find_table_def_in_with_clauses().
For the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH y(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM y)

      SELECT b FROM x AS r

    ) AS c

SELECT cte.c FROM cte;

we have an infinite sequence of recursive call. Note that there is no hanging CTE in this query.
A problem of the same kind we have for the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH x(b) AS (SELECT a FROM x AS t LIMIT 1) SELECT b FROM x)

      SELECT b FROM x AS r

    ) AS c

SELECT cte.c FROM cte;

as well as for the query

WITH x AS

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

      SELECT b FROM x AS r

    ) AS c

SELECT x.c from x;

and for the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 2 AS b)

      SELECT r1.b FROM x AS r1, x AS r2 WHERE r1.b=r2.b

    ) AS c

SELECT cte.c from cte;

If we

DROP TABLE x;

then the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT 1 AS b)

      SELECT b FROM x AS r

    ) AS c

SELECT cte.c FROM cte;

returns the expected result

ERROR 1146 (42S02): Table 'test.x' doesn't exist

.
However in debugger we see that error message is reported for the occurrence of x as t in the cloned unit
SELECT a FROM x AS t that appeared when table resolution was performed for SELECT b FROM x AS r. This clone should not have appeared at all.
For the query

WITH cte AS

  SELECT

      WITH x AS

      (WITH x AS (SELECT a FROM x AS t) SELECT b FROM t1)

      SELECT b FROM x AS r

    ) AS c

SELECT cte.c FROM cte;

we still have an infinite loop in st_select_lex::find_table_def_in_with_clauses().

Igor Babaev (Inactive) added a comment - 2023-01-21 04:59 - edited As a result of the resolution of table reference x as t against the CTE x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) we have SELECT a FROM x AS t to be the inner unit for the unit WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b and vice versa. For the query WITH cte AS ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) SELECT b FROM x AS r ) AS c ) SELECT cte.c FROM cte; it brings us to an infinite sequence of recursive calls in st_select_lex_unit::set_unique_exclude(). For the query WITH cte AS ( SELECT ( WITH x AS ( WITH y AS ( SELECT a FROM x AS t) SELECT b FROM t1) SELECT b FROM x AS r ) AS c ) SELECT cte.c FROM cte; where t1 is defined as CREATE TABLE t1(b int ); it brings us to an infinite loop in the function st_select_lex::find_table_def_in_with_clauses(). For the query WITH cte AS ( SELECT ( WITH x AS ( WITH y(b) AS ( SELECT a FROM x AS t LIMIT 1) SELECT b FROM y) SELECT b FROM x AS r ) AS c ) SELECT cte.c FROM cte; we have an infinite sequence of recursive call. Note that there is no hanging CTE in this query. A problem of the same kind we have for the query WITH cte AS ( SELECT ( WITH x AS ( WITH x(b) AS ( SELECT a FROM x AS t LIMIT 1) SELECT b FROM x) SELECT b FROM x AS r ) AS c ) SELECT cte.c FROM cte; as well as for the query WITH x AS ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) SELECT b FROM x AS r ) AS c ) SELECT x.c from x; and for the query WITH cte AS ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 2 AS b) SELECT r1.b FROM x AS r1, x AS r2 WHERE r1.b=r2.b ) AS c ) SELECT cte.c from cte; If we DROP TABLE x; then the query WITH cte AS ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT 1 AS b) SELECT b FROM x AS r ) AS c ) SELECT cte.c FROM cte; returns the expected result ERROR 1146 (42S02): Table 'test.x' doesn't exist . However in debugger we see that error message is reported for the occurrence of x as t in the cloned unit SELECT a FROM x AS t that appeared when table resolution was performed for SELECT b FROM x AS r. This clone should not have appeared at all. For the query WITH cte AS ( SELECT ( WITH x AS ( WITH x AS ( SELECT a FROM x AS t) SELECT b FROM t1) SELECT b FROM x AS r ) AS c ) SELECT cte.c FROM cte; we still have an infinite loop in st_select_lex::find_table_def_in_with_clauses().

Oleksandr Byelkin added a comment - 2023-01-23 08:23

OK to push

Oleksandr Byelkin added a comment - 2023-01-23 08:23 OK to push

Igor Babaev (Inactive) added a comment - 2023-01-25 05:45

The patch above in one of the comments that uses the method With_clause::find_with_element_by_spec() is incorrect because there is no 1 to 1 relation between WITH elements and units created for the references to these elements.

Igor Babaev (Inactive) added a comment - 2023-01-25 05:45 The patch above in one of the comments that uses the method With_clause::find_with_element_by_spec() is incorrect because there is no 1 to 1 relation between WITH elements and units created for the references to these elements.

Igor Babaev (Inactive) added a comment - 2023-01-25 06:01

All not simplified test cases were checked with the fix.

Igor Babaev (Inactive) added a comment - 2023-01-25 06:01 All not simplified test cases were checked with the fix.

Igor Babaev (Inactive) added a comment - 2023-01-25 06:05

A fix for this bug was pushed into 10.3. It should be merged upstream as it is.

Igor Babaev (Inactive) added a comment - 2023-01-25 06:05 A fix for this bug was pushed into 10.3. It should be merged upstream as it is.

Roel Van de Paar added a comment - 2023-01-28 06:11

Impressive work igor, thank you.

Roel Van de Paar added a comment - 2023-01-28 06:11 Impressive work igor , thank you.

Roel Van de Paar added a comment - 2023-02-13 06:45

An additional testcase was observed to generate a slightly different stack. The issue looks to be fixed with the patch from this bug. Adding it for completeness. It looks very similar to a testcase by Igor provided earlier.

WITH x AS (((SELECT (WITH x AS (WITH x AS (SELECT 1 FROM x) SELECT 1) SELECT 1)))) SELECT 1;

SIGSEGV|st_select_lex::first_inner_unit|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude

SIGSEGV|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude

Roel Van de Paar added a comment - 2023-02-13 06:45 An additional testcase was observed to generate a slightly different stack. The issue looks to be fixed with the patch from this bug. Adding it for completeness. It looks very similar to a testcase by Igor provided earlier. WITH x AS ((( SELECT ( WITH x AS ( WITH x AS ( SELECT 1 FROM x) SELECT 1) SELECT 1)))) SELECT 1; SIGSEGV|st_select_lex::first_inner_unit|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude SIGSEGV|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude|st_select_lex_unit::set_unique_exclude

People

Assignee:: Igor Babaev (Inactive)

Reporter:: Roel Van de Paar

Votes:: 0 Vote for this issue

Watchers:: 5 Start watching this issue

Dates

Created:: 2022-12-17 06:41

Updated:: 2023-02-13 06:45

Resolved:: 2023-01-25 06:05

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server