Bug #67351 Cardinality samples of partitioned tables sometimes widely off
Submitted: 24 Oct 2012 8:02 Modified: 1 Dec 2012 16:00
Reporter: Patrick van Bergen Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Partitions Severity:S2 (Serious)
Version:5.5.27-29.0 OS:Linux
Assigned to: CPU Architecture:Any
Tags: cardinality, Optimizer, partitions
Triage: Needs Triage: D2 (Serious)

[24 Oct 2012 8:02] Patrick van Bergen
Description:
We have recently partitioned some triple tables to take advantage of the fact that active triples could be stored and queried from a single partition. However, sometimes the queries on these tables are very very slow (over 30 times slower, taking 10 seconds in stead of 0.3). An explain shows that the wrong key is used in these instances. And this again seems to be caused by an incorrect sampling of the cardinality of such a table, as shown by a 'show index' query.

How to repeat:
To replicate the bug I will show the create table statement, a sample query that has will show very different execution times, a sample database, and a way to provoke cardinality resampling.

The partitioned table:

CREATE TABLE `mod_lime_int` (
  `triple_id` int(11) NOT NULL,
  `subject_id` int(11) NOT NULL,
  `predicate_id` int(11) NOT NULL,
  `object` int(11) NOT NULL,
  `active` tinyint(1) NOT NULL DEFAULT '1',
  PRIMARY KEY (`subject_id`,`predicate_id`,`object`,`active`),
  KEY `predicate_id` (`predicate_id`,`object`),
  KEY `triple_id` (`triple_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
/*!50100 PARTITION BY LIST (active)
(PARTITION inactive VALUES IN (0) ENGINE = InnoDB,
 PARTITION active VALUES IN (1) ENGINE = InnoDB,
 PARTITION destroyed VALUES IN (2) ENGINE = InnoDB) */
 
A query that performs sometimes very slowly:
 
 SELECT `object_ownerRelation`.`subject_id` `id`
FROM `mod_lime_int` `object_ownerRelation`
LEFT JOIN `mod_lime_int` `object_managerRelation`  ON  ((`object_managerRelation`.`subject_id` = `object_ownerRelation`.`subject_id`) AND (`object_managerRelation`.`predicate_id` = 15289) AND (`object_managerRelation`.`active` = 1)) 
LEFT JOIN `mod_lime_int` `object_originalObjectId`  ON  ((`object_originalObjectId`.`subject_id` = `object_ownerRelation`.`subject_id`) AND (`object_originalObjectId`.`predicate_id` = 30060) AND (`object_originalObjectId`.`active` = 1)) 
LEFT JOIN `mod_lime_int` `object_active`  ON  ((`object_active`.`subject_id` = `object_ownerRelation`.`subject_id`) AND (`object_active`.`predicate_id` = 1477) AND (`object_active`.`active` = 1)) 
WHERE ((`object_ownerRelation`.`predicate_id` = 15288) AND (`object_ownerRelation`.`active` = 1)) AND ((`object_ownerRelation`.`object` = '2') OR (`object_managerRelation`.`object` = '2'))  AND `object_originalObjectId`.`object` IS NULL AND `object_active`.`object` = TRUE
LIMIT 25;

This is how I experimented with cardinality resampling. I run this several times, obtaining very different results each time:

analyze table mod_lime_int; set global innodb_stats_on_metadata=0; show index from mod_lime_int;

Here are two result sets of two runs this line of queries:

This result is associated with fast queries:

+--------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table        | Non_unique | Key_name     | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| mod_lime_int |          0 | PRIMARY      |            1 | subject_id   | A         |      185269 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          0 | PRIMARY      |            2 | predicate_id | A         |      316501 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          0 | PRIMARY      |            3 | object       | A         |     7596044 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          0 | PRIMARY      |            4 | active       | A         |     7596044 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          1 | predicate_id |            1 | predicate_id | A         |          20 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          1 | predicate_id |            2 | object       | A         |     2532014 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          1 | triple_id    |            1 | triple_id    | A         |     7596044 |     NULL | NULL   |      | BTREE      |         |               |
+--------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
7 rows in set (0.01 sec)

This result is associated with slow queries:

+--------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table        | Non_unique | Key_name     | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+--------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| mod_lime_int |          0 | PRIMARY      |            1 | subject_id   | A         |          21 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          0 | PRIMARY      |            2 | predicate_id | A         |          21 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          0 | PRIMARY      |            3 | object       | A         |     8655933 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          0 | PRIMARY      |            4 | active       | A         |     8655933 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          1 | predicate_id |            1 | predicate_id | A         |          21 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          1 | predicate_id |            2 | object       | A         |     4327966 |     NULL | NULL   |      | BTREE      |         |               |
| mod_lime_int |          1 | triple_id    |            1 | triple_id    | A         |     8655933 |     NULL | NULL   |      | BTREE      |         |               |
+--------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
7 rows in set (0.00 sec)

As you can see, cardinality of PRIMARY/predicate_id (which is essential to the query) is sometimes widely off (21 versus 316501).

Suggested fix:
I would like to ask you if you can find out why the query is very slow in some occasions. If, as we expect, the cause lies in the incorrect sampling of cardinality of the compound keys of the partitioned table, I would like ask you to repair it.
[29 Nov 2012 21:00] Sveta Smirnova
Thank you for the report.

I am sorry: missed this report earlier and now your file was expired after 21 days lifetime. Can you re-upload it?

Anyway table statistics get outdated after about 25% or rows were modified. For example, if many rows were updated or removed. If this is your case this is technically not a bug. Please check if this is not the case.
[30 Nov 2012 10:17] Patrick van Bergen
I uploaded the database file anew.

In reply to your suggestion: statistics change even though the data stays exactly the same.
[30 Nov 2012 16:29] Sveta Smirnova
Thank you for the feedback.

I don't see the file. What is the name of new file?
[1 Dec 2012 16:00] Sveta Smirnova
Thank you for the file.

Verified as described.

To repeat: load dump provided, measure time which select query takes (0.6 sec in average on my slow laptop), then run `analyze table mod_lime_int; set global innodb_stats_on_metadata=0; show index from mod_lime_int; ` until Cardinality field shows for both subject_id and predicate_id columns values of 20 (or 21, or similar, much less than 309473 for one of normal execution time), then run select query again. Query took 1 min 21.65 sec on the same machine.

Workaround: upgrade to version 5.6 and use innodb_stats_persistent (http://dev.mysql.com/doc/refman/5.6/en/innodb-parameters.html#sysvar_innodb_stats_persiste...) or use ANALYZE TABLE until plan is good, then turn OFF innodb_stats_on_metadata.
[1 Dec 2012 20:34] Mattias Jonsson
The index statistic is only based on a single partition (normally the one with the most rows).

It is updated during open of the table instance (can be several instances open and kept in the table cache).

It is also updated when doing ANALYZE TABLE or ALTER TABLE ANALYZE PARTITION (which allows you to choose which partition to use the statistics from).

And if one selects from INFORMATION_SCHEMA.PARTITIONS, it will get the index statistics from the last partition.

For more info see bug#60071.
[12 Dec 2012 16:52] Vlad Safronov
Upload limit has been increased up to 3M.
[29 Dec 2012 3:13] Aaron Greenspan
I have several tables that are being JOINed together, each of which is partitioned. They are all MyISAM tables. The cardinality of the indexes seems pretty off, even if (as this threat indicates) only one of the partitions is being used to calculate the cardinality. For example, I have a table called "patentassignmentdocuments" that has an ENUM column called "linktable" in which only two values are allowed: patents and patentapplications. Both of these values are used among several million rows. Therefore, my understanding is that the cardinality of that column index should be 2. According to MySQL, it's now 59. Before it was 172.

Here is what I see:

mysql> SHOW INDEXES FROM patentassignmentdocuments;
+---------------------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| Table                     | Non_unique | Key_name     | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------------------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| patentassignmentdocuments |          0 | PRIMARY      |            1 | documentid   | A         |    48647475 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | assignmentid |            1 | assignmentid | A         |      884499 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | number       |            1 | number       | A         |    24323737 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | patentid     |            1 | linktable    | A         |         172 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | patentid     |            2 | linkid       | A         |    16215825 |     NULL | NULL   |      | BTREE      |         |
+---------------------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
5 rows in set (0.00 sec)

mysql> ANALYZE TABLE patentassignmentdocuments;
+-------------------------------------+---------+----------+----------+
| Table                               | Op      | Msg_type | Msg_text |
+-------------------------------------+---------+----------+----------+
| plainsite.patentassignmentdocuments | analyze | status   | OK       |
+-------------------------------------+---------+----------+----------+
1 row in set (13.00 sec)

mysql> SHOW INDEXES FROM patentassignmentdocuments;
+---------------------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| Table                     | Non_unique | Key_name     | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------------------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| patentassignmentdocuments |          0 | PRIMARY      |            1 | documentid   | A         |    48647475 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | assignmentid |            1 | assignmentid | A         |      992805 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | number       |            1 | number       | A         |    16215825 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | patentid     |            1 | linktable    | A         |          59 |     NULL | NULL   |      | BTREE      |         |
| patentassignmentdocuments |          1 | patentid     |            2 | linkid       | A         |     9729495 |     NULL | NULL   |      | BTREE      |         |
+---------------------------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
5 rows in set (0.01 sec)

mysql> SELECT DISTINCT linktable FROM patentassignmentdocuments;
+--------------------+
| linktable          |
+--------------------+
| patents            |
| patentapplications |
+--------------------+
2 rows in set (3.82 sec)

Even if somehow the cardinality is being multiplied across every partition in the table, the number is likely still wrong. (There are currently 48 partitions by range of the primary key--I'd expect the cardinality to be 48 x 2 = 96.)

Any help would be appreciated. Thanks!
[29 Dec 2012 3:19] Aaron Greenspan
I should also have stated the version I'm running:

mysql> SELECT @@version;
+-----------+
| @@version |
+-----------+
| 5.1.61    |
+-----------+
1 row in set (0.00 sec)

[root@x flashlight]# uname -a
Linux x.thinkcomputer.com 2.6.32-279.11.1.el6.i686 #1 SMP Tue Oct 16 14:40:53 UTC 2012 i686 i686 i386 GNU/Linux

This is on CentOS, if that matters.
[15 Nov 2013 11:42] Shane Bester
Sample testcase.  Note the cardinality of column b before/after partitioning.

drop table if exists t1;
create table t1(a int not null,b int,unique key(a),key(b)) engine=myisam;

insert into t1(a,b) values (0,1),(1,2),(2,3);
replace into t1(a,b) select rand()*500,rand()*1000 from t1,t1 t2,t1 t3,t1 t4,t1 t5,t1 t6;
replace into t1(a,b) select rand()*100,rand()*1000 from t1;
update t1 set b=1 where a<100;

analyze table t1;
show keys from t1;

alter table t1
partition by range(a)( 
partition p1 values less than (100),
partition p2 values less than (200),
partition p3 values less than (300),
partition p4 values less than (400),
partition p5 values less than (500),
partition p6 values less than (maxvalue)
); 

analyze table t1;
show keys from t1;

select partition_name,table_rows from information_schema.partitions where table_name='t1' order by table_rows desc limit 2;
[15 Nov 2013 11:43] Shane Bester
mysql> analyze table t1;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.t1 | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> show keys from t1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+--
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | C
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+--
| t1    |          0 | a        |            1 | a           | A         |         419 |     NULL | NULL   |      | BTREE      |
| t1    |          1 | b        |            1 | b           | A         |         209 |     NULL | NULL   | YES  | BTREE      |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+--
2 rows in set (0.00 sec)

mysql>
mysql> alter table t1
    -> partition by range(a)(
    -> partition p1 values less than (100),
    -> partition p2 values less than (200),
    -> partition p3 values less than (300),
    -> partition p4 values less than (400),
    -> partition p5 values less than (500),
    -> partition p6 values less than (maxvalue)
    -> );
Query OK, 419 rows affected (0.01 sec)
Records: 419  Duplicates: 0  Warnings: 0

mysql>
mysql>
mysql> analyze table t1;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.t1 | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.00 sec)

mysql> show keys from t1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+--
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | C
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+--
| t1    |          0 | a        |            1 | a           | A         |         419 |     NULL | NULL   |      | BTREE      |
| t1    |          1 | b        |            1 | b           | A         |           4 |     NULL | NULL   | YES  | BTREE      |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+--
2 rows in set (0.00 sec)

mysql>
mysql> select partition_name,table_rows from information_schema.partitions where table_name='t1' order by table_rows desc limit 2;
+----------------+------------+
| partition_name | table_rows |
+----------------+------------+
| p1             |        100 |
| p5             |         88 |
+----------------+------------+
2 rows in set (0.00 sec)

mysql>
mysql>
mysql> select count(distinct b) from t1 where a<=100;
+-------------------+
| count(distinct b) |
+-------------------+
|                 2 |
+-------------------+
1 row in set (0.00 sec)
[9 Jan 2014 13:11] Arnaud Adant
New test case for InnoDB :

use test;
drop table if exists t;
create table t(id bigint auto_increment primary key, c1 bigint, c2 bigint, c3 bigint) engine = InnoDB stats_persistent=1 stats_sample_pages=10000;

create index in_composite on t(c1, c2, c3);

insert into t(c1, c2, c3) values (rand()*10, rand()*2, rand()*3);
insert into t(c1, c2, c3) values (rand()*10, rand()*2, rand()*3);

replace into t(c1, c2, c3) select rand()*10, rand()*2, rand()*3 from t t1, t t2, t t3, t t4, t t5, t t6, t t7, t t8, t t9, t t10, t t11, t t12, t t13, t t14, t t15, t t16, t t17, t t18, t t19, t t20, t t21, t t22;

select count(distinct c1), count(distinct concat(c1,'-',c2)), count(distinct concat(c1,'-',c2,'-',c3)) from t;

analyze table t;
show indexes from t;

alter table t PARTITION BY key(id)     PARTITIONS 32;

analyze table t;
show indexes from t;

-- results :

mysql> select count(distinct c1), count(distinct concat(c1,'-',c2)), count(distinct concat(c1,'-',c2,'-',c3)) from t;
+--------------------+-----------------------------------+------------------------------------------+
| count(distinct c1) | count(distinct concat(c1,'-',c2)) | count(distinct concat(c1,'-',c2,'-',c3)) |
+--------------------+-----------------------------------+------------------------------------------+
|                 11 |                                33 |                                      132 |
+--------------------+-----------------------------------+------------------------------------------+
1 row in set (5.57 sec)

mysql>
mysql> analyze table t;
+--------+---------+----------+----------+
| Table  | Op      | Msg_type | Msg_text |
+--------+---------+----------+----------+
| test.t | analyze | status   | OK       |
+--------+---------+----------+----------+
1 row in set (0.96 sec)

mysql> show indexes from t;
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t     |          0 | PRIMARY      |            1 | id          | A         |     4180175 |     NULL | NULL   |      | BTREE      |         |               |
| t     |          1 | in_composite |            1 | c1          | A         |          22 |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            2 | c2          | A         |          66 |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            3 | c3          | A         |         264 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)

mysql>
mysql> alter table t PARTITION BY key(id)     PARTITIONS 32;
Query OK, 4194306 rows affected (45.74 sec)
Records: 4194306  Duplicates: 0  Warnings: 0

mysql>
mysql> analyze table t;
+--------+---------+----------+----------+
| Table  | Op      | Msg_type | Msg_text |
+--------+---------+----------+----------+
| test.t | analyze | status   | OK       |
+--------+---------+----------+----------+
1 row in set (1.21 sec)

mysql> show indexes from t;
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t     |          0 | PRIMARY      |            1 | id          | A         |     4194306 |     NULL | NULL   |      | BTREE      |         |               |
| t     |          1 | in_composite |            1 | c1          | A         |         316 |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            2 | c2          | A         |         948 |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            3 | c3          | A         |        3795 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)
[10 Feb 2017 16:21] Morgan Tocker
The behavior of statistics sampling has changed with MySQL 5.7 and native InnoDB partitioning.  Here is a test case to demonstrate:

-------

DROP TABLE IF EXISTS t1;
CREATE TABLE t1 (id INT NOT NULL auto_increment, a INT, b INT, UNIQUE KEY (id, b)) stats_sample_pages=10000;

INSERT INTO t1 VALUES (NULL, NULL, NULL);
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;
INSERT INTO t1 SELECT NULL, NULL, NULL FROM t1;

# Partition in a skewed way

alter table t1
partition by range(b)( 
partition p1 values less than (100),
partition p2 values less than (200),
partition p3 values less than (500),
partition p4 values less than (maxvalue)
);

UPDATE t1 SET a=id, b=(FLOOR(id/1000)*1000);

ALTER TABLE t1 ADD INDEX (b, a), ADD INDEX (a, b);

ANALYZE TABLE t1;
show keys from t1;

UPDATE t1 SET a = 1 WHERE b > 5000;
ANALYZE TABLE t1;
show keys from t1;

----------

MySQL 5.6 will show the same cardinality for both SHOW KEYS statements, since it samples the first partition to produce cardinality statistics.  In MySQL 5.7, the largest partition is used for sampling.
[10 Feb 2017 16:22] Morgan Tocker
Expected results:

5632> show keys from t1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t1    |          0 | id       |            1 | id          | A         |        8194 |     NULL | NULL   |      | BTREE      |         |               |
| t1    |          0 | id       |            2 | b           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            1 | b           | A         |          23 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            2 | a           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            1 | a           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            2 | b           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
6 rows in set (0.00 sec)

5632> 
5632> UPDATE t1 SET a = 1 WHERE b > 5000;
Query OK, 4229 rows affected (1.29 sec)
Rows matched: 4229  Changed: 4229  Warnings: 0

5632> ANALYZE TABLE t1;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.t1 | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.26 sec)

5632> show keys from t1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t1    |          0 | id       |            1 | id          | A         |        8194 |     NULL | NULL   |      | BTREE      |         |               |
| t1    |          0 | id       |            2 | b           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            1 | b           | A         |          23 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            2 | a           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            1 | a           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            2 | b           | A         |        8194 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
6 rows in set (0.00 sec)

5717> show keys from t1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t1    |          0 | id       |            1 | id          | A         |        8192 |     NULL | NULL   |      | BTREE      |         |               |
| t1    |          0 | id       |            2 | b           | A         |        8192 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            1 | b           | A         |          12 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            2 | a           | A         |        8192 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            1 | a           | A         |        8192 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            2 | b           | A         |        8192 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
6 rows in set (0.01 sec)

5717> 
5717> UPDATE t1 SET a = 1 WHERE b > 5000;
Query OK, 4229 rows affected (1.85 sec)
Rows matched: 4229  Changed: 4229  Warnings: 0

5717> ANALYZE TABLE t1;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.t1 | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.60 sec)

5717> show keys from t1;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t1    |          0 | id       |            1 | id          | A         |        8192 |     NULL | NULL   |      | BTREE      |         |               |
| t1    |          0 | id       |            2 | b           | A         |        8192 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            1 | b           | A         |          12 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | b        |            2 | a           | A         |        3687 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            1 | a           | A         |        3682 |     NULL | NULL   | YES  | BTREE      |         |               |
| t1    |          1 | a        |            2 | b           | A         |        3687 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
6 rows in set (0.01 sec)
[3 May 2017 16:04] Arnaud Adant
5.7 improved the cardinality estimates.

mysql> select @@version;
+-----------+
| @@version |
+-----------+
| 5.7.18    |
+-----------+
1 row in set (0.00 sec)

mysql> show indexes from t;
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t     |          0 | PRIMARY      |            1 | id          | A         |   4180175   |     NULL | NULL   |      | BTREE      |         |               |
| t     |          1 | in_composite |            1 | c1          | A         |       11    |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            2 | c2          | A         |       33    |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            3 | c3          | A         |      132    |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)

mysql>
mysql> alter table t PARTITION BY key(id)     PARTITIONS 32;
Query OK, 4194306 rows affected (3 min 28.22 sec)
Records: 4194306  Duplicates: 0  Warnings: 0

mysql>
mysql> analyze table t;
+--------+---------+----------+----------+
| Table  | Op      | Msg_type | Msg_text |
+--------+---------+----------+----------+
| test.t | analyze | status   | OK       |
+--------+---------+----------+----------+
1 row in set (19.56 sec)

mysql> show indexes from t;
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| t     |          0 | PRIMARY      |            1 | id          | A         |   4194306   |     NULL | NULL   |      | BTREE      |         |               |
| t     |          1 | in_composite |            1 | c1          | A         |       158   |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            2 | c2          | A         |       474   |     NULL | NULL   | YES  | BTREE      |         |               |
| t     |          1 | in_composite |            3 | c3          | A         |      1897   |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)

From times 28 to times 14. Still partitioning introduces a bias in 5.7. The non partitioned table stats are accurate now, there was a factor 2 difference in 5.6.