MySQL Bugs: #88181: Another example of optimizer choosing ref over range when range is faster

Bug #88181	Another example of optimizer choosing ref over range when range is faster
Submitted:	23 Oct 2017 5:30	Modified:	23 Oct 2017 7:09
Reporter:	Jaime Sicam	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	5.7.20	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
Here's another example of https://bugs.mysql.com/bug.php?id=87947 but this time around it's slower because the query needs to create a sort index when using ref:

CREATE TABLE `t1` (
  `a` bigint(20) NOT NULL AUTO_INCREMENT,
  `b` bigint(20) NOT NULL,
  `c` bigint(20) NOT NULL,
  `d` bigint(20) NOT NULL,
  PRIMARY KEY (`a`),
  KEY `i1` (`b`,`a`,`c`),
  KEY `i2` (`b`,`d`)
) ENGINE=InnoDB AUTO_INCREMENT=2528215 DEFAULT CHARSET=latin1;

mysql> EXPLAIN SELECT a FROM t1 WHERE a>10 AND b=6 ORDER BY a LIMIT 1;
+----+-------------+-------+------------+-------+---------------+---------+---------+------+---------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key     | key_len | ref  | rows    | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+---------+----------+-------------+
|  1 | SIMPLE      | t1    | NULL       | range | PRIMARY,i1,i2 | PRIMARY | 8       | NULL | 1196250 |    50.00 | Using where |
+----+-------------+-------+------------+-------+---------------+---------+---------+------+---------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

The problem manifests when b is very selectable:

mysql> EXPLAIN SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1;
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref   | rows | filtered | Extra                                    |
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | ref  | PRIMARY,i1,i2 | i2   | 8       | const |  400 |    50.00 | Using where; Using index; Using filesort |
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+------------------------------------------+
1 row in set, 1 warning (0.01 sec)

mysql> SELECT b, COUNT(*) FROM t1 GROUP BY b;
+---+----------+
| b | COUNT(*) |
+---+----------+
| 6 |  2399792 |
| 7 |      400 |
+---+----------+
2 rows in set (0.33 sec)

As you can see below using i1 

+----------+------------+----------------------------------------------------------------------+
| Query_ID | Duration   | Query                                                                |
+----------+------------+----------------------------------------------------------------------+
|        1 | 0.00175875 | SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1               |
|        2 | 0.00173975 | SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1               |
|        3 | 0.00149875 | SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1               |
|        4 | 0.00073275 | SELECT a FROM t1 USE INDEX(i1) WHERE a>10 AND b=7 ORDER BY a LIMIT 1 |
|        5 | 0.00064400 | SELECT a FROM t1 USE INDEX(i1) WHERE a>10 AND b=7 ORDER BY a LIMIT 1 |
|        6 | 0.00096025 | SELECT a FROM t1 USE INDEX(i1) WHERE a>10 AND b=7 ORDER BY a LIMIT 1 |
+----------+------------+----------------------------------------------------------------------+

So, query 4-6 are faster because it doesn't need to create a sort index:

mysql> SHOW PROFILE FOR QUERY 1;
+----------------------+----------+
| Status               | Duration |
+----------------------+----------+
| starting             | 0.000174 |
| checking permissions | 0.000023 |
| Opening tables       | 0.000038 |
| init                 | 0.000064 |
| System lock          | 0.000025 |
| optimizing           | 0.000034 |
| statistics           | 0.000315 |
| preparing            | 0.000055 |
| Sorting result       | 0.000020 |
| executing            | 0.000008 |
| Sending data         | 0.000017 |
| Creating sort index  | 0.000801 |
| end                  | 0.000014 |
| query end            | 0.000022 |
| closing tables       | 0.000017 |
| freeing items        | 0.000107 |
| cleaning up          | 0.000029 |
+----------------------+----------+
17 rows in set, 1 warning (0.00 sec)

mysql> SHOW PROFILE FOR QUERY 4;
+----------------------+----------+
| Status               | Duration |
+----------------------+----------+
| starting             | 0.000155 |
| checking permissions | 0.000016 |
| Opening tables       | 0.000030 |
| init                 | 0.000052 |
| System lock          | 0.000019 |
| optimizing           | 0.000026 |
| statistics           | 0.000154 |
| preparing            | 0.000037 |
| Sorting result       | 0.000010 |
| executing            | 0.000006 |
| Sending data         | 0.000077 |
| end                  | 0.000010 |
| query end            | 0.000020 |
| closing tables       | 0.000014 |
| freeing items        | 0.000081 |
| cleaning up          | 0.000028 |
+----------------------+----------+
16 rows in set, 1 warning (0.00 sec)

How to repeat:
1. Load the dump file
mysql test < t1.sql

2. Go to mysql console and optimize table
mysql test
mysql> OPTIMIZE TABLE t1;

3. Enable profiling
SET PROFILING  = 1;

