[MDEV-21992] 10.5-monty tree: queries in innodb_ext_keys use sub-optimal plan with rowid filter Created: 2020-03-21  Updated: 2020-03-31  Resolved: 2020-03-31

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Fix Version/s: N/A

Type: Task Priority: Major
Reporter: Sergei Petrunia Assignee: Sergei Petrunia
Resolution: Done Votes: 0
Labels: None


 Description   

This query uses an apparently sub-optimal query plan with rowid-filter:

explain
 
select count(*) from lineitem where l_orderkey=130 and l_shipdate='1992-07-01';
 
id      select_type     table   type    possible_keys   key     key_len ref     rows    Extra
 
1       SIMPLE  lineitem        ref|filter      PRIMARY,i_l_shipdate,i_l_orderkey,i_l_orderkey_quantity i_l_orderkey|i_l_shipdate       4|8     const   5 (0%)  Using where; Using rowid filter

Reasoning for why it is suboptimal:

Table keys:

CREATE TABLE lineitem (
 
  ...
 
  PRIMARY KEY (l_orderkey,l_linenumber),
 
  KEY i_l_shipdate (l_shipDATE),
 
  KEY i_l_orderkey (l_orderkey),
 
  ...
 
);


select count(*) from lineitem where l_orderkey=130 and l_shipdate='1992-07-01';

Note that due to extended keys, the indexes actually are:

KEY i_l_orderkey (l_orderkey, l_linenumber )
KEY i_l_shipdate (l_shipDATE, l_orderkey, l_linenumber)

i_l_shipdate is covering for the query.

Now, think of two plans:

Plan-A.
use an index-only range scan on i_l_shipdate, pass the rows to output

Plan-B.
Use an index-only scan on i_l_shipdate, build the rowid filter $FILTER
Use scan on i_l_orderkey with $FILTER.

The optimizer picks plan B, while plan A is obviously cheaper.

