[#MDEV-31130] INSERT-SELECT with many when/case/if conditions running forever

[MDEV-31130] INSERT-SELECT with many when/case/if conditions running forever Created: 2023-04-26 Updated: 2024-01-17
Status:	Stalled
Project:	MariaDB Server
Component/s:	None
Affects Version/s:	10.6.4, 10.3.38, 10.6.12
Fix Version/s:	10.4, 10.6

Type:

Bug

Priority:

Critical

Reporter:

suresh ramagiri

Assignee:

Oleksandr Byelkin

Resolution:

Unresolved

Votes:

Labels:

ddl

Attachments:

mdev31130.jpg

oracle_script.sql

Description

One of our customers migrated from MySQL to MariaDB 10.6.4 and their INSERT-SELECT query having many case/when/if conditions running forever.

Locally on the empty tables, can reproduce this situation, queries are getting stuck with "Init" and "Closing tables" state.

MariaDB [(none)]> show processlist;

+------+-----------------+-----------+------+---------+-------+------------------------+------------------------------------------------------------------------------------------------------+----------+

| Id   | User            | Host      | db   | Command | Time  | State                  | Info                                                                                                 | Progress |

+------+-----------------+-----------+------+---------+-------+------------------------+------------------------------------------------------------------------------------------------------+----------+

.....

|  255 | root            | localhost | mcc  | Query   |  9511 | closing tables         | insert into mcc.testoutplanreport_p1

select period,plant_code,rawline,finishedgood,status,w1status |    0.000 |

|  288 | root            | localhost | NULL | Query   |  8881 | init                   | select period,plant_code,rawline,finishedgood,status,w1status,DELQ,DEL_DSI,DELO

,WW1P1,WW1P1_DSI,WW1 |    0.000 |

.....

Comments

Comment by Rex Johnston [ 2023-04-27 ]

set optimizer_switch="derived_merge=off";

sidesteps the problem

Comment by Sergei Petrunia [ 2023-05-02 ]

As far as I understand, this means that name resolution was incorrect. In our SQL dialect, derived tables may not have outside references so it should not be possible to construct a recursive expression.

Comment by Sergei Petrunia [ 2023-05-10 ]

The testcase can be simplified further.
The following takes one minute to execute (too slow).
I've also renamed the fields at each level so it's easier to debug:

drop table if exists foo;

create table foo (

  f1 integer,

  f2 integer,

  f3 integer,

  f4 integer,

  f5 integer,

  f6 integer,

  f7 integer,

  f8 integer,

  f9 integer );

-- set optimizer_switch="derived_merge=off";

select

  case

    when s8 > s8 then s8

    when s8 > s8 then s8

    when s8 > s8 then s8

  end s9

from (

  select

    case

      when s7 > s7 then s7

      when s7 > s7 then s7

      when s7 > s7 then s7

    end s8

  from (

    select

      case

        when s6 > s6 then s6

        when s6 > s6 then s6

        when s6 > s6 then s6

      end s7

    from (

      select

        case

          when s5 > s5 then s5

          when s5 > s5 then s5

          when s5 > s5 then s5

        end s6

      from (

        select

          case

            when s4 > s4 then s4

            when s4 > s4 then s4

            when s4 > s4 then s4

          end s5

        from (

          select

            case

              when s3 > s3 then s3

              when s3 > s3 then s3

              when s3 > s3 then s3

            end s4

          from (

            select

              case

                when s2 > s2 then s2

                when s2 > s2 then s2

                when s2 > s2 then s2

              end s3

            from (

              select

                case

                  when s1 > s1 then s1

                  when s1 > s1 then s1

                  when s1 > s1 then s1

                end s2

              from (

                select

                  case

                    when f3 > f4 then f4

                    when f3 > f5 then f5

                    when f4 > f5 then f3

                  end s1

                 from foo )

              m8 )

            m7 )

          m6 )

        m5 )

      m4 )

    m3 )

  m2 )

m1;

Comment by Sergei Petrunia [ 2023-05-10 ]

Then, the select list for s7:

  case

     when s7 > s7 then s7

      when s7 > s7 then s7

      when s7 > s7 then s7

    end s8

has 9 pointers to the Item_func_case_searched object representing the s7:

Comment by Sergei Petrunia [ 2023-05-10 ]

... which is not a problem as such.
We get the problem when we do Item tree walking. Execution spends a lot of time walking the item tree:

  #0  0x0000555556273e3c in bitmap_set_bit (map=0x7fffa0033e68, bit=4) at /home/psergey/dev-git2/10.6/include/my_bitmap.h:98

  #1  0x0000555556276bd3 in Item_field::register_field_in_read_map (this=0x7fffa09a9db8, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.cc:893

  #2  0x0000555555d7e2e0 in Item::walk (this=0x7fffa09a9db8, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2118

  #3  0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09aa500, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #4  0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09aa490, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #5  0x000055555629a898 in Item_direct_view_ref::walk (this=0x7fffa0992ba0, processor=&virtual Item::register_field_in_read_map(void*), walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:6083

  #6  0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09a7f38, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #7  0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09a7ec8, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #8  0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09a8df0, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #9  0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09a8d80, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #10 0x000055555629a898 in Item_direct_view_ref::walk (this=0x7fffa0995000, processor=&virtual Item::register_field_in_read_map(void*), walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:6083

  #11 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09a76e0, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #12 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09a7670, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #13 0x000055555629a898 in Item_direct_view_ref::walk (this=0x7fffa0997330, processor=&virtual Item::register_field_in_read_map(void*), walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:6083

  #14 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09a3978, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #15 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09a3908, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #16 0x000055555629a898 in Item_direct_view_ref::walk (this=0x7fffa001ddf8, processor=&virtual Item::register_field_in_read_map(void*), walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:6083

  #17 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09a1968, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #18 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09a18f8, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #19 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09a2268, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #20 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09a21f8, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #21 0x000055555629a898 in Item_direct_view_ref::walk (this=0x7fffa0020c38, processor=&virtual Item::register_field_in_read_map(void*), walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:6083

  #22 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa09a0b58, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #23 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa09a0ae8, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #24 0x000055555629a898 in Item_direct_view_ref::walk (this=0x7fffa0022ec0, processor=&virtual Item::register_field_in_read_map(void*), walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:6083

  #25 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa001ae08, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #26 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa001ad98, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #27 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa001bcc0, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #28 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa001bc50, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #29 0x000055555629a898 in Item_direct_view_ref::walk (this=0x7fffa0024408, processor=&virtual Item::register_field_in_read_map(void*), walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:6083

  #30 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa0019cb0, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #31 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa0019c40, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #32 0x0000555555e1514b in Item_args::walk_args (this=0x7fffa001a5b0, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:2773

  #33 0x0000555555e1571a in Item_func_or_sum::walk (this=0x7fffa001a540, processor=&virtual table offset 944, walk_subquery=false, arg=0x0) at /home/psergey/dev-git2/10.6/sql/item.h:5476

  #34 0x0000555555e0b5ac in find_field_in_table_ref (thd=0x7fffa0000d78, table_list=0x7fffa098ffe0, name=0x7fffa0018410 "s8", length=2, item_name=0x7fffa0018410 "s8", db_name=0x0, table_name=0x0, ignored_tables=0x0, ref=0x7fffa00185b0, check_privileges=true, allow_rowid=true,            cached_field_index_ptr=0x7fffa0018500, register_tree_change=true, actual_table=0x7fffec955b50) at /home/psergey/dev-git2/10.6/sql/sql_base.cc:6264

  #35 0x0000555555e0bf2a in find_field_in_tables (thd=0x7fffa0000d78, item=0x7fffa0018418, first_table=0x7fffa098ffe0, last_table=0x0, ignored_tables=0x0, ref=0x7fffa00185b0, report_error=IGNORE_EXCEPT_NON_UNIQUE, check_privileges=true, register_tree_change=true) at /home/psergey/dev-   git2/10.6/sql/sql_base.cc:6520

  #36 0x00005555562879c6 in Item_field::fix_fields (this=0x7fffa0018418, thd=0x7fffa0000d78, reference=0x7fffa00185b0) at /home/psergey/dev-git2/10.6/sql/item.cc:6007

  #37 0x0000555555d8ad26 in Item::fix_fields_if_needed (this=0x7fffa0018418, thd=0x7fffa0000d78, ref=0x7fffa00185b0) at /home/psergey/dev-git2/10.6/sql/item.h:1147

  #38 0x00005555562df811 in Item_func::fix_fields (this=0x7fffa0018530, thd=0x7fffa0000d78, ref=0x7fffa0018f48) at /home/psergey/dev-git2/10.6/sql/item_func.cc:350

  #39 0x0000555555d8ad26 in Item::fix_fields_if_needed (this=0x7fffa0018530, thd=0x7fffa0000d78, ref=0x7fffa0018f48) at /home/psergey/dev-git2/10.6/sql/item.h:1147

  #40 0x00005555562df811 in Item_func::fix_fields (this=0x7fffa0018e30, thd=0x7fffa0000d78, ref=0x7fffa0018f80) at /home/psergey/dev-git2/10.6/sql/item_func.cc:350

  #41 0x00005555562ac4e3 in Item_func_case::fix_fields (this=0x7fffa0018e30, thd=0x7fffa0000d78, ref=0x7fffa0018f80) at /home/psergey/dev-git2/10.6/sql/item_cmpfunc.cc:3150

  #42 0x0000555555d8ad26 in Item::fix_fields_if_needed (this=0x7fffa0018e30, thd=0x7fffa0000d78, ref=0x7fffa0018f80) at /home/psergey/dev-git2/10.6/sql/item.h:1147

  #43 0x0000555555d8ad53 in Item::fix_fields_if_needed_for_scalar (this=0x7fffa0018e30, thd=0x7fffa0000d78, ref=0x7fffa0018f80) at /home/psergey/dev-git2/10.6/sql/item.h:1156

  #44 0x0000555555e0f127 in setup_fields (thd=0x7fffa0000d78, ref_pointer_array={m_array = 0x7fffa0028760, m_size = 199}, fields=@0x7fffa0017b38: {<base_list> = {<Sql_alloc> = {<No data fields>}, first = 0x7fffa0018f78, last = 0x7fffa0018f78, elements = 1}, <No data fields>},            column_usage=MARK_COLUMNS_READ, sum_func_list=0x7fffa0991268, pre_fix=0x7fffa0017b50, allow_sum_func=true) at /home/psergey/dev-git2/10.6/sql/sql_base.cc:7735

  #45 0x0000555555efe71a in JOIN::prepare (this=0x7fffa0990f08, tables_init=0x7fffa098ffe0, 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=0x7fffa0017880, unit_arg=0x7fffa00050e8) at /home/psergey/dev-  git2/10.6/sql/sql_select.cc:1437

  #46 0x0000555555f0be14 in mysql_select (thd=0x7fffa0000d78, tables=0x7fffa098ffe0, fields=@0x7fffa0017b38: {<base_list> = {<Sql_alloc> = {<No data fields>}, first = 0x7fffa0018f78, last = 0x7fffa0018f78, elements = 1}, <No data fields>}, conds=0x0, og_num=0, order=0x0, group=0x0,      having=0x0, proc_param=0x0, select_options=2147748608, result=0x7fffa09ae868, unit=0x7fffa00050e8, select_lex=0x7fffa0017880) at /home/psergey/dev-git2/10.6/sql/sql_select.cc:5046

As far as I understand, if one calls walk() for the Item object representing s9,

we will visit the Item object representing s8 9 times (as s9 has 9 pointers to s8)
we will visit the Item object representing s7 9^2 = 81 times (s8 has 9 pointers to s7)
and so forth

Rougly speaking, at depth-most level it's fanout ^ depth = 10^8 calls. That's why the query is slow.

Comment by Sergei Petrunia [ 2023-05-10 ]

An idea about fixing it:

An Item tree may have references to the same item only through Item_direct_view_ref objects. What if we manage to avoid walking to the same Item multiple times?

This can be done as easily as remembering "walk id" in THD and refusing to do the same walk again.

In class Item, add:

 ulonglong Item::last_walk_id= 0.

Before the walk call, set the id:

+             thd->last_walk_id=  current_time(); // or a per-THD counter. You get the idea

              it->walk(&Item::register_field_in_read_map, 0, 0);

When walking, do not walk the items we have already walked:

bool Item_direct_view_ref::walk(Item_processor processor, bool walk_subquery, void *arg)

+  if (last_walk_id == thd->current_walk_id)

+    return false;

   last_walk_id= thd->current_walk_id;

   return (*ref)->walk(processor, walk_subquery, arg) ||

          (this->*processor)(arg);

NOTE: Please do NOT code this until we've agreed to do it...

Comment by Sergei Petrunia [ 2023-05-10 ]

.. if all Item_direct_view_refs point to the same "translation table", perhaps we could remember the fact that the traversal was done in the translation table?

Comment by Sergei Petrunia [ 2023-05-10 ]

For the record:
latest mysql-8.0 seems to be just as slow.

PostgreSQL 13.7 died as it was killed by the kernel OOM killer:

PostgreSQL Out of memory: Killed process 3496772 (postgres) total-vm:53893380kB, anon-rss:28723976kB, file-rss:0kB, shmem-rss:268kB, UID:127 pgtables:105192kB oom_score_adj:0

Comment by Oleg Smirnov [ 2023-05-12 ]

oracle_script.sql
Tested this script on Oracle (attached one adapted for Oracle). After about 2 minutes of processing it throws out the error "FROM keyword not found where expected".

Comment by Oleksandr Byelkin [ 2023-10-24 ]

drop table if exists foo;

create table foo (

  f1 integer,

  f2 integer,

  f3 integer,

  f4 integer,

  f5 integer);

#set optimizer_switch="derived_merge=off";

#set @save_max_statement_time= @@max_statement_time;

#set max_statement_time= 10;

select

  case

    when s14 > s14 then s14

    when s14 > s14 then s14

    when s14 > s14 then s14

  end s15

from (

select

  case

    when s13 > s13 then s13

    when s13 > s13 then s13

    when s13 > s13 then s13

  end s14

from (

select

  case

    when s12 > s12 then s12

    when s12 > s12 then s12

    when s12 > s12 then s12

  end s13

from (

select

  case

    when s11 > s11 then s11

    when s11 > s11 then s11

    when s11 > s11 then s11

  end s12

from (

select

  case

    when s10 > s10 then s10

    when s10 > s10 then s10

    when s10 > s10 then s10

  end s11

from (

select

  case

    when s9 > s9 then s9

    when s9 > s9 then s9

    when s9 > s9 then s9

  end s10

from (

select

  case

    when s8 > s8 then s8

    when s8 > s8 then s8

    when s8 > s8 then s8

  end s9

from (

select

  case

    when s7 > s7 then s7

    when s7 > s7 then s7

    when s7 > s7 then s7

  end s8

from (

select

  case

    when s6 > s6 then s6

    when s6 > s6 then s6

    when s6 > s6 then s6

  end s7

from (

select

  case

    when s5 > s5 then s5

    when s5 > s5 then s5

    when s5 > s5 then s5

  end s6

from (

select

  case

    when s4 > s4 then s4

    when s4 > s4 then s4

    when s4 > s4 then s4

  end s5

from (

select

  case

    when s3 > s3 then s3

    when s3 > s3 then s3

    when s3 > s3 then s3

  end s4

from (

select

  case

    when s2 > s2 then s2

    when s2 > s2 then s2

    when s2 > s2 then s2

  end s3

from (

select

  case

    when s1 > s1 then s1

    when s1 > s1 then s1

    when s1 > s1 then s1

  end s2

from (

  select

    case

      when f3 > f4 then f4

      when f3 > f5 then f5

      when f4 > f5 then f3

    end s1

   from foo )

m8)

m7)

m6)

m5)

m4)

m3)

m2)

m1)

m0)

m_1)

m_2)

m_3)

m_4)

m_6;

#set max_statement_time= @save_max_statement_time;

drop table foo;

Comment by Oleksandr Byelkin [ 2024-01-02 ]

Interesting what a difference if all references would be different Items, it still will work through them?

Comment by Oleksandr Byelkin [ 2024-01-15 ]

Idea with automatic walk_id do not work, because then each walk looks like a separate walk.

There is 2 ideas:

1. Walk protection make switchable (for example 0 walk id mean do not use it) and switch it on and of from higher functions

2. Also remember processor and start new id only if processor changed (other way to make it automatic)

Comment by Oleksandr Byelkin [ 2024-01-16 ]

Prototype with second way did not work, because probably exclude important walking.

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

[MDEV-31130] INSERT-SELECT with many when/case/if conditions running forever Created: 2023-04-26 Updated: 2024-01-17