Bug #81672 Less optimal index is chosen, index length does impact cost
Submitted: 1 Jun 2016 9:04 Modified: 21 Sep 2016 15:11
Reporter: Kenny Gryp Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.6 OS:Any
Assigned to: CPU Architecture:Any
Tags: Optimizer

[1 Jun 2016 9:04] Kenny Gryp 
Description:

A query which selects data col1 and col2 prefers an index on (col1,col2,col3,col4) instead of (col1,col2,col3).

How to repeat:

We have a table named 'audits':

  mysql> show create table audits\G
  *************************** 1. row ***************************
         Table: audits
  Create Table: CREATE TABLE `audits` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `auditable_id` int(11) NOT NULL,
    `auditable_type` varchar(255) COLLATE utf8_unicode_ci NOT NULL,
    `client_application_id` int(11) DEFAULT NULL,
    `consumer_key` varchar(50) COLLATE utf8_unicode_ci DEFAULT NULL,
    `user_id` int(11) DEFAULT NULL,
    `action` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
    `created_at` datetime NOT NULL,
    PRIMARY KEY (`id`),
    KEY `index_audits_on_auditable_action_created` (`auditable_id`,`auditable_type`,`action`,`created_at`),
    KEY `index_audits_on_consumer_key_auditable_and_action` (`consumer_key`,`auditable_id`,`auditable_type`,`action`),
    KEY `index_audits_on_auditable_id_and_auditable_type_and_action` (`auditable_id`,`auditable_type`,`action`)
  ) ENGINE=InnoDB AUTO_INCREMENT=393162038 DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci
  1 row in set (0.00 sec)

We have a query filtering on 'auditable_id' and 'auditable_type':

  mysql> EXPLAIN /*!50100 PARTITIONS*/ ->
  SELECT `audits`.*
  FROM `audits`
  WHERE (`audits`.`auditable_id` IN (XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX,
                                     XXXX)
         AND `audits`.`auditable_type` = 'Track')\G
  *************************** 1. row ***************************
             id: 1
    select_type: SIMPLE
          table: audits
     partitions: NULL
           type: range
  possible_keys: index_audits_on_auditable_action_created,index_audits_on_auditable_id_and_auditable_type_and_action
            key: index_audits_on_auditable_action_created
        key_len: 771
            ref: NULL
           rows: 20
          Extra: Using index condition
  1 row in set (0.00 sec)

The query chooses the 'index_audits_on_auditable_action_created' index, however the 'index_audits_on_auditable_id_and_auditable_type_and_action' index is not chosen, even though the index size is smaller (and therefore the cost should be smaller too).

Here's EXPLAIN FORMAT=JSON:

  *************************** 1. row ***************************
  EXPLAIN: {
    "query_block": {
      "select_id": 1,
      "table": {
        "table_name": "audits",
        "access_type": "range",
        "possible_keys": [
          "index_audits_on_auditable_action_created",
          "index_audits_on_auditable_id_and_auditable_type_and_action"
        ],
        "key": "index_audits_on_auditable_action_created",
        "used_key_parts": [
          "auditable_id",
          "auditable_type"
        ],
        "key_length": "771",
        "rows": 20,
        "filtered": 100,
        "index_condition": "((`some_database`.`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
  XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`some_database`.`audits`.`auditable_type` = 'Track'))"
      }
    }
  }
  1 row in set, 1 warning (0.00 sec)

Optimizer Trace:

mysql> select * from information_schema.OPTIMIZER_TRACE\G
*************************** 1. row ***************************
                            QUERY: EXPLAIN FORMAT=json SELECT `audits`.* FROM `audits` WHERE (`audits`.`auditable_id` IN (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX ) and `audits`.`auditable_type` = 'Track')
                            TRACE: {
  "steps": [
    {
      "join_preparation": {
        "select#": 1,
        "steps": [
          {
            "expanded_query": "/* select#1 */ select `audits`.`id` AS `id`,`audits`.`auditable_id` AS `auditable_id`,`audits`.`auditable_type` AS `auditable_type`,`audits`.`client_application_id` AS
 `client_application_id`,`audits`.`consumer_key` AS `consumer_key`,`audits`.`user_id` AS `user_id`,`audits`.`action` AS `action`,`audits`.`created_at` AS `created_at` from `audits` where ((`audits`.
`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
,XXXX)) and (`audits`.`auditable_type` = 'Track'))"
          }
        ]
      }
    },
    {
      "join_optimization": {
        "select#": 1,
        "steps": [
          {
            "condition_processing": {
              "condition": "WHERE",
              "original_condition": "((`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`audits`.`auditable_type` = 'Track'))",
              "steps": [
                {
                  "transformation": "equality_propagation",
                  "resulting_condition": "((`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`audits`.`auditable_type` = 'Track'))"
                },
                {
                  "transformation": "constant_propagation",
                  "resulting_condition": "((`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`audits`.`auditable_type` = 'Track'))"
                },
                {
                  "transformation": "trivial_condition_removal",
                  "resulting_condition": "((`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`audits`.`auditable_type` = 'Track'))"
                }
              ]
            }
          },
          {
            "table_dependencies": [
              {
                "table": "`audits`",
                "row_may_be_null": false,
                "map_bit": 0,
                "depends_on_map_bits": [
                ]
              }
            ]
          },
          {
            "ref_optimizer_key_uses": [
            ]
          },
          {
            "rows_estimation": [
              {
                "table": "`audits`",
                "range_analysis": {
                  "table_scan": {
                    "rows": 387609736,
                    "cost": 7.92e7
                  },
                  "potential_range_indices": [
                    {
                      "index": "PRIMARY",
                      "usable": false,
                      "cause": "not_applicable"
                    },
                    {
                      "index": "index_audits_on_auditable_action_created",
                      "usable": true,
                      "key_parts": [
                        "auditable_id",
                        "auditable_type",
                        "action",
                        "created_at",
                        "id"
                      ]
                    },
                    {
                      "index": "index_audits_on_consumer_key_auditable_and_action",
                      "usable": false,
                      "cause": "not_applicable"
                    },
                    {
                      "index": "index_audits_on_auditable_id_and_auditable_type_and_action",
                      "usable": true,
                      "key_parts": [
                        "auditable_id",
                        "auditable_type",
                        "action",
                        "id"
                      ]
                    }
                  ],
                  "setup_range_conditions": [
                  ],
                  "group_index_range": {
                    "chosen": false,
                    "cause": "not_group_by_or_distinct"
                  },
                  "analyzing_range_alternatives": {
                    "range_scan_alternatives": [
                      {
                        "index": "index_audits_on_auditable_action_created",
                        "ranges": [
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track"
                        ],
                        "index_dives_for_eq_ranges": false,
                        "rowid_ordered": false,
                        "using_mrr": false,
                        "index_only": false,
                        "rows": 20,
                        "cost": 44.01,
                        "chosen": true
                      },
                      {
                        "index": "index_audits_on_auditable_id_and_auditable_type_and_action",
                        "ranges": [
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                          "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track"
                        ],
                        "index_dives_for_eq_ranges": false,
                        "rowid_ordered": false,
                        "using_mrr": false,
                        "index_only": false,
                        "rows": 20,
                        "cost": 44.01,
                        "chosen": false,
                        "cause": "cost"
                      }
                    ],
                    "analyzing_roworder_intersect": {
                      "usable": false,
                      "cause": "too_few_roworder_scans"
                    }
                  },
                  "chosen_range_access_summary": {
                    "range_access_plan": {
                      "type": "range_scan",
                      "index": "index_audits_on_auditable_action_created",
                      "rows": 20,
                      "ranges": [
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track",
                        "XXXX <= auditable_id <= XXXX AND Track <= auditable_type <= Track"
                      ]
                    },
                    "rows_for_plan": 20,
                    "cost_for_plan": 44.01,
                    "chosen": true
                  }
                }
              }
            ]
          },
          {
            "considered_execution_plans": [
              {
                "plan_prefix": [
                ],
                "table": "`audits`",
                "best_access_path": {
                  "considered_access_paths": [
                    {
                      "access_type": "range",
                      "rows": 20,
                      "cost": 48.01,
                      "chosen": true
                    }
                  ]
                },
                "cost_for_plan": 48.01,
                "rows_for_plan": 20,
                "chosen": true
              }
            ]
          },
          {
            "attaching_conditions_to_tables": {
              "original_condition": "((`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`audits`.`auditable_type` = 'Track'))",
              "attached_conditions_computation": [
              ],
              "attached_conditions_summary": [
                {
                  "table": "`audits`",
                  "attached": "((`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`audits`.`auditable_type` = 'Track'))"
                }
              ]
            }
          },
          {
            "refine_plan": [
              {
                "table": "`audits`",
                "pushed_index_condition": "((`audits`.`auditable_id` in (XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX
XXXX,XXXX,XXXX,XXXX,XXXX,XXXX,XXXX)) and (`audits`.`auditable_type` = 'Track'))",
                "table_condition_attached": null,
                "access_type": "range"
              }
            ]
          }
        ]
      }
    },
    {
      "join_explain": {
        "select#": 1,
        "steps": [
        ]
      }
    }
  ]
}
MISSING_BYTES_BEYOND_MAX_MEM_SIZE: 0
          INSUFFICIENT_PRIVILEGES: 0