Relevant parts of the optimizer trace:

         "analyzing_range_alternatives": {
 
           "range_scan_alternatives": [
 
             ...


             {
 
               "index": "i_l_shipdate",
 
               "ranges": [
 
                 "(1992-07-01,130) <= (l_shipDATE,l_orderkey) <= (1992-07-01,130)"
 
               ],
 
               "rowid_ordered": true,
 
               "using_mrr": false,
 
               "index_only": true,
 
               "rows": 1,
 
               "cost": 0.3251,
 
               "chosen": true
 
             },


             {
 
               "index": "i_l_orderkey",
 
               "ranges": ["(130) <= (l_orderkey) <= (130)"],
 
               "rowid_ordered": true,
 
               "using_mrr": false,
 
               "index_only": false,
 
               "rows": 5,
 
               "cost": 6.1257,
 
               "chosen": false,
 
               "cause": "cost"
 
             },

No issues so far. 

            "best_access_path": {
 
                {
 
                  "access_type": "ref",
 
                  "index": "i_l_shipdate",
 
                  "used_range_estimates": true,
 
                  "rows": 1,
 
                  "cost": 1.0001,
 
                  "chosen": true
 
                },

Here, the #rows estimate was reused from the range access, but the cost is
different. Denote this as "I_L_SHIPDATE-MISMATCH".

                 {
 
                   "access_type": "ref",
 
                   "index": "i_l_orderkey",
 
                   "used_range_estimates": true,
 
                   "rows": 5,
 
                   "cost": 0.1308,
 
                   "chosen": true
 
                 },

(Here the cost is also different from the one we got for range access, but here
the cost takes into account using the rowid filter (which reduces the cost)
(TODO: use of rowid filter should be shown in the trace!)

 Comments   
Comment by Sergei Petrunia [ 2020-03-21 ]

Studying the I_L_SHIPDATE-MISMATCH, the range access part:

The range estimate number is obtained here:

(gdb) wher
 
  #0  handler::keyread_time (this=0x7fffbc98ca70, index=1, ranges=0, rows=1) at /home/psergey/dev-git2/10.5/sql/handler.cc:2779
 
  #1  0x0000555555ffc0ed in handler::multi_range_read_info_const (this=0x7fffbc98ca70, keyno=1, seq=0x7fffeab64070, seq_init_param=0x7fffeab640a0, n_ranges_arg=0, bufsz=0x7fffeab63f64, flags=0x7fffeab63f60, cost=0x7fffeab64720) at /home/psergey/dev-git2/10.5/sql/multi_range_read.cc:310
 
  #2  0x0000555555fffa26 in DsMrr_impl::dsmrr_info_const (this=0x7fffbc98cf58, keyno=1, seq=0x7fffeab64070, seq_init_param=0x7fffeab640a0, n_ranges=0, bufsz=0x7fffeab64638, flags=0x7fffeab64634, cost=0x7fffeab64720) at /home/psergey/dev-git2/10.5/sql/multi_range_read.cc:1709
 
  #3  0x00005555565cba46 in ha_innobase::multi_range_read_info_const (this=0x7fffbc98ca70, keyno=1, seq=0x7fffeab64070, seq_init_param=0x7fffeab640a0, n_ranges=0, bufsz=0x7fffeab64638, flags=0x7fffeab64634, cost=0x7fffeab64720) at /home/psergey/dev-git2/10.5/storage/innobase/handler/ha_innodb.cc:20545
 
  #4  0x00005555562fa6ee in check_quick_select (param=0x7fffeab649c0, idx=1, index_only=true, tree=0x7fffbc9f1880, update_tbl_stats=true, mrr_flags=0x7fffeab64634, bufsize=0x7fffeab64638, cost=0x7fffeab64720, is_ror_scan=0x7fffeab64632) at /home/psergey/dev-git2/10.5/sql/opt_range.cc:11117
 
  #5  0x00005555562f0e03 in get_key_scans_params (param=0x7fffeab649c0, tree=0x7fffbc9f1588, index_read_must_be_used=false, update_tbl_stats=true, read_time=1.142605633802817) at /home/psergey/dev-git2/10.5/sql/opt_range.cc:7403
 
  #6  0x00005555562e58d8 in SQL_SELECT::test_quick_select (this=0x7fffbc01a448, thd=0x7fffbc000d78, keys_to_use=..., prev_tables=0, limit=18446744073709551615, force_quick_range=false, ordered_output=false, remove_false_parts_of_where=true, only_single_index_range_scan=false) at /home/psergey/dev-git2/10.5/sql/opt_range.cc:2900
 
  #7  0x0000555555e5ac0f in get_quick_record_count (thd=0x7fffbc000d78, select=0x7fffbc01a448, table=0x7fffbc98bbe8, keys=0x7fffbc019278, limit=18446744073709551615) at /home/psergey/dev-git2/10.5/sql/sql_select.cc:4708
 
  #8  0x0000555555e5d419 in make_join_statistics (join=0x7fffbc018328, tables_list=..., keyuse_array=0x7fffbc018618) at /home/psergey/dev-git2/10.5/sql/sql_select.cc:5433
 
  #9  0x0000555555e51b3b in JOIN::optimize_inner (this=0x7fffbc018328) at /home/psergey/dev-git2/10.5/sql/sql_select.cc:2260
 
  #10 0x0000555555e4f446 in JOIN::optimize (this=0x7fffbc018328) at /home/psergey/dev-git2/10.5/sql/sql_select.cc:1606

handler->keyread_time()= 0.0001464754

then, in handler::multi_range_read_info_const(): 

      cost->idx_cpu_cost= (keyread_time(keyno, 0, total_rows) +
 
                           n_ranges * IDX_LOOKUP_COST);

Here, n_ranges=1,
and the cost is:

  $64 = {io_count = 0, avg_io_cost = 1, idx_io_count = 0, idx_avg_io_cost = 1, cpu_cost = 0, idx_cpu_cost = 0.12514647543484894, }

then 

    cost->cpu_cost+= (double) total_rows / TIME_FOR_COMPARE;

and then the cost is:

  $66 = {io_count = 0, avg_io_cost = 1, idx_io_count = 0, idx_avg_io_cost = 1, cpu_cost = 0.20000000000000001, idx_cpu_cost = 0.12514647543484894, import_cost = 0, mem_cost = 0, }

and

(gdb) p cost->total_cost()
 
  $67 = 0.32514647543484898

This is the value that we see in range_scan_alternatives in the optimizer trace.

Comment by Sergei Petrunia [ 2020-03-21 ]

Studying the I_L_SHIPDATE-MISMATCH, the ref access part:

  #0  handler::keyread_time (this=0x7fffbc98ca70, index=1, ranges=1, rows=1) at /home/psergey/dev-git2/10.5-monty/sql/handler.cc:2779
 
  #1  0x0000555555e64034 in best_access_path (join=0x7fffbc018328, s=0x7fffbc019100, remaining_tables=1, join_positions=0x7fffbc0196b0, idx=0, disable_jbuf=true, record_count=1, pos=0x7fffbc0196b0, loose_scan_pos=0x7fffeab64f70) at /home/psergey/dev-git2/10.5-monty/sql/sql_select.cc:7727

key_read(time ... ) =1.0001
note the differences:

  • Here, keyread_time() is called with ranges=1 while range access calls it with ranges=0. (This is the source of the biggest difference for this example)
  • multi_range_read_info_const also adds this cost n_ranges * IDX_LOOKUP_COST (n_ranges=1, unlike 'ranges')
  • multi_range_read_info_const also adds this cost: total_rows / TIME_FOR_COMPARE.
Comment by Sergei Petrunia [ 2020-03-21 ]

Now, let's check ref access on i_l_orderkey and its rowid filter...

              tmp= table->file->read_time(key, 1,
 
                                          (ha_rows) MY_MIN(tmp,s->worst_seeks));

records=5, read_time(...) = 4.

The filter has:

(gdb) p *filter
 
  $83 = {... est_elements = 1, 
         b = 0.13014647543484895, 
         a = 1.1998001665278932, 
         cross_x = 0.10847346005250223,
 
         a_adj = 0.99983347210657769, 
         cross_x_adj = 0.13016815206300267, 
         key_no = 1, 
         selectivity = 0.00016652789342214822}


filter->get_adjusted_gain(5)=4.86
 
filter->get_cmp_gain()=0.99983

note the

         b = 0.13014647543484895,

This is the cost to build the Rowid Filter. It's the third different number for the same operation - cost of doing an index only scan.

Comment by Sergei Petrunia [ 2020-03-22 ]

.. Investigating where this number comes from.

  #0  Range_rowid_filter_cost_info::build_cost (this=0x7fffb801a688, cont_type=SORTED_ARRAY_CONTAINER) at /home/psergey/dev-git2/10.5/sql/rowid_filter.cc:139
 
  #1  0x000055555607ccb5 in Range_rowid_filter_cost_info::init (this=0x7fffb801a688, cont_type=SORTED_ARRAY_CONTAINER, tab=0x7fffb898bbe8, idx=6) at /home/psergey/dev-git2/10.5/sql/rowid_filter.cc:116
 
  #2  0x000055555607d70c in TABLE::init_cost_info_for_usable_range_rowid_filters (this=0x7fffb898bbe8, thd=0x7fffb8000d78) at /home/psergey/dev-git2/10.5/sql/rowid_filter.cc:400
 
  #3  0x0000555555e5d515 in make_join_statistics (join=0x7fffb8018328, tables_list=..., keyuse_array=0x7fffb8018618) at /home/psergey/dev-git2/10.5/sql/sql_select.cc:5448
 
  #4  0x0000555555e51b3b in JOIN::optimize_inner (this=0x7fffb8018328) at /home/psergey/dev-git2/10.5/sql/sql_select.cc:2260

quick_index_only_costs are set in range optimizer, in check_quick_select:

        param->table->quick_index_only_costs[keynr]= cost->index_only_cost();

which is defined as 

  double index_only_cost()
 
  {
 
    return IO_COEFF*idx_io_count*idx_avg_io_cost +
 
           CPU_COEFF*idx_cpu_cost;
 
  }


$129 = {io_count = 0, avg_io_cost = 1, idx_io_count = 0, idx_avg_io_cost = 1,
 
cpu_cost = 0.20000000000000001, idx_cpu_cost = 0.12514647543484894,
 
import_cost = 0, mem_cost = 0... }

and index_only_cost()=0.1251

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