[MDEV-29567] Performance degradation with new default settings for optimizer in 10.10 Created: 2022-09-18  Updated: 2023-11-28

Status: Open
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.10
Fix Version/s: 10.11

Type: Bug Priority: Critical
Reporter: Igor Babaev Assignee: Sergei Petrunia
Resolution: Unresolved Votes: 0
Labels: None


 Description   

A performance degradation can be observed with new default setting for 'optimizer_prune_level' in 10.10 for the following simple query over the dbt3 tables:

select l_orderkey, l_linenumber, l_tax from lineitem
 
  where l_orderkey in (select o_orderkey from orders
 
                         where o_custkey in
 
                               (select c_custkey from customer
 
                                  where c_nationkey in
 
                                        (select n_nationkey from nation
 
                                           where n_name='PERU'))
 
                               and
 
                              o_orderDATE between '1992-06-30' and '1992-12-31')
 
        and
 
        (l_partkey, l_suppkey) in
 
        (select p_partkey, s_suppkey from part, supplier
 
           where p_retailprice between 901 and 1000 and
 
                 s_nationkey in (select n_nationkey from nation
 
                                   where n_name='PERU'));

The query was run on a Release build of the latest 10.10 for the the database created with these mtr commands

--disable_warnings
 
DROP DATABASE IF EXISTS dbt3_s001;
 
--enable_warnings
 
 
 
CREATE DATABASE dbt3_s001;
 
 
 
use dbt3_s001;
 
 
 
--disable_query_log
 
--disable_result_log
 
--disable_warnings
 
--source include/dbt3_s001.inc
 
--enable_warnings
 
--enable_result_log
 
--enable_query_log
 
 
 
create index i_n_name on nation(n_name);
 
analyze table nation;

The default setting for 'optimizer_prune_level' is 2 10.10 while before this version the default setting for this variable was 1.
The performance degradation for the reported query can be observed for MyISAM. For InnoDB we don't see such degradation for this particular query.
Here's what I got when running the above query for MyISAM (all time measurements were taken from ANALYZE stmt)

1. set optimizer_prune_level=default
 
  1st run: "r_total_time_ms": 5.942242744
 
  2nd run: "r_total_time_ms": 5.795177193
 
  3rd run: "r_total_time_ms": 5.734443905
 
2. set optimizer_prune_level=1
 
  1st run: "r_total_time_ms": 4.177749859
 
  2nd run: "r_total_time_ms": 3.995446738
 
  3rd run: "r_total_time_ms": 4.384639953
 
3. set optimizer_prune_level=0
 
  1st run: "r_total_time_ms": 4.269302585
 
  2nd run: "r_total_time_ms": 3.914398888
 
  3rd run: "r_total_time_ms": 3.921989294

With the above settings for optimizer_prune_level the optimizer choses the following execution plans:

1. set optimizer_prune_level=default
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index
 
condition
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    2
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  i_l_suppkey5dbt3_s001.supplier.s_suppkey    100     Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
1       PRIMARY orders  eq_ref|filter   PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY|i_o_orderdate   4|4     dbt3_s001.lineitem.l_orderkey       1 (7%)  Using where; Using rowid filter
 
1       PRIMARY customer        eq_ref  PRIMARY,i_c_nationkey   PRIMARY 4       dbt3_s001.orders.o_custkey      1       Using where
 
 
 
2. set optimizer_prune_level=1
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    2
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  i_l_suppkey5dbt3_s001.supplier.s_suppkey    100     Using where
 
1       PRIMARY orders  eq_ref|filter   PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY|i_o_orderdate   4|4     dbt3_s001.lineitem.l_orderkey       1 (7%)  Using where; Using rowid filter
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
1       PRIMARY customer        eq_ref  PRIMARY,i_c_nationkey   PRIMARY 4       dbt3_s001.orders.o_custkey      1       Using where
 
 
 
3. set optimizer_prune_level=0
 
 
 
 id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    2
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  i_l_suppkey5dbt3_s001.supplier.s_suppkey    100
 
1       PRIMARY orders  eq_ref|filter   PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY|i_o_orderdate   4|4     dbt3_s001.lineitem.l_orderkey       1 (7%)  Using where; Using rowid filter
 
1       PRIMARY customer        eq_ref  PRIMARY,i_c_nationkey   PRIMARY 4       dbt3_s001.orders.o_custkey      1       Using where
 
1       PRIMARY nation  eq_ref|filter   PRIMARY,i_n_name        PRIMARY|i_n_name        4|26    dbt3_s001.customer.c_nationkey  1 (4%)  Using where; Using rowid filter
 
1       PRIMARY part    ALL     PRIMARY NULL    NULL    NULL    200     Using where; Using join buffer (flat, BNL join)

We see that with different settings for optimizer_prune_level the optimizer chooses different join orders:
1. set optimizer_prune_level=default
nation, nation, supplier, lineitem, part, orders, customer
2. set optimizer_prune_level=1
nation, nation, supplier, lineitem, orders, part, customer
3. set optimizer_prune_level=0
nation, supplier, lineitem, orders, customer, nation, part

For InnoDB I got