1 row in set (0.00 sec)

So the index cost is the same, but the 'better index which is smaller in size' is not chosen because of 'cost' according to the optimizer trace.

Tue May 31 16:39:51 2016 - root@localhost [some_database]> show indexes from audits ;
+--------+------------+------------------------------------------------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+
| Table  | Non_unique | Key_name                                                   | Seq_in_index | Column_name    | Collation | Cardinality | Sub_part | Packed | Null | Index_type |
+--------+------------+------------------------------------------------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+
| audits | 0          | PRIMARY                                                    | 1            | id             | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_auditable_action_created                   | 1            | auditable_id   | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_auditable_action_created                   | 2            | auditable_type | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_auditable_action_created                   | 3            | action         | A         | 387613874   | NULL     | NULL   | YES  | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_auditable_action_created                   | 4            | created_at     | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_consumer_key_auditable_and_action          | 1            | consumer_key   | A         | 93762       | NULL     | NULL   | YES  | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_consumer_key_auditable_and_action          | 2            | auditable_id   | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_consumer_key_auditable_and_action          | 3            | auditable_type | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_consumer_key_auditable_and_action          | 4            | action         | A         | 387613874   | NULL     | NULL   | YES  | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_auditable_id_and_auditable_type_and_action | 1            | auditable_id   | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_auditable_id_and_auditable_type_and_action | 2            | auditable_type | A         | 387613874   | NULL     | NULL   |      | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
| audits | 1          | index_audits_on_auditable_id_and_auditable_type_and_action | 3            | action         | A         | 387613874   | NULL     | NULL   | YES  | BTREE      |
|        |            |                                                            |              |                |           |             |          |        |      |            |
+--------+------------+------------------------------------------------------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+
---------+
12 rows in set (0.00 sec)

Index Cardinalities look good.

Suggested fix:
It seems like the first matching index is used.

The fix would be to choose the most optimal index (including the index length)
[1 Jun 2016 15:02] MySQL Verification Team 
Hi!

Total length of the index is less important that then number of rows matched.

The query chooses the 'index_audits_on_auditable_action_created' index, which hits 20 rows entries.

How many rows are selected when  'index_audits_on_auditable_id_and_auditable_type_and_action'
index is chosen.

If that amount is 20 or less, then please try latest 5.7 release as there were many bug fixes between 5.6 and latest 5.7, and we would not like to explore already fixed bugs.
[2 Jul 2016 1:00] Bugs System 
No feedback was provided for this bug for over a month, so it is
being suspended automatically. If you are able to provide the
information that was originally requested, please do so and change
the status of the bug back to "Open".
[21 Sep 2016 15:11] Kenny Gryp 
I think it can be closed as duplicate of #83071

I was able to prove the same situations where indexes have the same cost (but should not have the same cost) with a reproducible test case in a much more simpler schema on smaller dataset http://bugs.mysql.com/bug.php?id=83071.