4. Run explain plans:
EXPLAIN SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1;
EXPLAIN SELECT a FROM t1 USE INDEX(i1) WHERE a>10 AND b=7 ORDER BY a LIMIT 1;

5. Run queries:
SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1;
SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1;
SELECT a FROM t1 WHERE a>10 AND b=7 ORDER BY a LIMIT 1;
SELECT a FROM t1 USE INDEX(i1) WHERE a>10 AND b=7 ORDER BY a LIMIT 1;
SELECT a FROM t1 USE INDEX(i1) WHERE a>10 AND b=7 ORDER BY a LIMIT 1;
SELECT a FROM t1 USE INDEX(i1) WHERE a>10 AND b=7 ORDER BY a LIMIT 1;

6. Check profiles:
SHOW PROFILES;
SHOW PROFILE FOR QUERY 1;
SHOW PROFILE FOR QUERY 4;

Hello Jaime Sicam,

Thank you for the report and test case.

Thanks,
Umesh

Posted by developer:
 
It seems an 0.2*#rows is added to the cost of range access.  This makes is more expensive that ref.  
This is the trace from the range optimizer:

                    "range_scan_alternatives": [
                      {
                        "index": "PRIMARY",
                        "ranges": [
                          "10 < a"
                        ],
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": true,
                        "using_mrr": false,
                        "index_only": false,
                        "rows": 1196250,
                        "cost": 241341,
                        "chosen": true
                      },
                      {
                        "index": "i1",
                        "ranges": [
                          "7 <= b <= 7 AND 10 < a"
                        ],
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": false,
                        "using_mrr": false,
                        "index_only": true,
                        "rows": 390,
                        "cost": 80.524,
                        "chosen": true
                      },
                      {
                        "index": "i2",
                        "ranges": [
                          "7 <= b <= 7"
                        ],
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": false,
                        "using_mrr": false,
                        "index_only": true,
                        "rows": 400,
                        "cost": 82.177,
                        "chosen": false,
                        "cause": "cost"
                      }
                    ],

We see that i1 has the lowest cost (80.524).  However, when selecting access method, we see that the range cost is higher:

                "best_access_path": {
                  "considered_access_paths": [
                    {
                      "access_type": "ref",
                      "index": "i1",
                      "rows": 2.39e6,
                      "cost": 487810,
                      "chosen": true
                    },
                    {
                      "access_type": "ref",
                      "index": "i2",
                      "rows": 400,
                      "cost": 82.167,
                      "chosen": true
                    },
                    {
                      "rows_to_scan": 390,
                      "access_type": "range",
                      "range_details": {
                        "used_index": "i1"
                      },
                      "resulting_rows": 390,
                      "cost": 158.52,
                      "chosen": false
                    }
                  ]

Hence, range access is selected.

Posted by developer:
 
Sorry, for typo at end of last comment.  I meant to say:  "Hence, ref access is selected"

The problem can be verified on previous versions as well.

master [localhost] {msandbox} ((none)) >   explain format=json SELECT a.profile_id,a.ad_id_in_target,a.affcode  FROM test.test_table a USE KEY(profile_id_date) WHERE profile_id = 53  AND  DATE >=  '2018-02-28' AND DATE < NOW();
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| {
  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "a",
      "access_type": "ref",
      "possible_keys": [
        "profile_id_date"
      ],
      "key": "profile_id_date",
      "used_key_parts": [
        "profile_id"
      ],
      "key_length": "4",
      "ref": [
        "const"
      ],
      "rows": 19818,
      "filtered": 100,
      "index_condition": "((`test`.`a`.`date` >= '2018-02-28') and (`test`.`a`.`date` < now()))"
    }
  }
} |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set, 1 warning (0.00 sec)

master [localhost] {msandbox} ((none)) >   explain format=json SELECT a.profile_id,a.ad_id_in_target,a.affcode  FROM test.test_table a WHERE profile_id = 53  AND  DATE >=  '2018-02-28' AND DATE < NOW();
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| {
  "query_block": {
    "select_id": 1,
    "table": {
      "table_name": "a",
      "access_type": "ref",
      "possible_keys": [
        "affcode_per_day",
        "profile_ad_id_date",
        "profile_affcode",
        "profile_id_date"
      ],
      "key": "affcode_per_day",
      "used_key_parts": [
        "profile_id"
      ],
      "key_length": "4",
      "ref": [
        "const"
      ],
      "rows": 23410,
      "filtered": 100,
      "using_index": true,
      "attached_condition": "((`test`.`a`.`date` >= '2018-02-28') and (`test`.`a`.`date` < <cache>(now())))"
    }
  }
} |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set, 1 warning (0.00 sec)

master [localhost] {msandbox} ((none)) > select @@version;
+------------+
| @@version  |
+------------+
| 5.6.36-log |
+------------+
1 row in set (0.00 sec)