1. set optimizer_prune_level=default
 
  1st run: "r_total_time_ms": 2.05392333
 
  2nd run: "r_total_time_ms": 2.169093801
 
  3rd run   "r_total_time_ms": 1.988759027
 
2. set optimizer_prune_level=1
 
  1st run: "r_total_time_ms": 1.904479043
 
  2nd run: "r_total_time_ms": 2.059541392
 
  3rd run: "r_total_time_ms": 1.961143374
 
3. set optimizer_prune_level=0
 
  1st run: "r_total_time_ms": 1.391450822
 
  2st run: "r_total_time_ms": 1.450423518
 
  3rd run: "r_total_time_ms": 1.565808954

For InnoDB with the above settings for optimiser_prune_level the optimizer chooses the following execution plans:

1. set optimizer_prune_level=default
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY customer        ref     PRIMARY,i_c_nationkey   i_c_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY orders  ref     PRIMARY,i_o_orderdate,i_o_custkey       i_o_custkey     5       dbt3_s001.customer.c_custkey    1       Using where
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  PRIMARY 4  dbt3_s001.orders.o_orderkey      1       Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
 
 
2. set optimizer_prune_level=1
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY customer        ref     PRIMARY,i_c_nationkey   i_c_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY orders  ref     PRIMARY,i_o_orderdate,i_o_custkey       i_o_custkey     5       dbt3_s001.customer.c_custkey    1       Using where
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  PRIMARY 4  dbt3_s001.orders.o_orderkey      1       Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
 
 
3. set optimizer_prune_level=0
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY customer        ref     PRIMARY,i_c_nationkey   i_c_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY orders  ref     PRIMARY,i_o_orderdate,i_o_custkey       i_o_custkey     5       dbt3_s001.customer.c_custkey    1       Using where
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  PRIMARY 4  dbt3_s001.orders.o_orderkey      1       Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY supplier        eq_ref  PRIMARY,i_s_nationkey   PRIMARY 4       dbt3_s001.lineitem.l_suppkey    1       Using where
 
analyze format=json select l_orderkey, l_linenumber, l_tax from lineitem

Here with different settings for optimizer_prune_level we see that the optimizer chooses such join orders:
1. set optimizer_prune_level=default
nation, supplier, nation, customer, orders, lineitem, part
2. set optimizer_prune_level=1
nation, supplier, nation, customer, orders, lineitem, part
3. set optimizer_prune_level=0
nation, customer, orders, lineitem, part, nation, supplier

Here for Innodb we don't see that the execution plans for settings of optimizer_prune_level to 2 (default) and 1 differ. However setting of this variable to 0 gives us a better plan.

 Comments   
Comment by Igor Babaev [ 2022-09-19 ]

Here are execution times, execution plans and chosen join orders with the setting

set optimizer_switch='rowid_filter=off'

First for MyISAM:

1. set optimizer_prune_level=default
 
  1st run: "r_total_time_ms": 6.8446722345
 
  2nd run: "r_total_time_ms": 7.083778008
 
  3rd run: "r_total_time_ms": 6.890859816
 
2. set optimizer_prune_level=1
 
  1st run: "r_total_time_ms": 6.746200502
 
  2nd run: "r_total_time_ms": 6.588075527
 
  3rd run: "r_total_time_ms": 6.428131537
 
3. set optimizer_prune_level=0
 
  1st run: "r_total_time_ms": 5.24554235
 
  2nd run: "r_total_time_ms": 5.304924817
 
  3rd run: "r_total_time_ms": 4.957518332


1. set optimizer_prune_level=default
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    2
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  i_l_suppkey5dbt3_s001.supplier.s_suppkey    100     Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
1       PRIMARY orders  eq_ref  PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY 4       dbt3_s001.lineitem.l_orderkey   1       Using where
 
1       PRIMARY customer        eq_ref  PRIMARY,i_c_nationkey   PRIMARY 4       dbt3_s001.orders.o_custkey      1       Using where
 
 
 
2. set optimizer_prune_level=1
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    2
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  i_l_suppkey5dbt3_s001.supplier.s_suppkey    100     Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
1       PRIMARY orders  eq_ref  PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY 4       dbt3_s001.lineitem.l_orderkey   1       Using where
 
1       PRIMARY customer        eq_ref  PRIMARY,i_c_nationkey   PRIMARY 4       dbt3_s001.orders.o_custkey      1       Using where
 
 
 
3. set optimizer_prune_level=0
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using index condition
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    2
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  i_l_suppkey5dbt3_s001.supplier.s_suppkey    100
 
1       PRIMARY orders  eq_ref  PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY 4       dbt3_s001.lineitem.l_orderkey   1       Using where
 
1       PRIMARY customer        eq_ref  PRIMARY,i_c_nationkey   PRIMARY 4       dbt3_s001.orders.o_custkey      1       Using where
 
1       PRIMARY nation  eq_ref  PRIMARY,i_n_name        PRIMARY 4       dbt3_s001.customer.c_nationkey  1       Using where
 
1       PRIMARY part    ALL     PRIMARY NULL    NULL    NULL    200     Using where; Using join buffer (flat, BNL join)

