[MDEV-21813] Optimizer choosing the wrong index despite the cost calculation Created: 2020-02-25  Updated: 2023-12-05

Status: Stalled
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.4.12
Fix Version/s: 10.4

Type: Bug Priority: Major
Reporter: Manuel Arostegui Assignee: Sergei Petrunia
Resolution: Unresolved Votes: 1
Labels: order-by-optimization, regression
Environment:

debian buster


Issue Links:
Relates
relates to MDEV-23707 Fix condition selectivity computation... Stalled

 Description   

Disclaimer: I cannot provide full query details due to PII.

While testing 10.4.12 vs 10.1 I have noticed the following query there is a big difference on runtime on the following query.
It takes around 12 seconds on 10.4.12 and 0.02 on 10.1.43

SELECT /* SpecialRecentChanges::doMainQuery */ rc_id, rc_timestamp, rc_namespace, rc_title, rc_minor, rc_bot, rc_new, rc_cur_id, rc_this_oldid, rc_last_oldid, rc_type, rc_source, rc_patrolled, rc_ip, rc_old_len, rc_new_len, rc_deleted, rc_logid, rc_log_type, rc_log_action, rc_params, comment_rc_comment.comment_text AS `rc_comment_text`, comment_rc_comment.comment_data AS `rc_comment_data`, comment_rc_comment.comment_id AS `rc_comment_cid`, actor_rc_user.actor_user AS `rc_user`, actor_rc_user.actor_name AS `rc_user_text`, rc_actor, wl_user, wl_notificationtimestamp, page_latest, (SELECT GROUP_CONCAT(ctd_name SEPARATOR ', ') FROM `change_tag` JOIN `change_tag_def` ON ((ct_tag_id=ctd_id)) WHERE ct_rc_id=rc_id ) AS `ts_tags`, fp_stable, fp_pending_since, ores_damaging_cls.oresc_probability AS `ores_damaging_score`, ores_goodfaith_cls.oresc_probability AS `ores_goodfaith_score` FROM `recentchanges` JOIN `actor` `actor_rc_user` ON ((actor_rc_user.actor_id = rc_actor)) LEFT JOIN `user` ON ((actor_rc_user.actor_user = user_id)) JOIN `comment` `comment_rc_comment` ON ((comment_rc_comment.comment_id = rc_comment_id)) LEFT JOIN `watchlist` ON (wl_user = REDACTED AND (wl_title=rc_title) AND (wl_namespace=rc_namespace)) LEFT JOIN `page` ON ((rc_cur_id=page_id)) LEFT JOIN `flaggedpages` ON ((fp_page_id = rc_cur_id)) LEFT JOIN `ores_classification` `ores_damaging_cls` ON (ores_damaging_cls.oresc_model = 37 AND (ores_damaging_cls.oresc_rev=rc_this_oldid) AND ores_damaging_cls.oresc_class = 1) LEFT JOIN `ores_classification` `ores_goodfaith_cls` ON (ores_goodfaith_cls.oresc_model = 38 AND (ores_goodfaith_cls.oresc_rev=rc_this_oldid) AND ores_goodfaith_cls.oresc_class = 1) WHERE ((actor_rc_user.actor_user IS NULL) OR (NOT ( (user_editcount >= 10) AND (user_registration <= '20200220144929') ))) AND rc_bot = 0 AND ((rc_this_oldid = page_latest) OR rc_type = 3) AND (rc_type != 6) AND (rc_source != 'wb') AND (rc_namespace IN ('6', '7')) AND (rc_timestamp >= '20200224144839') AND rc_new IN (0, 1) ORDER BY rc_timestamp DESC LIMIT 500

Explain on 10.4.12:

+------+--------------------+--------------------+--------+----------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+---------+-------------+
| id   | select_type        | table              | type   | possible_keys                                                                                                                                | key                   | key_len | ref                                                                   | rows    | Extra       |
+------+--------------------+--------------------+--------+----------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+---------+-------------+
|    1 | PRIMARY            | recentchanges      | ref    | rc_timestamp,new_name_timestamp,tmp_2,tmp_3,rc_name_type_patrolled_timestamp,rc_ns_actor,rc_actor,rc_namespace_title_timestamp,rc_this_oldid | tmp_2                 | 1       | const                                                                 | 4274159 | Using where |
|    1 | PRIMARY            | watchlist          | eq_ref | wl_user,namespace_title,wl_user_notificationtimestamp                                                                                        | wl_user               | 265     | const,enwiki.recentchanges.rc_namespace,enwiki.recentchanges.rc_title | 1       |             |
|    1 | PRIMARY            | actor_rc_user      | eq_ref | PRIMARY,actor_user                                                                                                                           | PRIMARY               | 8       | enwiki.recentchanges.rc_actor                                         | 1       |             |
|    1 | PRIMARY            | user               | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.actor_rc_user.actor_user                                       | 1       | Using where |
|    1 | PRIMARY            | page               | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.recentchanges.rc_cur_id                                        | 1       | Using where |
|    1 | PRIMARY            | flaggedpages       | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.recentchanges.rc_cur_id                                        | 1       |             |
|    1 | PRIMARY            | ores_damaging_cls  | eq_ref | oresc_rev_model_class                                                                                                                        | oresc_rev_model_class | 7       | enwiki.recentchanges.rc_this_oldid,const,const                        | 1       |             |
|    1 | PRIMARY            | ores_goodfaith_cls | eq_ref | oresc_rev_model_class                                                                                                                        | oresc_rev_model_class | 7       | enwiki.recentchanges.rc_this_oldid,const,const                        | 1       |             |
|    1 | PRIMARY            | comment_rc_comment | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 8       | enwiki.recentchanges.rc_comment_id                                    | 1       |             |
|    2 | DEPENDENT SUBQUERY | change_tag         | ref    | change_tag_rc_tag_id,change_tag_tag_id_id                                                                                                    | change_tag_rc_tag_id  | 5       | enwiki.recentchanges.rc_id                                            | 1       | Using index |
|    2 | DEPENDENT SUBQUERY | change_tag_def     | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.change_tag.ct_tag_id                                           | 1       |             |
+------+--------------------+--------------------+--------+----------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+---------+-------------+
11 rows in set (0.00 sec)

It is picking tmp_2 as an index, while 10.1 picks tmp_3, which is a lot better:
Explain on 10.1

+------+--------------------+--------------------+--------+----------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+------+----------------------------------------------------+
| id   | select_type        | table              | type   | possible_keys                                                                                                                                | key                   | key_len | ref                                                                   | rows | Extra                                              |
+------+--------------------+--------------------+--------+----------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+------+----------------------------------------------------+
|    1 | PRIMARY            | recentchanges      | range  | rc_timestamp,new_name_timestamp,tmp_2,tmp_3,rc_name_type_patrolled_timestamp,rc_ns_actor,rc_actor,rc_namespace_title_timestamp,rc_this_oldid | tmp_3                 | 20      | NULL                                                                  |  958 | Using index condition; Using where; Using filesort |
|    1 | PRIMARY            | watchlist          | eq_ref | wl_user,namespace_title,wl_user_notificationtimestamp                                                                                        | wl_user               | 265     | const,enwiki.recentchanges.rc_namespace,enwiki.recentchanges.rc_title |    1 |                                                    |
|    1 | PRIMARY            | actor_rc_user      | eq_ref | PRIMARY,actor_user                                                                                                                           | PRIMARY               | 8       | enwiki.recentchanges.rc_actor                                         |    1 |                                                    |
|    1 | PRIMARY            | user               | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.actor_rc_user.actor_user                                       |    1 | Using where                                        |
|    1 | PRIMARY            | page               | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.recentchanges.rc_cur_id                                        |    1 | Using where                                        |
|    1 | PRIMARY            | flaggedpages       | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.recentchanges.rc_cur_id                                        |    1 |                                                    |
|    1 | PRIMARY            | ores_damaging_cls  | eq_ref | oresc_rev_model_class                                                                                                                        | oresc_rev_model_class | 7       | enwiki.recentchanges.rc_this_oldid,const,const                        |    1 |                                                    |
|    1 | PRIMARY            | ores_goodfaith_cls | eq_ref | oresc_rev_model_class                                                                                                                        | oresc_rev_model_class | 7       | enwiki.recentchanges.rc_this_oldid,const,const                        |    1 |                                                    |
|    1 | PRIMARY            | comment_rc_comment | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 8       | enwiki.recentchanges.rc_comment_id                                    |    1 |                                                    |
|    2 | DEPENDENT SUBQUERY | change_tag         | ref    | change_tag_rc_tag_id,change_tag_tag_id_id                                                                                                    | change_tag_rc_tag_id  | 5       | enwiki.recentchanges.rc_id                                            |    1 | Using index                                        |
|    2 | DEPENDENT SUBQUERY | change_tag_def     | eq_ref | PRIMARY                                                                                                                                      | PRIMARY               | 4       | enwiki.change_tag.ct_tag_id                                           |    1 |                                                    |
+------+--------------------+--------------------+--------+----------------------------------------------------------------------------------------------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+------+----------------------------------------------------+

Despite of the filesort there, it runs a lot faster and scans a lot less rows.
The optimize trace actually shows that tmp_3 index is a better election, but it chooses tmp_2 anyways:

{
                       "index": "tmp_2",
                       "ranges": ["(0,020200224144839) <= (rc_bot,rc_timestamp)"],
                       "rowid_ordered": false,
                       "using_mrr": false,
                       "index_only": false,
                       "rows": 405574,
                       "cost": 508110,
                       "chosen": false,
                       "cause": "cost"
                     },
                     {
                       "index": "tmp_3",
                       "ranges": [
                         "(6,620200224144839) <= (rc_namespace,rc_timestamp)",
                         "(7,720200224144839) <= (rc_namespace,rc_timestamp)"
                       ],
                       "rowid_ordered": false,
                       "using_mrr": false,
                       "index_only": false,
                       "rows": 957,
                       "cost": 1201,
                       "chosen": true
 
           "considered_execution_plans": [
             {
               "plan_prefix": [],
               "table": "recentchanges",
               "best_access_path": {
                 "considered_access_paths": [
                   {
                     "access_type": "ref",
                     "index": "tmp_2",
                     "rows": 4.27e6,
                     "cost": 440644,
                     "chosen": true
                   },

Forcing index tmp_3 on 10.4 shows the same result than on 10.1 and a lot faster query 12 seconds vs 0.02 query runtime even though it does filesorting

 
 
+------+--------------------+--------------------+--------+-------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+------+----------------------------------------------------+
| id   | select_type        | table              | type   | possible_keys                                         | key                   | key_len | ref                                                                   | rows | Extra                                              |
+------+--------------------+--------------------+--------+-------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+------+----------------------------------------------------+
|    1 | PRIMARY            | recentchanges      | range  | tmp_3                                                 | tmp_3                 | 20      | NULL                                                                  | 962  | Using index condition; Using where; Using filesort |
|    1 | PRIMARY            | watchlist          | eq_ref | wl_user,namespace_title,wl_user_notificationtimestamp | wl_user               | 265     | const,enwiki.recentchanges.rc_namespace,enwiki.recentchanges.rc_title | 1    |                                                    |
|    1 | PRIMARY            | actor_rc_user      | eq_ref | PRIMARY,actor_user                                    | PRIMARY               | 8       | enwiki.recentchanges.rc_actor                                         | 1    |                                                    |
|    1 | PRIMARY            | user               | eq_ref | PRIMARY                                               | PRIMARY               | 4       | enwiki.actor_rc_user.actor_user                                       | 1    | Using where                                        |
|    1 | PRIMARY            | page               | eq_ref | PRIMARY                                               | PRIMARY               | 4       | enwiki.recentchanges.rc_cur_id                                        | 1    | Using where                                        |
|    1 | PRIMARY            | flaggedpages       | eq_ref | PRIMARY                                               | PRIMARY               | 4       | enwiki.recentchanges.rc_cur_id                                        | 1    |                                                    |
|    1 | PRIMARY            | ores_damaging_cls  | eq_ref | oresc_rev_model_class                                 | oresc_rev_model_class | 7       | enwiki.recentchanges.rc_this_oldid,const,const                        | 1    |                                                    |
|    1 | PRIMARY            | ores_goodfaith_cls | eq_ref | oresc_rev_model_class                                 | oresc_rev_model_class | 7       | enwiki.recentchanges.rc_this_oldid,const,const                        | 1    |                                                    |
|    1 | PRIMARY            | comment_rc_comment | eq_ref | PRIMARY                                               | PRIMARY               | 8       | enwiki.recentchanges.rc_comment_id                                    | 1    |                                                    |
|    2 | DEPENDENT SUBQUERY | change_tag         | ref    | change_tag_rc_tag_id,change_tag_tag_id_id             | change_tag_rc_tag_id  | 5       | enwiki.recentchanges.rc_id                                            | 1    | Using index                                        |
|    2 | DEPENDENT SUBQUERY | change_tag_def     | eq_ref | PRIMARY                                               | PRIMARY               | 4       | enwiki.change_tag.ct_tag_id                                           | 1    |                                                    |
+------+--------------------+--------------------+--------+-------------------------------------------------------+-----------------------+---------+-----------------------------------------------------------------------+------+----------------------------------------------------+
11 rows in set (0.01 sec)

This is the ANALYZE JSON format output on a normal run

"query_block": {
   "select_id": 1,
   "r_loops": 1,
   "r_total_time_ms": 12905,
   "table": {
     "table_name": "recentchanges",
     "access_type": "ref",
     "possible_keys": [
       "rc_timestamp",
       "new_name_timestamp",
       "tmp_2",
       "tmp_3",
       "rc_name_type_patrolled_timestamp",
       "rc_ns_actor",
       "rc_actor",
       "rc_namespace_title_timestamp",
       "rc_this_oldid"
     ],
     "key": "tmp_2",
     "key_length": "1",
     "used_key_parts": ["rc_bot"],
     "ref": ["const"],
     "r_loops": 1,
     "rows": 4274159,
     "r_rows": 7.28e6,
     "r_total_time_ms": 11593,
     "filtered": 0.0113,
     "r_filtered": 0.0091,
     "attached_condition": "recentchanges.rc_b

Hinting the optimizer to USE INDEX (tmp_3)

"query_block": {
   "select_id": 1,
   "r_loops": 1,
   "r_total_time_ms": 13.483,
   "read_sorted_file": {
     "r_rows": 663,
     "filesort": {
       "sort_key": "recentchanges.rc_timestamp desc",
       "r_loops": 1,
       "r_total_time_ms": 5.9206,
       "r_used_priority_queue": false,
       "r_output_rows": 663,
       "r_buffer_size": "2047Kb",
       "table": {
         "table_name": "recentchanges",
         "access_type": "range",
         "possible_keys": ["tmp_3"],
         "key": "tmp_3",
         "key_length": "20",
         "used_key_parts": ["rc_namespace", "rc_timestamp"],
         "r_loops": 1,
         "rows": 967,
         "r_rows": 967,
         "r_total_time_ms": 6.7351,
         "filtered": 83.716,
         "r_filtered": 68.563,
         "index_condition": "recentchanges.rc_namespace in ('6','7') and recentchanges.rc_timestamp >= '20200224144839'",
         "attached_condition": "recentchanges.rc_bot = 0 and recentchanges.rc_type <> 6 and recentchanges.rc_source <> 'wb' and recentchanges.rc_new in (0,1)"
       }

Tables definition:

*************************** 1. row ***************************
       Table: recentchanges
Create Table: CREATE TABLE `recentchanges` (
  `rc_id` int(8) NOT NULL AUTO_INCREMENT,
  `rc_timestamp` varbinary(14) NOT NULL DEFAULT '',
  `rc_actor` bigint(20) unsigned NOT NULL,
  `rc_namespace` int(11) NOT NULL DEFAULT 0,
  `rc_title` varbinary(255) NOT NULL DEFAULT '',
  `rc_comment_id` bigint(20) unsigned NOT NULL,
  `rc_minor` tinyint(3) unsigned NOT NULL DEFAULT 0,
  `rc_bot` tinyint(3) unsigned NOT NULL DEFAULT 0,
  `rc_new` tinyint(3) unsigned NOT NULL DEFAULT 0,
  `rc_cur_id` int(10) unsigned NOT NULL DEFAULT 0,
  `rc_this_oldid` int(10) unsigned NOT NULL DEFAULT 0,
  `rc_last_oldid` int(10) unsigned NOT NULL DEFAULT 0,
  `rc_type` tinyint(3) unsigned NOT NULL DEFAULT 0,
  `rc_source` varbinary(16) NOT NULL DEFAULT '',
  `rc_patrolled` tinyint(3) unsigned NOT NULL DEFAULT 0,
  `rc_ip` varbinary(40) NOT NULL DEFAULT '',
  `rc_old_len` int(10) DEFAULT NULL,
  `rc_new_len` int(10) DEFAULT NULL,
  `rc_deleted` tinyint(1) unsigned NOT NULL DEFAULT 0,
  `rc_logid` int(10) unsigned NOT NULL DEFAULT 0,
  `rc_log_type` varbinary(255) DEFAULT NULL,
  `rc_log_action` varbinary(255) DEFAULT NULL,
  `rc_params` blob NOT NULL,
  PRIMARY KEY (`rc_id`),
  KEY `rc_timestamp` (`rc_timestamp`),
  KEY `rc_cur_id` (`rc_cur_id`),
  KEY `new_name_timestamp` (`rc_new`,`rc_namespace`,`rc_timestamp`),
  KEY `rc_ip` (`rc_ip`),
  KEY `tmp_2` (`rc_bot`,`rc_timestamp`),
  KEY `tmp_3` (`rc_namespace`,`rc_timestamp`),
  KEY `rc_name_type_patrolled_timestamp` (`rc_namespace`,`rc_type`,`rc_patrolled`,`rc_timestamp`),
  KEY `rc_ns_actor` (`rc_namespace`,`rc_actor`),
  KEY `rc_actor` (`rc_actor`,`rc_timestamp`),
  KEY `rc_namespace_title_timestamp` (`rc_namespace`,`rc_title`,`rc_timestamp`),
  KEY `rc_this_oldid` (`rc_this_oldid`)
) ENGINE=InnoDB AUTO_INCREMENT=1234530860 DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: watchlist
Create Table: CREATE TABLE `watchlist` (
  `wl_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `wl_user` int(5) unsigned NOT NULL DEFAULT 0,
  `wl_namespace` int(11) NOT NULL DEFAULT 0,
  `wl_title` varbinary(255) NOT NULL DEFAULT '',
  `wl_notificationtimestamp` varbinary(14) DEFAULT NULL,
  PRIMARY KEY (`wl_id`),
  UNIQUE KEY `wl_user` (`wl_user`,`wl_namespace`,`wl_title`),
  KEY `namespace_title` (`wl_namespace`,`wl_title`),
  KEY `wl_user_notificationtimestamp` (`wl_user`,`wl_notificationtimestamp`)
) ENGINE=InnoDB AUTO_INCREMENT=244510744 DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: actor
Create Table: CREATE TABLE `actor` (
  `actor_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `actor_user` int(10) unsigned DEFAULT NULL,
  `actor_name` varbinary(255) NOT NULL,
  PRIMARY KEY (`actor_id`),
  UNIQUE KEY `actor_name` (`actor_name`),
  UNIQUE KEY `actor_user` (`actor_user`)
) ENGINE=InnoDB AUTO_INCREMENT=201849245 DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: user
Create Table: CREATE TABLE `user` (
  `user_id` int(5) unsigned NOT NULL AUTO_INCREMENT,
  `user_name` varbinary(255) NOT NULL DEFAULT '',
  `user_real_name` varbinary(255) NOT NULL DEFAULT '',
  `user_password` tinyblob NOT NULL,
  `user_newpassword` tinyblob NOT NULL,
  `user_email` tinyblob NOT NULL,
  `user_touched` varbinary(14) NOT NULL DEFAULT '',
  `user_token` varbinary(32) NOT NULL DEFAULT '',
  `user_email_authenticated` varbinary(14) DEFAULT NULL,
  `user_email_token` varbinary(32) DEFAULT NULL,
  `user_email_token_expires` varbinary(14) DEFAULT NULL,
  `user_registration` varbinary(14) DEFAULT NULL,
  `user_newpass_time` varbinary(14) DEFAULT NULL,
  `user_editcount` int(11) DEFAULT NULL,
  `user_password_expires` varbinary(14) DEFAULT NULL,
  PRIMARY KEY (`user_id`),
  UNIQUE KEY `user_name` (`user_name`),
  KEY `user_email_token` (`user_email_token`),
  KEY `user_email` (`user_email`(50))
) ENGINE=InnoDB AUTO_INCREMENT=38630081 DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: page
Create Table: CREATE TABLE `page` (
  `page_id` int(8) unsigned NOT NULL AUTO_INCREMENT,
  `page_namespace` int(11) NOT NULL DEFAULT 0,
  `page_title` varbinary(255) NOT NULL DEFAULT '',
  `page_restrictions` tinyblob NOT NULL,
  `page_is_redirect` tinyint(1) unsigned NOT NULL DEFAULT 0,
  `page_is_new` tinyint(1) unsigned NOT NULL DEFAULT 0,
  `page_random` double unsigned NOT NULL DEFAULT 0,
  `page_touched` varbinary(14) NOT NULL DEFAULT '',
  `page_links_updated` varbinary(14) DEFAULT NULL,
  `page_latest` int(8) unsigned NOT NULL DEFAULT 0,
  `page_len` int(8) unsigned NOT NULL DEFAULT 0,
  `page_content_model` varbinary(32) DEFAULT NULL,
  `page_lang` varbinary(35) DEFAULT NULL,
  PRIMARY KEY (`page_id`),
  UNIQUE KEY `name_title` (`page_namespace`,`page_title`),
  KEY `page_random` (`page_random`),
  KEY `page_len` (`page_len`),
  KEY `page_redirect_namespace_len` (`page_is_redirect`,`page_namespace`,`page_len`)
) ENGINE=InnoDB AUTO_INCREMENT=63204770 DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: flaggedpages
Create Table: CREATE TABLE `flaggedpages` (
  `fp_page_id` int(10) unsigned NOT NULL,
  `fp_reviewed` tinyint(1) NOT NULL DEFAULT 0,
  `fp_pending_since` binary(14) DEFAULT NULL,
  `fp_stable` int(10) unsigned NOT NULL,
  `fp_quality` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`fp_page_id`),
  KEY `fp_reviewed_page` (`fp_reviewed`,`fp_page_id`),
  KEY `fp_quality_page` (`fp_quality`,`fp_page_id`),
  KEY `fp_pending_since` (`fp_pending_since`)
) ENGINE=InnoDB DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: ores_classification
Create Table: CREATE TABLE `ores_classification` (
  `oresc_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `oresc_rev` int(10) unsigned NOT NULL,
  `oresc_model` smallint(6) NOT NULL,
  `oresc_class` tinyint(4) NOT NULL,
  `oresc_probability` decimal(3,3) NOT NULL,
  `oresc_is_predicted` tinyint(1) NOT NULL,
  PRIMARY KEY (`oresc_id`),
  UNIQUE KEY `oresc_rev_model_class` (`oresc_rev`,`oresc_model`,`oresc_class`)
) ENGINE=InnoDB AUTO_INCREMENT=505922062 DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: comment
Create Table: CREATE TABLE `comment` (
  `comment_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `comment_hash` int(11) NOT NULL,
  `comment_text` blob NOT NULL,
  `comment_data` blob DEFAULT NULL,
  PRIMARY KEY (`comment_id`),
  KEY `comment_hash` (`comment_hash`)
) ENGINE=InnoDB AUTO_INCREMENT=311512696 DEFAULT CHARSET=binary
*************************** 1. row ***************************
       Table: change_tag
Create Table: CREATE TABLE `change_tag` (
  `ct_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `ct_rc_id` int(11) DEFAULT NULL,
  `ct_log_id` int(10) unsigned DEFAULT NULL,
  `ct_rev_id` int(10) unsigned DEFAULT NULL,
  `ct_params` blob DEFAULT NULL,
  `ct_tag_id` int(10) unsigned NOT NULL,
  PRIMARY KEY (`ct_id`),
  UNIQUE KEY `change_tag_rc_tag_id` (`ct_rc_id`,`ct_tag_id`),
  UNIQUE KEY `change_tag_log_tag_id` (`ct_log_id`,`ct_tag_id`),
  UNIQUE KEY `change_tag_rev_tag_id` (`ct_rev_id`,`ct_tag_id`),
  KEY `change_tag_tag_id_id` (`ct_tag_id`,`ct_rc_id`,`ct_rev_id`,`ct_log_id`)
) ENGINE=InnoDB AUTO_INCREMENT=106682245 DEFAULT CHARSET=binary



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

(Setting fixVersion to be 10.4, for now. I'm not actually sure if we'll be able to fix this in 10.4, but lets be optimistic)

Comment by Sergei Petrunia [ 2020-03-18 ]

Note to self:
the way the ranges got printed in the optimizer trace looks odd:

     "ranges": [
       "(6,620200224144839) <= (rc_namespace,rc_timestamp)",
       "(7,720200224144839) <= (rc_namespace,rc_timestamp)"
     ],

will look at this in a separate MDEV.

Comment by Sergei Petrunia [ 2020-09-26 ]

Analysis:

The join orders are the same in both cases. The difference is in the first table, recentchanges

  • The "good" query plan uses range access on index tmp_3 and filesort. rows=958
  • The "bad" query plan uses index tmp_2, ref(const) access. rows=4,274,159

Index definitions:

  KEY tmp_2 (rc_bot,rc_timestamp),
  KEY tmp_3 (rc_namespace,rc_timestamp),

The query has

ORDER BY rc_timestamp DESC LIMIT 500

Part of the WHERE clause that refers to the `recentchanges` table:

  rc_bot = 0 AND 
  rc_type != 6 AND 
  rc_source != 'wb' AND 
  rc_namespace IN ('6', '7') AND 
  rc_timestamp >= '20200224144839' AND 
  rc_new IN (0, 1) 

Index tmp_3 doesn't match the ORDER BY clause (and so needs filesort).

There is rc_bot=1, with which index tmp_2 matches the ORDER BY clause.
But the question is, how soon the optimizer will find #LIMIT matches when scanning it.

We don't have information about the selectivity of each part of the WHERE, but
we know that

rc_namespace IN ('6', '7')

is already very selective.

Looking at the ANALYZE output:

   "table": {
     "table_name": "recentchanges",
     "access_type": "ref",
     "possible_keys": [...  ],
     "key": "tmp_2",
     ...
     "rows": 4 274 159,
     "r_rows": 7.28e6,
     "r_total_time_ms": 11593,
     "filtered": 0.0113,
     "r_filtered": 0.0091,

one can see that we had to evaluate 7.2M rows before finding #LIMIT matches.
(Looking at the other lines in the EXPLAIN output, I can see that fanout=1.0 for all tables).
Indeed:

r_rows * r_filtered * 100% = 7.28e6 * 0.0091 / 100 = 662.48

The optimizer's idea about condition selectivity is actually close to reality:

     "filtered": 0.0113,
     "r_filtered": 0.0091,

Comment by Sergei Petrunia [ 2020-09-26 ]

MDEV-18079 is about creating a general approach to address issues like this.

But can this case be solved only with MDEV-18079 (which is a big feature), or there is a smaller and simpler solution? This is not clear, yet.

Comment by Sergei Petrunia [ 2020-09-26 ]

An odd thing:

The posted optimizer trace is shows:

{
           "index": "tmp_2",
           "ranges": ["(0,020200224144839) <= (rc_bot,rc_timestamp)"],
           "rowid_ordered": false,
           "using_mrr": false,
           "index_only": false,
           "rows": 405574,
           "cost": 508110,
           "chosen": false,
           "cause": "cost"

while ANALYZE FORMAT=JSON output shows:

   "table": {
     "table_name": "recentchanges",
     "access_type": "ref",
     ...
     "key": "tmp_2",
     "key_length": "1",
     "used_key_parts": ["rc_bot"],
     "ref": ["const"],
     "r_loops": 1,
     "rows": 4274159,

Note that it is using ref access over one key part, while there is a range access over two key parts.

For ref access, rows=4.2M, while for range it would be 405K - 10x less!

Comment by Sergei Petrunia [ 2020-10-03 ]

I was able to construct a testcase where I am observing a similar effect:

The regular query uses:

    "table": {
      "table_name": "recentchanges",
      "access_type": "ref",
      "possible_keys": [ ...  ],
      "key": "tmp_2",
      "key_length": "1",
      "used_key_parts": ["rc_bot"],
      "ref": ["const"],
      "rows": 498617,
      "filtered": 0.1003,
      "attached_condition": "recentchanges.rc_bot <=> 0 and recentchanges.rc_type <> 6 and recentchanges.rc_namespace in ('6','7') and recentchanges.rc_timestamp >= 900000 and recentchanges.rc_new in (0,1)"
    },

while a query with force index(tmp_2) uses:

  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "recentchanges",
      "access_type": "range",
      "possible_keys": ["tmp_2"],
      "key": "tmp_2",
      "key_length": "5",
      "used_key_parts": ["rc_bot", "rc_timestamp"],
      "rows": 202734,
      "filtered": 20.433,
      "attached_condition": "recentchanges.rc_bot = 0 and recentchanges.rc_type <> 6 and recentchanges.rc_namespace in ('6','7') and recentchanges.rc_timestamp >= 900000 and recentchanges.rc_new in (0,1)"
    },

I was able to achieve this after I've collected EITS statistics for column rc.

The effect doesn't seem to have anything to do with ORDER BY ... LIMIT optimization. Optimizer trace shows that the choice to use ref(tmp_2) instead of range access on the same index is made already in best_access_path(). The cause is most likely the issue with wrong selectivity calculation for multi-part keys (known as MDEV-20740 and related)

Comment by Sergei Petrunia [ 2020-10-03 ]

It would be helpful to get the full optimizer trace contents of the original query (Most needed) and the query with the USE INDEX hint (lower priority but would be useful too).

marostegui, is it possible to get those? (I see the condition on rc_timestamp is time-dependent so it might need to be adjusted to still see the effect?)

Comment by Sergei Petrunia [ 2020-10-03 ]

Another thing: I suspect setting @@optimizer_use_condition_selectivity=1 will fix this issue but it might negatively affect the query plan choices for other queries.

Comment by Manuel Arostegui [ 2020-10-22 ]

I have been unable to paste such a long comment on Jira, as it was complaining about exceeding the number of allowed characters.
It is pasted here instead: https://phabricator.wikimedia.org/P13051

Comment by Sergei Petrunia [ 2020-11-02 ]

marostegui, thanks for the traces!

Looking at the EXPLAINs first:

Query With hint:

id:            1
select_type:   PRIMARY
table:         recentchanges
type:          range
possible_keys: tmp_3
key:           tmp_3
key_len:       20
ref:           NULL
rows:          141493
Extra:         Using index condition; Using where; Using filesort

Query Without hint:

id:            1
select_type:   PRIMARY
table:         recentchanges
type:          ref
possible_keys: rc_timestamp,new_name_timestamp,rc_name_type_patrolled_timestamp,rc_namespace_title_timestamp,rc_ns_actor,rc_actor,rc_this_oldid,tmp_2,tmp_3
key:           tmp_2
key_len:       1
ref:           const
rows:          4845459
Extra:         Using where

Comment by Sergei Petrunia [ 2020-11-02 ]

Now, reading the trace of query without the hint:

analyzing_range_alternatives": {
  "range_scan_alternatives": [
    {
      "index": "tmp_2",
      "ranges": [
        "(0,20200224144839) <= (rc_bot,rc_timestamp) <= (0)"
      ],
      "rowid_ordered": false,
      "using_mrr": true,
      "index_only": false,
      "rows": 4 845 688,
      "cost": 5.2e6,
      "chosen": false,
      "cause": "cost"
    },

Note: the right endpoint of the range looks odd (it should actually be something like (0, +inf))", but this is likely an error in the code that prints the trace.

    {
      "index": "tmp_3",
      "ranges": [
        "(6,20200224144839) <= (rc_namespace,rc_timestamp) <= (6)",
        "(7,20200224144839) <= (rc_namespace,rc_timestamp) <= (7)"
      ],
      "rowid_ordered": false,
      "using_mrr": false,
      "index_only": false,
      "rows": 141 783,
      "cost": 177 548,
      "chosen": false,
      "cause": "cost"
    }

The best key for range access was neither tmp_2 nor tmp_3:

  "chosen_range_access_summary": {
    "range_access_plan": {
      "type": "range_scan",
      "index": "rc_name_type_patrolled_timestamp",
      "rows": 130655,
      "ranges": [
        "(6) <= (rc_namespace,rc_type) < (6,6)",
        "(6,6) < (rc_namespace,rc_type) <= (6)",
        "(7) <= (rc_namespace,rc_type) < (7,6)",
        "(7,6) < (rc_namespace,rc_type) <= (7)"
      ]
    },
    "rows_for_plan": 130 655,
    "cost_for_plan": 163 640,
    "chosen": true
  }

Then, in the join optimizer:

"considered_execution_plans": [
  {
    "plan_prefix": [],
    "table": "recentchanges",

    "best_access_path": {
      "considered_access_paths": [
        {
          "access_type": "ref",
          "index": "tmp_2",
          "used_range_estimates": true,
          "rows": 4.85e6,
          "cost": 527236,
          "chosen": true
        },

        {
          "access_type": "range",
          "resulting_rows": 6.9e8,
          "cost": 2e308,
          "chosen": false
        }

Note the cost: 2e308. This can be due to the (TODO: lookup MDEV#).

      "chosen_access_method": {
        "type": "ref",
        "records": 4.85e6,
        "cost": 527236,
        "uses_join_buffering": false
      }
    },
    "rows_for_plan": 4.85e6,
    "cost_for_plan": 1.5e6,
    "selectivity": 0.0154,

and it picks a ref access which is clearly more expensive than any range access.

Query with the hint has got this:

"considered_execution_plans": [
  {
    "plan_prefix": [],
    "table": "recentchanges",
    "best_access_path": {
      "considered_access_paths": [
        {
          "access_type": "range",
          "resulting_rows": 141521,
          "cost": 177220,
          "chosen": true
        }
      ],
      "chosen_access_method": {
        "type": "range",
        "records": 141521,
        "cost": 177220,
        "uses_join_buffering": false
      }
    },

As for the ORDER BY optimization, the trace for the query with hint has this:

  "reconsidering_access_paths_for_index_ordering": {
    "clause": "ORDER BY",
    "fanout": 1,
    "read_time": 177220,
    "table": "recentchanges",
    "rows_estimation": 141521,
    "possible_keys": [
      ...
      {
        "index": "tmp_2",
        "can_resolve_order": false,
        "cause": "not usable index for the query"
      },
      {
        "index": "tmp_3",
        "can_resolve_order": false,
        "cause": "order can not be resolved by key"
      }

While the query without hint doesn't have a reconsidering_access_paths_for_index_ordering node.

Comment by Sergei Petrunia [ 2020-11-06 ]

(Ok the issue with ranges looking odd in printout is filed as MDEV-24157. It's a minor part of this issue, though) (In case anybody is wondering, MySQL doesn't print ranges correctly either, and in greater number of cases - see e.g. https://bugs.mysql.com/bug.php?id=95824)
UPD Maybe this is not a bug after all, misread the issue.

Comment by Sergei Petrunia [ 2020-11-06 ]

Back to the main issue.

marostegui, I think the cause of this behavior is this one: https://jira.mariadb.org/browse/MDEV-23707

and the only way out currently is to use a hint or set optimizer_use_condition_selectivity to 1 (the default value before the 10.4. In 10.4 it was changed to 4). This may have a negative effect though, as this will disable use of condition selectivity.

We do intend to fix MDEV-23707 but I can't give a date ATM.

Comment by Manuel Arostegui [ 2020-11-10 ]

Thanks for taking a look. If you believe this is a case of MDEV-23707, can we include this one on that list?.
That meta task is set for 10.6, do you think that's still the case or any chances it can be done on 10.5? (I assume 10.4 is not realistic).
For now we won't touch

optimizer_use_condition_selectivity

as this is not a super frequent query and it might have negative impact on the other queries arriving to that host.

Thank you!

Comment by Manuel Arostegui [ 2022-03-14 ]

This seems to still happen with 10.6.7

Comment by Julien Fritsch [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

Comment by JiraAutomate [ 2023-12-05 ]

Automated message:
----------------------------
Since this issue has not been updated since 6 weeks, it's time to move it back to Stalled.

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