[MDEV-6735] Range checked for each record used with key Created: 2014-09-12  Updated: 2015-08-31  Resolved: 2015-06-10

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 5.5.39, 10.0.13
Fix Version/s: 5.5.44, 10.0.20

Type: Bug Priority: Major
Reporter: MG Assignee: Sergei Petrunia
Resolution: Fixed Votes: 1
Labels: optimizer

Attachments: File MDEV-6735.patch     File bugtest.sql.gz     File mdev-6735.sql     File mdev-6735_x2_x1_testcase.sql.gz    
Issue Links:
Relates
relates to MDEV-7786 regression in query plan - join buffe... Closed
relates to MDEV-7923 forcing index changes query plan (eve... Closed
Sprint: 10.0.20

 Description   

Using the attached mysqldump, the following query is very slow in MariaDB compared to MySQL 5.5 or MySQL 5.6:

SELECT 1 FROM `catalog_category_flat_store_1` AS `main_table`
 
              LEFT JOIN `core_url_rewrite` AS `url_rewrite`
 
                 ON url_rewrite.category_id=main_table.entity_id
 
                 AND url_rewrite.is_system=1
 
                 AND url_rewrite.store_id = 1
 
                 AND url_rewrite.id_path LIKE 'category/%'
 
          WHERE (main_table.include_in_menu = '1')
 
          AND (main_table.is_active = '1')
 
          AND (main_table.path like '1/2/%')
 
          ORDER BY `main_table`.`position` ASC

The schema and query are part of Magento, but the attached dump has had FK, some unique indexes, and most of the columns dropped.

The query plan in MySQL, which executes quickly:

|  1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                       | NULL                                            | NULL    | NULL |  124 | Using where; Using temporary; Using filesort |
 
|  1 | SIMPLE      | url_rewrite | range | UNQ_CORE_URL_REWRITE_ID_PATH_IS_SYSTEM_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | UNQ_CORE_URL_REWRITE_ID_PATH_IS_SYSTEM_STORE_ID | 773     | NULL | 1138 | Using where                                  |

5.6 has BNL and using Join buffer for the second table, and runs at a similar speed.

In MariaDB 5.5 and MariaDB 10, the following slow plan is used:

|    1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                       | NULL                                            | NULL    | NULL |  149 | Using where; Using filesort                     |
 
|    1 | SIMPLE      | url_rewrite | range | UNQ_CORE_URL_REWRITE_ID_PATH_IS_SYSTEM_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | UNQ_CORE_URL_REWRITE_ID_PATH_IS_SYSTEM_STORE_ID | 773     | NULL | 1138 | Range checked for each record (index map: 0x74) |

This can be made fast in MariaDB with ADD INDEX ix_foo (category_id, store_id) or IGNORE INDEX.

There also seems to be no optimizer_switch to turn off this strategy.

 Comments   
Comment by Elena Stepanova [ 2014-09-15 ]

5.5 revno 4278:
102 rows in set (7 min 45.45 sec)

|    1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |  143 |    98.60 | Using where; Using filesort                     |
 
|    1 | SIMPLE      | url_rewrite | range | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1138 |    75.04 | Range checked for each record (index map: 0x1E) |
 
 
 
select 1 AS `1` from `test`.`catalog_category_flat_store_1` `main_table` left join `test`.`core_url_rewrite` `url_rewrite` on(((`test`.`url_rewrite`.`category_id` = `test`.`main_table`.`entity_id`) and (`test`.`url_rewrite`.`is_system` = 1) and (`test`.`url_rewrite`.`store_id` = 1) and (`test`.`url_rewrite`.`id_path` like 'category/%'))) where ((`test`.`main_table`.`include_in_menu` = '1') and (`test`.`main_table`.`is_active` = '1') and (`test`.`main_table`.`path` like '1/2/%')) order by `test`.`main_table`.`position`

10.0 revno 4393:
102 rows in set (10 min 16.73 sec)

| id   | select_type | table       | type | possible_keys                                                                                                                                          | key                          | key_len | ref  | rows    | filtered | Extra                                           |
 
+------+-------------+-------------+------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+---------+----------+-------------------------------------------------+
 
|    1 | SIMPLE      | main_table  | ALL  | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |     143 |    98.60 | Using where; Using filesort                     |
 
|    1 | SIMPLE      | url_rewrite | ALL  | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1069786 |     0.08 | Range checked for each record (index map: 0x1E) |
 
 
 
Note  | 1003 | select 1 AS `1` from `test`.`catalog_category_flat_store_1` `main_table` left join `test`.`core_url_rewrite` `url_rewrite` on(((`test`.`url_rewrite`.`category_id` = `test`.`main_table`.`entity_id`) and (`test`.`url_rewrite`.`is_system` = 1) and (`test`.`url_rewrite`.`store_id` = 1) and (`test`.`url_rewrite`.`id_path` like 'category/%'))) where ((`test`.`main_table`.`include_in_menu` = '1') and (`test`.`main_table`.`is_active` = '1') and (`test`.`main_table`.`path` like '1/2/%')) order by `test`.`main_table`.`position`

5.6 revno 6060:
102 rows in set (0.13 sec)

|  1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |  143 |    98.60 | Using where; Using temporary; Using filesort       |
 
|  1 | SIMPLE      | url_rewrite | range | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1138 |   100.00 | Using where; Using join buffer (Block Nested Loop) |
 
 
 
/* select#1 */ select 1 AS `1` from `test`.`catalog_category_flat_store_1` `main_table` left join `test`.`core_url_rewrite` `url_rewrite` on(((`test`.`url_rewrite`.`store_id` = 1) and (`test`.`url_rewrite`.`is_system` = 1) and (`test`.`url_rewrite`.`category_id` = `test`.`main_table`.`entity_id`) and (`test`.`url_rewrite`.`id_path` like 'category/%'))) where ((`test`.`main_table`.`include_in_menu` = '1') and (`test`.`main_table`.`is_active` = '1') and (`test`.`main_table`.`path` like '1/2/%')) order by `test`.`main_table`.`position`

Comment by MG [ 2015-03-17 ]

I get a quick response in 5.5.32: 102 rows in set (0.03 sec)

|    1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |  143 | Using where; Using temporary; Using filesort    |
 
|    1 | SIMPLE      | url_rewrite | range | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1138 | Using where; Using join buffer (flat, BNL join) |

I get a slow plan in 5.5.33 as well as 5.5.33a: 102 rows in set (48.10 sec)

|    1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |  143 | Using where; Using filesort                     |
 
|    1 | SIMPLE      | url_rewrite | range | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1138 | Range checked for each record (index map: 0x1E) |

Any version I tested after 5.5.32 showed this slow QEP. I was prompted to check older versions after reading MDEV-7786

Comment by Daniel Black [ 2015-03-20 ]

FYI, taking the [5.5 head and reverting [r3204

leads to and explain of:

MariaDB [test]> explain SELECT 1 FROM `catalog_category_flat_store_1` AS `main_table`               LEFT JOIN `core_url_rewrite` AS `url_rewrite`                  ON url_rewrite.category_id=main_table.entity_id                  AND url_rewrite.is_system=1                  AND url_rewrite.store_id = 1                  AND url_rewrite.id_path LIKE 'category/%'           WHERE (main_table.include_in_menu = '1')           AND (main_table.is_active = '1')           AND (main_table.path like '1/2/%')           ORDER BY `main_table`.`position` ASC;
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+
 
| id   | select_type | table       | type  | possible_keys                                                                                                                                          | key                          | key_len | ref  | rows | Extra                                           |
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |  143 | Using where; Using temporary; Using filesort    |
 
|    1 | SIMPLE      | url_rewrite | range | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1138 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+

This looks very like MDEV-7786

(removed debug trace, was looking at wrong join)

Comment by Daniel Black [ 2015-03-20 ] 

SELECT 1 FROM `catalog_category_flat_store_1` AS `main_table`
 
              LEFT JOIN `core_url_rewrite` AS `url_rewrite`
 
                 ON url_rewrite.category_id=main_table.entity_id
 
                 AND url_rewrite.is_system=1
 
                 AND url_rewrite.store_id = 1
 
                 AND url_rewrite.id_path LIKE 'category/%'
 
          WHERE (main_table.include_in_menu = '1')
 
          AND (main_table.is_active = '1')
 
          AND (main_table.path like '1/2/%')
 
          ORDER BY `main_table`.`position` ASC
 
 
 
Breakpoint 3, make_join_select (join=0x7f2d24914078, select=0x7f2d24912428, cond=0x7f2d2490eee0) at /home/dan/software_projects/mariadb-server/sql/sql_select.cc:9014        
9014              sel->quick_keys= tab->table->quick_keys;
 
(gdb) p sel->needed_reg
 
$16 = {map = 0}
 
(gdb) p sel->quick_keys
 
$17 = {map = 0}
 
(gdb) p tab->table->quick_keys
 
$18 = {map = 2}
 
(gdb) n
 
9015              if (!sel->quick_keys.is_subset(tab->checked_keys) ||
 
(gdb) p sel->quick_keys
 
$19 = {map = 2}
 
(gdb) p tab->checked_keys
 
$20 = {map = 0}
 
(gdb) p sel->needed_reg
 
$21 = {map = 0}                                                                                                                                                              
(gdb) n                                                                                                                                                                      
9018                tab->use_quick= (!sel->needed_reg.is_clear_all() &&
 
(gdb) p sel->quick->records
 
Cannot access memory at address 0x8
 
(gdb) p sel->quick
 
$22 = (QUICK_SELECT_I *) 0x0
 
(gdb) p sel->needed_reg
 
$23 = {map = 0}
 
(gdb) p sel->quick_keys
 
$24 = {map = 2}                                                                                                                                                              
(gdb) p tab->use_quick                                                                                                                                                       
$25 = 0
 
(gdb) n
 
9022                  2 : 1;
 
(gdb) n
 
9023                sel->read_tables= used_tables & ~current_map;
 
(gdb) p tab->use_quick
 
$26 = 1
 
(gdb) p used_tables
 
$27 = 13835058055282163713
 
(gdb) p current_map
 
$28 = 1
 
(gdb) n
 
9024                sel->quick_keys.clear_all();
 
(gdb) p sel->read_tables
 
$29 = 13835058055282163712
 
(gdb) p sel->quick_keys
 
$30 = {map = 2}
 
(gdb) n
 
9026              if (i != join->const_tables && tab->use_quick != 2 &&
 
(gdb) p sel->quick_keys
 
$31 = {map = 0}
 
(gdb) p select->quick_keys
 
$32 = {map = 0}
 
(gdb) p sel->quick
 
$33 = (QUICK_SELECT_I *) 0x0
 
(gdb) p tab->use_quick
 
$34 = 1
 
(gdb) p join->const_tables
 
$35 = 0
 
(gdb) p i
 
$36 = 0
 
(gdb) p tab->first_inner
 
$37 = (st_join_table *) 0x0  
(gdb) c                                                                                                                                                                      
Continuing.
 
 
 
Breakpoint 2, make_join_select (join=0x7f2d24914078, select=0x7f2d24912428, cond=0x7f2d2490eee0) at /home/dan/software_projects/mariadb-server/sql/sql_select.cc:8939
 
8939            uint ref_key= sel->head? (uint) sel->head->reginfo.join_tab->ref.key+1 : 0;
 
(gdb) c
 
Continuing.
 
 
 
Breakpoint 3, make_join_select (join=0x7f2d24914078, select=0x7f2d24912428, cond=0x7f2d2490eee0) at /home/dan/software_projects/mariadb-server/sql/sql_select.cc:9014
 
9014              sel->quick_keys= tab->table->quick_keys;
 
(gdb) n
 
9015              if (!sel->quick_keys.is_subset(tab->checked_keys) ||
 
(gdb) p sel->quick_keys
 
$38 = {map = 14}
 
(gdb) p *tab->table
 
$39 = {s = 0x7f2d2484ff78, file = 0x7f2d248d3078, next = 0x7f2d2482d660, prev = 0x7f2d24831260, share_next = 0x0, share_prev = 0x7f2d24850110, in_use = 0x7f2d437ad060, 
  field = 0x7f2d24850e78, record = {0x7f2d24895d78 "\377\217\217\217\217\001", 0x7f2d24896088 "\377", '\245' <repeats 199 times>...}, write_row_record = 0x0, 
  insert_values = 0x0, covering_keys = {map = 0}, quick_keys = {map = 14}, merge_keys = {map = 30}, intersect_keys = {map = 0}, keys_in_use_for_query = {map = 31}, 
  keys_in_use_for_group_by = {map = 31}, keys_in_use_for_order_by = {map = 31}, key_info = 0x7f2d24851378, next_number_field = 0x0, 
  found_next_number_field = 0x7f2d24850ea8, timestamp_field = 0x0, vfield = 0x0, triggers = 0x0, pos_in_table_list = 0x7f2d24821c70, pos_in_locked_tables = 0x0, 
  group = 0x0, alias = {Ptr = 0x7f2d2481f160 "url_rewrite", str_length = 11, Alloced_length = 24, extra_alloc = 0, alloced = true, 
    str_charset = 0x13b4b00 <my_charset_bin>}, null_flags = 0x7f2d24895d78 "\377\217\217\217\217\001", bitmap_init_value = 0x0, def_read_set = {bitmap = 0x7f2d248511b0, 
    last_word_ptr = 0x7f2d248511b0, mutex = 0x0, last_word_mask = 4294967264, n_bits = 5}, def_write_set = {bitmap = 0x7f2d248511b4, last_word_ptr = 0x7f2d248511b4, 
    mutex = 0x0, last_word_mask = 4294967264, n_bits = 5}, def_vcol_set = {bitmap = 0x7f2d248511b8, last_word_ptr = 0x7f2d248511b8, mutex = 0x0, 
    last_word_mask = 4294967264, n_bits = 5}, tmp_set = {bitmap = 0x7f2d248511bc, last_word_ptr = 0x7f2d248511bc, mutex = 0x0, last_word_mask = 4294967264, n_bits = 5}, 
  eq_join_set = {bitmap = 0x7f2d248511c0, last_word_ptr = 0x7f2d248511c0, mutex = 0x0, last_word_mask = 4294967264, n_bits = 5}, read_set = 0x7f2d2482ff70, 
  write_set = 0x7f2d2482ff90, vcol_set = 0x7f2d2482ffb0, query_id = 0, quick_rows = {0, 393206, 1138, 393206, 0 <repeats 60 times>}, const_key_parts = {0, 1, 0, 1, 
    0 <repeats 60 times>}, quick_key_parts = {0, 1, 1, 1, 0 <repeats 60 times>}, quick_n_ranges = {0, 1, 1, 1, 0 <repeats 60 times>}, quick_condition_rows = 1138, 
  timestamp_field_type = TIMESTAMP_NO_AUTO_SET, map = 2, lock_position = 1, lock_data_start = 1, lock_count = 1, tablenr = 1, used_fields = 4, temp_pool_slot = 0, 
  status = 3, db_stat = 39, derived_select_number = 0, maybe_null = 1, current_lock = 0, copy_blobs = false, next_number_field_updated = false, null_row = false, 
  no_rows_with_nulls = false, null_catch_flags = 0 '\000', force_index = false, force_index_order = false, force_index_group = false, distinct = false, 
  const_table = false, no_rows = false, used_for_duplicate_elimination = false, keep_row_order = false, key_read = false, no_keyread = false, locked_by_logger = false, 
  no_replicate = false, locked_by_name = false, fulltext_searched = false, no_cache = false, open_by_handler = false, auto_increment_field_not_null = false, 
  insert_or_update = false, alias_name_used = false, get_fields_in_item_tree = false, m_needs_reopen = false, created = true, reginfo = {join_tab = 0x7f2d249120e8, 
    lock_type = TL_READ, not_exists_optimize = false, impossible_range = false}, mem_root = {free = 0x7f2d24850e60, used = 0x7f2d24851360, pre_alloc = 0x0, 
    min_malloc = 32, block_size = 984, block_num = 8, first_block_usage = 0, error_handler = 0x6dea74 <sql_alloc_error_handler()>}, grant = {grant_table = 0x0, 
    version = 0, privilege = 18446744072635809791, want_privilege = 0, orig_want_privilege = 1, m_internal = {m_schema_lookup_done = true, m_schema_access = 0x0, 
      m_table_lookup_done = true, m_table_access = 0x0}}, sort = {io_cache = 0x0, sort_keys = 0x0, keys = 0, buffpek = 0x0, buffpek_len = 0, addon_buf = 0x0, 
    addon_length = 0, addon_field = 0x0, unpack = 0x0, record_pointers = 0x0, found_records = 0}, expr_arena = 0x0, part_info = 0x0, no_partitions_used = false, 
  max_keys = 0, mdl_ticket = 0x7f2d248802a0}
 
(gdb) p sel->quick_keys
 
$41 = {map = 14}
 
(gdb) p sel->checked_keys
 
There is no member or method named checked_keys.
 
(gdb) p sel->needed_reg
 
$42 = {map = 16}
 
(gdb) n
 
9018                tab->use_quick= (!sel->needed_reg.is_clear_all() &&
 
(gdb) p sel->needed_reg
 
$43 = {map = 16}
 
(gdb) p select->needed_reg
 
$44 = {map = 0}
 
(gdb) p sel->quick_keys
 
$45 = {map = 14}
 
(gdb) p select->quick_keys
 
$46 = {map = 0}
 
(gdb) p sel->quick
 
$47 = (QUICK_SELECT_I *) 0x7f2d2488e220
 
(gdb) p select->quick
 
$48 = (QUICK_SELECT_I *) 0x0
 
(gdb) p sel->quick->records
 
$49 = 1138
 
(gdb) n
 
9022                  2 : 1;
 
(gdb) n
 
9019                                 (sel->quick_keys.is_clear_all() ||
 
(gdb) p tab->use_quick
 
$50 = 0
 
(gdb) n
 
9018                tab->use_quick= (!sel->needed_reg.is_clear_all() &&
 
(gdb) p tab->use_quick
 
$51 = 0
 
(gdb) n
 
9019                                 (sel->quick_keys.is_clear_all() ||
 
(gdb) p tab->use_quick
 
$52 = 0
 
(gdb) n
 
9021                                   (sel->quick->records >= 100L)))) ?
 
(gdb) n
 
9020                                  (sel->quick &&
 
(gdb) n
 
9022                  2 : 1;
 
(gdb) n
 
9023                sel->read_tables= used_tables & ~current_map;
 
(gdb) p tab->use_quick
 
$53 = 2
 
(gdb) p used_tables
 
$54 = 13835058055282163715
 
(gdb) p current_map
 
$55 = 13835058055282163714
 
(gdb) n
 
9024                sel->quick_keys.clear_all();
 
(gdb) p sel->read_tables
 
$56 = 1
 
(gdb) p sel->quick_keys
 
$57 = {map = 14}
 
(gdb) n
 
9026              if (i != join->const_tables && tab->use_quick != 2 &&
 
(gdb) c
 
Continuing.
 
 
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+
 
| id   | select_type | table       | type  | possible_keys                                                                                                                                          | key                          | key_len | ref  | rows | Extra                                           |
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |  143 | Using where; Using filesort                     |
 
|    1 | SIMPLE      | url_rewrite | range | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1138 | Range checked for each record (index map: 0x1E) |
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+
 
 
 
The sel->quick->records >= 100L criteria caused tab->use_quick=2 which cause Range checked for each

sample patch

diff --git a/sql/sql_select.cc b/sql/sql_select.cc                                                                                                                           
index 8a53b98..01c811b 100644                                                                                                                                                
--- a/sql/sql_select.cc
 
+++ b/sql/sql_select.cc
 
@@ -9016,9 +9016,7 @@ bool TABLE_LIST::is_active_sjm()
 
               !sel->needed_reg.is_subset(tab->checked_keys))
 
          {
 
            tab->use_quick= (!sel->needed_reg.is_clear_all() &&
 
-                            (sel->quick_keys.is_clear_all() ||
 
-                             (sel->quick &&
 
-                              (sel->quick->records >= 100L)))) ?
 
+                            sel->quick_keys.is_clear_all()) ?
 
              2 : 1;
 
            sel->read_tables= used_tables & ~current_map;
 
             sel->quick_keys.clear_all();
 

MariaDB [test]> explain SELECT 1 FROM `catalog_category_flat_store_1` AS `main_table`               LEFT JOIN `core_url_rewrite` AS `url_rewrite`                  ON url_rewrite.category_id=main_table.entity_id                  AND url_rewrite.is_system=1                  AND url_rewrite.store_id = 1                  AND url_rewrite.id_path LIKE 'category/%'           WHERE (main_table.include_in_menu = '1')           AND (main_table.is_active = '1')           AND (main_table.path like '1/2/%')           ORDER BY `main_table`.`position` ASC;
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+
 
| id   | select_type | table       | type  | possible_keys                                                                                                                                          | key                          | key_len | ref  | rows | Extra                                           |
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | main_table  | ALL   | IDX_CATALOG_CATEGORY_FLAT_STORE_1_PATH                                                                                                                 | NULL                         | NULL    | NULL |  143 | Using where; Using temporary; Using filesort    |
 
|    1 | SIMPLE      | url_rewrite | range | IDX_CORE_URL_REWRITE_TARGET_PATH_STORE_ID,IDX_CORE_URL_REWRITE_ID_PATH,IDX_CORE_URL_REWRITE_STORE_ID,FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID | IDX_CORE_URL_REWRITE_ID_PATH | 768     | NULL | 1138 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------------+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+------------------------------+---------+------+------+-------------------------------------------------+

So successful.

regressions?

$ ./mtr range
 
Logging: ./mtr  range
 
vardir: /home/dan/software_projects/mariadb-server/mysql-test/var
 
Checking leftover processes...
 
Removing old var directory...
 
Creating var directory '/home/dan/software_projects/mariadb-server/mysql-test/var'...
 
Checking supported features...
 
MariaDB Version 5.5.42-MariaDB-debug
 
Installing system database...
 
 - skipping SSL, mysqld not compiled with SSL
 
 - binaries are debug compiled
 
Collecting tests...
 
 
 
==============================================================================
 
 
 
TEST                                      RESULT   TIME (ms) or COMMENT
 
--------------------------------------------------------------------------
 
 
 
worker[1] Using MTR_BUILD_THREAD 300, with reserved ports 16000..16019
 
main.range 'innodb_plugin'               [ pass ]   7284
 
main.range 'xtradb'                      [ pass ]   5542
 
--------------------------------------------------------------------------
 
The servers were restarted 1 times
 
Spent 12.826 of 30 seconds executing testcases
 
 
 
Completed: All 2 tests were successful.

Comment by Daniel Black [ 2015-03-20 ]

working patch attached. Now just need to simplify test from orig.

Comment by Daniel Black [ 2015-03-20 ]

test case for mdev-6735.sql

explain SELECT 1 FROM x1 LEFT JOIN x2 ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'c/%';

Comment by Daniel Black [ 2015-03-20 ]

As we can see here, the unused index FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID is having an effect on the query plan.

mdev-6735_x3_x1.sql in private ftp uploads

MariaDB [test]> drop table if exists x4;create table x4 like x3; insert into x4 select *  from x3; ANALYZE TABLE x4 PERSISTENT FOR ALL;  explain SELECT 1 FROM x1 LEFT JOIN x4  x2 ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'category/%';                                               
Query OK, 0 rows affected (0.03 sec)
 
 
 
Query OK, 0 rows affected (0.01 sec)
 
 
 
Query OK, 1139498 rows affected (16.21 sec)
 
Records: 1139498  Duplicates: 0  Warnings: 0
 
 
 
+---------+---------+----------+-----------------------------------------+
 
| Table   | Op      | Msg_type | Msg_text                                |
 
+---------+---------+----------+-----------------------------------------+
 
| test.x4 | analyze | status   | Engine-independent statistics collected |
 
| test.x4 | analyze | status   | OK                                      |
 
+---------+---------+----------+-----------------------------------------+
 
2 rows in set (7.14 sec)
 
 
 
+------+-------------+-------+-------+-------------------------------------------------------+---------+---------+------+---------+------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys                                         | key     | key_len | ref  | rows    | Extra                                          |
 
+------+-------------+-------+-------+-------------------------------------------------------+---------+---------+------+---------+------------------------------------------------+
 
|    1 | SIMPLE      | x1    | index | NULL                                                  | PRIMARY | 4       | NULL |     143 | Using index                                    |
 
|    1 | SIMPLE      | x2    | ALL   | FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID,idx | idx     | 768     | NULL | 1148729 | Range checked for each record (index map: 0x6) |
 
+------+-------------+-------+-------+-------------------------------------------------------+---------+---------+------+---------+------------------------------------------------+
 
2 rows in set (0.00 sec)
 
 
 
MariaDB [test]> select * from mysql.index_stats where db_name='test' and table_name in ('x4');                                                                                        +---------+------------+---------------------------------------------------+--------------+---------------+
 
| db_name | table_name | index_name                                        | prefix_arity | avg_frequency |
 
+---------+------------+---------------------------------------------------+--------------+---------------+
 
| test    | x4         | FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID |            1 |     1926.6338 |
 
| test    | x4         | FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID |            2 |        1.0000 |
 
| test    | x4         | PRIMARY                                           |            1 |        1.0000 |
 
| test    | x4         | idx                                               |            1 |        1.1271 |
 
| test    | x4         | idx                                               |            2 |        1.0000 |
 
+---------+------------+---------------------------------------------------+--------------+---------------+
 
5 rows in set (0.00 sec)
 
 
 
MariaDB [test]> 
MariaDB [test]> alter table x4 drop key FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID;Query OK, 0 rows affected (0.04 sec)
 
Records: 0  Duplicates: 0  Warnings: 0
 
 
 
MariaDB [test]> ANALYZE TABLE x4 PERSISTENT FOR ALL;  explain SELECT 1 FROM x1 LEFT JOIN x4  x2 ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'category/%';+---------+---------+----------+-----------------------------------------+
 
| Table   | Op      | Msg_type | Msg_text                                |
 
+---------+---------+----------+-----------------------------------------+
 
| test.x4 | analyze | status   | Engine-independent statistics collected |
 
| test.x4 | analyze | status   | OK                                      |
 
+---------+---------+----------+-----------------------------------------+
 
2 rows in set (9.21 sec)
 
 
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                                           |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | x1    | index | NULL          | PRIMARY | 4       | NULL |  143 | Using index                                     |
 
|    1 | SIMPLE      | x2    | range | idx           | idx     | 768     | NULL | 1138 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
2 rows in set (0.00 sec)
 
 
 
MariaDB [test]> show create table x3;
 
+-------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| Table | Create Table                                                                                                                                                                                                                                                                                                                                                                                                          |
 
+-------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| x3    | CREATE TABLE `x3` (
 
  `x2_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
 
  `id_path` varchar(255) DEFAULT NULL COMMENT 'Id Path',
 
  `category_id` int(10) unsigned DEFAULT NULL COMMENT 'Category Id',
 
  PRIMARY KEY (`x2_id`),
 
  KEY `FK_CORE_URL_REWRITE_CTGR_ID_CAT_CTGR_ENTT_ENTT_ID` (`category_id`),
 
  KEY `idx` (`id_path`)
 
) ENGINE=InnoDB AUTO_INCREMENT=13363204 DEFAULT CHARSET=utf8 COMMENT='Url Rewrites' |
 
+-------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

Comment by Daniel Black [ 2015-03-21 ]

Is this test case file too big? I was getting different query plan attempting to make x2 any smaller.

 analyze table x1 persistent for all;analyze table x2 persistent for all; explain SELECT 1 FROM x1 LEFT JOIN x2 ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'c%';
 
 
 
current 10.0.17:
 
 
 
MariaDB [test]>  analyze table x1 persistent for all;analyze table x2 persistent for all; explain SELECT 1 FROM x1 LEFT JOIN x2 ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'c%';
 
+---------+---------+----------+-----------------------------------------+
 
| Table   | Op      | Msg_type | Msg_text                                |
 
+---------+---------+----------+-----------------------------------------+
 
| test.x1 | analyze | status   | Engine-independent statistics collected |
 
| test.x1 | analyze | status   | OK                                      |
 
+---------+---------+----------+-----------------------------------------+
 
2 rows in set (0.00 sec)
 
 
 
+---------+---------+----------+-----------------------------------------+
 
| Table   | Op      | Msg_type | Msg_text                                |
 
+---------+---------+----------+-----------------------------------------+
 
| test.x2 | analyze | status   | Engine-independent statistics collected |
 
| test.x2 | analyze | status   | OK                                      |
 
+---------+---------+----------+-----------------------------------------+
 
2 rows in set (0.09 sec)
 
 
 
+------+-------------+-------+-------+---------------+---------+---------+------+-------+------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra                                          |
 
+------+-------------+-------+-------+---------------+---------+---------+------+-------+------------------------------------------------+
 
|    1 | SIMPLE      | x1    | index | NULL          | PRIMARY | 4       | NULL |   143 | Using index                                    |
 
|    1 | SIMPLE      | x2    | ALL   | idx,c         | idx     | 18      | NULL | 36832 | Range checked for each record (index map: 0x6) |
 
+------+-------------+-------+-------+---------------+---------+---------+------+-------+------------------------------------------------+
 
 
 
 select * from mysql.index_stats where db_name='test' and table_name in ('x1','x2');
 
+---------+------------+------------+--------------+---------------+
 
| db_name | table_name | index_name | prefix_arity | avg_frequency |
 
+---------+------------+------------+--------------+---------------+
 
| test    | x1         | PRIMARY    |            1 |        1.0000 |
 
| test    | x2         | PRIMARY    |            1 |        1.0000 |
 
| test    | x2         | c          |            1 |       82.3037 |
 
| test    | x2         | c          |            2 |        1.0000 |
 
| test    | x2         | idx        |            1 |       37.6357 |
 
| test    | x2         | idx        |            2 |        1.0000 |
 
+---------+------------+------------+--------------+---------------+
 
 
 
 
 
with patch on 10.0 branch head:
 
 
 
MariaDB [test]> analyze table x1 persistent for all;analyze table x2 persistent for all; explain SELECT 1 FROM x1 LEFT JOIN x2 ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'c%';
 
+---------+---------+----------+-----------------------------------------+
 
| Table   | Op      | Msg_type | Msg_text                                |
 
+---------+---------+----------+-----------------------------------------+
 
| test.x1 | analyze | status   | Engine-independent statistics collected |
 
| test.x1 | analyze | Error    | Table 'mysql.table_stats' doesn't exist |
 
| test.x1 | analyze | status   | OK                                      |
 
+---------+---------+----------+-----------------------------------------+
 
3 rows in set (0.00 sec)
 
 
 
+---------+---------+----------+-----------------------------------------+
 
| Table   | Op      | Msg_type | Msg_text                                |
 
+---------+---------+----------+-----------------------------------------+
 
| test.x2 | analyze | status   | Engine-independent statistics collected |
 
| test.x2 | analyze | Error    | Table 'mysql.table_stats' doesn't exist |
 
| test.x2 | analyze | status   | OK                                      |
 
+---------+---------+----------+-----------------------------------------+
 
3 rows in set (6.43 sec)
 
 
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                                           |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | x1    | index | NULL          | PRIMARY | 4       | NULL |  143 | Using index                                     |
 
|    1 | SIMPLE      | x2    | range | idx,c         | idx     | 18      | NULL |  114 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
 

Comment by Daniel Black [ 2015-03-22 ]

odd workaround - forcing an index it chose already

on 10.0.17
 
MariaDB [test]> explain SELECT 1 FROM x1  LEFT JOIN  x2 ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'c/%';
 
+------+-------------+-------+-------+---------------+---------+---------+------+-------+------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra                                          |
 
+------+-------------+-------+-------+---------------+---------+---------+------+-------+------------------------------------------------+
 
|    1 | SIMPLE      | x1    | index | NULL          | PRIMARY | 4       | NULL |   143 | Using index                                    |
 
|    1 | SIMPLE      | x2    | ALL   | idx,c         | idx     | 18      | NULL | 36832 | Range checked for each record (index map: 0x6) |
 
+------+-------------+-------+-------+---------------+---------+---------+------+-------+------------------------------------------------+
 
 
 
MariaDB [test]> explain SELECT 1 FROM x1  LEFT JOIN  x2 FORCE INDEX FOR JOIN (idx)  ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'c/%';
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                                           |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | x1    | index | NULL          | PRIMARY | 4       | NULL |  143 | Using index                                     |
 
|    1 | SIMPLE      | x2    | range | idx           | idx     | 18      | NULL |  114 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
2 rows in set (0.00 sec)
 
 
 
MariaDB [test]> explain SELECT 1 FROM x1  LEFT JOIN  x2 IGNORE INDEX FOR JOIN (c)  ON x2.category_id=x1.entity_id AND x2.id_path LIKE 'c/%';
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
| id   | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra                                           |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
|    1 | SIMPLE      | x1    | index | NULL          | PRIMARY | 4       | NULL |  143 | Using index                                     |
 
|    1 | SIMPLE      | x2    | range | idx           | idx     | 18      | NULL |  114 | Using where; Using join buffer (flat, BNL join) |
 
+------+-------------+-------+-------+---------------+---------+---------+------+------+-------------------------------------------------+
 
2 rows in set (0.00 sec)

Comment by Daniel Black [ 2015-03-22 ]

added test cases - https://github.com/openquery/mariadb-server/commit/e047bf9be60b8ed3057324f61ad3e2c3bd0ff13d - still getting query plans that vary between test runs as per comment in commit. Suggestions welcome.

Comment by Sergei Petrunia [ 2015-03-23 ]

Looking at the patch...

So, the old code switched to using "Range checked for each record" when

 there were potential range accesses,
 
 AND
 
  ( no quick select could be constructed OR
 
    the best quick select returned > 100 rows)

with the patch, we switch to "Range checked for each record" when

  there were potential range accesses AND 
  no quick select could be constructed

Comment by Sergei Petrunia [ 2015-03-23 ]

This seems to make sense in most cases.

Additional argument against "Range checked for each record" is that it can use join buffer (in recent versions with outer joins, too), which can be much faster than "range checked for each record".

OTOH, debugging the example for MDEV-7786, I see that the quick select produced by this call:

	    /*
 
              We can't call sel->cond->fix_fields,
 
              as it will break tab->on_expr if it's AND condition
 
              (fix_fields currently removes extra AND/OR levels).
 
              Yet attributes of the just built condition are not needed.
 
              Thus we call sel->cond->quick_fix_field for safety.
 
	    */
 
	    if (sel->cond && !sel->cond->fixed)
 
	      sel->cond->quick_fix_field();
 
 
 
	    if (sel->test_quick_select(thd, tab->keys,
 
				       ((used_tables & ~ current_map) |
 
                                        OUTER_REF_TABLE_BIT),
 
				       (join->select_options &
 
					OPTION_FOUND_ROWS ?
 
					HA_POS_ERROR :
 
					join->unit->select_limit_cnt), 0,
 
                                        FALSE) < 0)

it passes limit=300 as an argument SQL_SELECT::test_quick_select, which causes it to create quick select even when it is more expensive than full table scan.

I'm concerned about possible regressions.

Maybe, also add a requirement that
1. quick select exists
2. its cost is less than the cost of full table scan?

Comment by Sergei Petrunia [ 2015-03-23 ]

Implementing the above ideas, modified danblack's patch to be more conservative:

diff --git a/sql/sql_select.cc b/sql/sql_select.cc
 
index 7d75c12..b633e57 100644
 
--- a/sql/sql_select.cc
 
+++ b/sql/sql_select.cc
 
@@ -9740,8 +9740,9 @@ bool TABLE_LIST::is_active_sjm()
 
          {
 
            tab->use_quick= (!sel->needed_reg.is_clear_all() &&
 
                             (sel->quick_keys.is_clear_all() ||
 
-                             (sel->quick &&
 
-                              (sel->quick->records >= 100L)))) ?
 
+                             (sel->quick && 
+                                sel->quick->read_time >
 
+                                tab->table->file->scan_time()))) ?
 
              2 : 1;
 
            sel->read_tables= used_tables & ~current_map;
 
             sel->quick_keys.clear_all();

It still passes the testcase for this bug and for MDEV-7786.

Comment by Daniel Black [ 2015-03-23 ]

Thanks psergey works for me.

Comment by MG [ 2015-03-26 ]

With this patch on 5.5.42, I have gotten a few different plans depending on what table statistics happen to be, each not using "Range checked for each record (index map: 0x1E)" and several orders of magnitude faster than unpatched 5.5.42 which uses "Range checked for each record (index map: 0x1E)" for my sample data and query.

Comment by Daniel Black [ 2015-04-01 ]

psergey, really keen to see your patch committed. While I'm still not sure why what "sel->quick->read_time" and "tab->table->file->scan_time()" are exactly (happy to remain ignorant for a while - I trust you), it does look better than rather arbitrary looking 100 row limit. While its always tough doing these changes for fear of regressions this is already a regression from 5.5.33. Magento has a not insignificant user base who would notice the difference between a 0.13 sec query and a 10 minute query once they reached a not too high limit on categories.

Comment by Daniel Black [ 2015-05-12 ]

can we get this patch into the next 5.5/10.0 release?

Comment by Sergei Petrunia [ 2015-06-10 ]

Fix was pushed into 5.5 tree.

Comment by Sergei Petrunia [ 2015-06-10 ]

danblack, thanks for all the input on the issue, also for your patience when waiting for it to be pushed!

Generated at Thu Feb 08 07:14:12 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.