1. set optimizer_prune_level=default
nation, nation, supplier, lineitem, part, orders, customer
2. set optimizer_prune_level=1
nation, nation, supplier, lineitem, part, orders, customer
3. set optimizer_prune_level=0
nation, supplier, lineitem, orders, customer, nation, part

Here we see that with settings for optimizer_prune_level 2 or 1 the optimizer chooses the same execution plan. When optimizer_prune_level is set to 0 the chosen execution plan is different and it's better.

Let's move to InnoDB.

1. set optimizer_prune_level=default
 
  1st run: "r_total_time_ms": 1.939706979
 
  2nd run: "r_total_time_ms": 1.70148599
 
  3rd run   "r_total_time_ms": 1.733295023
 
2. set optimizer_prune_level=1
 
  1st run: "r_total_time_ms": 1.798289138
 
  2nd run: "r_total_time_ms": 1.893826221
 
  3rd run: "r_total_time_ms": 1.845377524
 
3. set optimizer_prune_level=0
 
  1st run: "r_total_time_ms": 1.329139495
 
  2st run: "r_total_time_ms": 1.354687984
 
  3rd run: "r_total_time_ms": 1.4000206


1. set optimizer_prune_level=default
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY customer        ref     PRIMARY,i_c_nationkey   i_c_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY orders  ref     PRIMARY,i_o_orderdate,i_o_custkey       i_o_custkey     5       dbt3_s001.customer.c_custkey    1       Using where
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  PRIMARY 4  dbt3_s001.orders.o_orderkey      1       Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
 
 
2. set optimizer_prune_level=1
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY supplier        ref     PRIMARY,i_s_nationkey   i_s_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY customer        ref     PRIMARY,i_c_nationkey   i_c_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY orders  ref     PRIMARY,i_o_orderdate,i_o_custkey       i_o_custkey     5       dbt3_s001.customer.c_custkey    1       Using where
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  PRIMARY 4  dbt3_s001.orders.o_orderkey      1       Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
 
 
3. set optimizer_prune_level=0
 
 
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY customer        ref     PRIMARY,i_c_nationkey   i_c_nationkey   5       dbt3_s001.nation.n_nationkey    1       Using index
 
1       PRIMARY orders  ref     PRIMARY,i_o_orderdate,i_o_custkey       i_o_custkey     5       dbt3_s001.customer.c_custkey    1       Using where
 
1       PRIMARY lineitem        ref     PRIMARY,i_l_suppkey_partkey,i_l_partkey,i_l_suppkey,i_l_orderkey,i_l_orderkey_quantity  PRIMARY 4  dbt3_s001.orders.o_orderkey      1       Using where
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
1       PRIMARY nation  ref     PRIMARY,i_n_name        i_n_name        26      const   1       Using where; Using index
 
1       PRIMARY supplier        eq_ref  PRIMARY,i_s_nationkey   PRIMARY 4       dbt3_s001.lineitem.l_suppkey    1       Using where

1. set optimizer_prune_level=default
nation, supplier, nation, customer, orders, lineitem, part
2. set optimizer_prune_level=1
nation, supplier, nation, customer, orders, lineitem, part
3. set optimizer_prune_level=0
nation, customer, orders, lineitem, part, nation, supplier

For InnoDB also with settings for optimizer_prune_level 2 or 1 the optimizer chooses the same execution plan. When optimizer_prune_level is set to 0 the chosen execution plan is different and it's better.

Comment by Igor Babaev [ 2022-09-20 ]

Pay attention to the difference of the plans for MyISAM with optimizer_prune_level 2 and 1:
optimizer_prune_level=2:

1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where
 
1       PRIMARY orders  eq_ref|filter   PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY|i_o_orderdate   4|4     dbt3_s001.lineitem.l_orderkey       1 (7%)  Using where; Using rowid filter

optimizer_prune_level=1

1       PRIMARY orders  eq_ref|filter   PRIMARY,i_o_orderdate,i_o_custkey       PRIMARY|i_o_orderdate   4|4     dbt3_s001.lineitem.l_orderkey       1 (7%)  Using where; Using rowid filter
 
1       PRIMARY part    eq_ref  PRIMARY PRIMARY 4       dbt3_s001.lineitem.l_partkey    1       Using where

It looks like something is wrong with eq_ref pruning.

Comment by Michael Widenius [ 2022-09-28 ]

optimizer_prune_level=2 means that we regard all eq_ref as equal and don't try different combinations of
other eq_ref tables when the first is found.
Higher prune levels means that we will speed up the greedy_optimizer at the cost of possible missing some plans. Usually these plans should be have a cost and thus performance close to the original,
so the performance win in the greedy_optimizer should compensate for the possible worse plans.

See check_if_edge_table().

It is possible to fix the above case by checking if there is any eq_ref table with a filter and in this case not regard the table as an edge table. This may however make the greedy optimizer part slower.

However, in the selectivity tree we calculate the number of accepted records (records_out) better than in the current 10.10 tree. One effect of this is likely to be that we will sort and thus consider eq_ref tables with filters before other eq_ref tables, which will solve this issue.
Should be tested as soon as we are done with the rebase of the selectivity tree on 10.11

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