Mysql innodb如何 统计table statistics
Table statistics 包含两个方面：
1) table stat 比如表内一共有多少条记录(n_rows)。
此类信息保存在mysql.innodb_table_stats表中。
2) index stat 比如index中包含多少个page, 多少个leaf page，共有多少条完全不同的索引
此信息保存在mysql.innodb_index_stats表中。
在innodb中，一切都是基于index的，table stat 中n_rows的计算也是基于index的。
下面就分析一下innodb是如何对index进行统计的。
哎，还是先简单介绍一下index的结构—B+ tree
B+tree的结构如下图：
这张图是从 Wikipedia copy过来的，不必太执着于它。
Index在硬盘文件中的最基本保存单位是page(默认16K一页)，这些page在一起组成了B+ tree。 表中的每一个index，对应一个B+tree。
根据page的类型，可以分为三类：
1) Root page 最上面的一个page, 对B+ tree的访问总是从它开始的。
2) leaf page 最下层的page. 储存了真正的索引数据。如果是主键的话，还储存了其它全部的字段。
3) non-leaf page 界于Root page与leaf page之间的page.
另外还有一个level的概念：
Leaf page 的level 为0, 每往上走一层，level就+1。
Root 的level最大，表示这个tree 的高度。
Leaf page 的简单结构：
此page中的记录，从Infimum开始，到Supremum结束，每个记录都有一条指针指向下一条记录，组成了一条单向升序的链表。 Infimum与Supremum为system记录，表示page中记录的开始和结束。它们之间的记录为User记录，保存了key(索引的值)与value(如果为主键索引，那么value就是其它的全部字段的值；如果是非主键索引，value就是主键的值(Primary Key Value , PKV))。
Non-leaf page的简单结构：
与leaf page的结构相似，只不过在每条记录中，它保存的key的意思是：child page中最小的索引值。 然后也保存了child 的page num（相当于一个指向child page的指针）。每一条记录，只有一个child page。
再来看一下level的概念：
同一level中的page由二条指针组成了双向的链表， 同时有了升序和降序。
最后从整体上把握一下：
CREATE TABLE t (
i INT NOT NULL,
s CHAR(10) NOT NULL,
PRIMARY KEY(i)
) ENGINE=InnoDB;
INSERT INTO t (i, s)
VALUES (0, "A"), (1, "B"), (2, "C"), (3, “D”),(4,”E”),(5,”F”),(6,”G”),(7,”H”); |
如果需要对index进行统计，最简单的办法就是从头到尾扫描此index对应的B+tree全部的leaf page中的全部记录，看一下有多少条不相同的索引。优点是非常精确， 缺点是如果page相当多的话，扫描的速度会相当慢。
Mysql的做法是采样，从全部leaf page中取出20个page 进行分析，
mysql> SELECT @@global.innodb_stats_persistent_sample_pages;
+-----------------------------------------------+
| @@global.innodb_stats_persistent_sample_pages |
+-----------------------------------------------+
| 20 |
+-----------------------------------------------+
1 ROW IN SET (0.00 sec) |
当然这个变量是可以配置的， 它的值越大，统计的结果越精确，统计的速度也就越慢。把它记为A。
还是先用简单的主键索引(clustered index )来分析吧。。。越来越乱了。
之所以说主键索引比较简单，是因为在任意一个level中，全部page中的全部记录的key都是不相同的。
从Root page开始，向下面的level遍历它的全部child page，直到遇到这样的一个level:
此level中至少包含A * 10条不相同的key。
把此level标记为LA。
然后从此level的全部记录中随机选出A条记录。
顺着这A条记录向下，找到A个leaf page。 分析每个leaf page中含有多少个不同的key。对于主键索引来说，leaf page中有多少条记录，就有多少个不同的key。
分析完这A个leaf page， 每个page中不同的key的数量保存到 P1, P2, P3, P4 … PA中。
那么平均值 N_DIFF_AVG_LEAF 就是 (P1 + P2 + … + PA) / A。
再假设全部leaf page的数量为N，
那么全部leaf page中不同的key的数量为 N * N_DIFF_AVG_LEAF。
对于主键索引，这个值刚好就是全部leaf page中的记录数，也就是此表中的记录数n_rows。
mysql> SELECT * FROM innodb_index_stats WHERE TABLE_NAME='xxxx2' AND index_name='PRIMARY';
+---------------+------------+------------+---------------------+--------------+------------+-------------+-----------------------------------+
| database_name | TABLE_NAME | index_name | last_update | stat_name | stat_value | sample_size | stat_description |
+---------------+------------+------------+---------------------+--------------+------------+-------------+-----------------------------------+
| kaixin | xxxx2 | PRIMARY | 2013-05-08 15:55:04 | n_diff_pfx01 | 5207 | 20 | id |
| kaixin | xxxx2 | PRIMARY | 2013-05-08 15:55:04 | n_leaf_pages | 277 | NULL | NUMBER OF leaf pages IN the INDEX |
| kaixin | xxxx2 | PRIMARY | 2013-05-08 15:55:04 | SIZE | 353 | NULL | NUMBER OF pages IN the INDEX |
+---------------+------------+------------+---------------------+--------------+------------+-------------+-----------------------------------+
3 ROWS IN SET (0.00 sec)
mysql> SELECT * FROM innodb_table_stats WHERE TABLE_NAME='xxxx2';
+---------------+------------+---------------------+--------+----------------------+--------------------------+
| database_name | TABLE_NAME | last_update | n_rows | clustered_index_size | sum_of_other_index_sizes |
+---------------+------------+---------------------+--------+----------------------+--------------------------+
| kaixin | xxxx2 | 2013-05-08 15:55:04 | 5207 | 353 | 177 |
+---------------+------------+---------------------+--------+----------------------+--------------------------+
由于只是一个随机的采样，且样本只有20个page, 准确度确实难以保证，但还是有一定的参考价值的。
mysql> SELECT COUNT(*) FROM kaixin.xxxx2;
+----------+
| COUNT(*) |
+----------+
| 5432 |
+----------+
1 ROW IN SET (0.00 sec) |
最后来看比较复杂一点的secondary index。
假设表结构为
CREATE TABLE t (
i INT NOT NULL,
s CHAR(10) NOT NULL,
a INT NOT NULL,
b INT NOT NULL,
c INT NOT NULL,
PRIMARY KEY(i),
KEY (a,b,c)
) ENGINE=InnoDB; |
在a b c 三个字段上定义了一个索引，不唯一，允许重复的值出现。
反映到此索引的B+tree中， 某一条记录可能与它相邻记录的key值是相同的， 甚至某一个page中，key值都是相同的。
与Non-leaf page和level相关的一个概念：boring record：
如果non-leaf page中的一条记录R的key与它右侧(可跨越page，但要保证在同一个level上面)的记录的key值相同，那么认为此记录R为boring record。
Boring record的特性：
在Boring record的全部child page，直至leaf page中，key值都是相同的，都与boring record的key值相同。
所以这种boring record就没有分析的必要， 因为key值不同的记录数肯定为1。
流程开始：
仍然是从Root page开始，向下面的level遍历它的全部child page，直到遇到这样的一个level:
此level中至少包含A * 10条不相同的key。
把此level标记为LA。
先定义一个数组boundaries[]
对于 level LA中具有相同key的记录，只把最后一个记录保存到数组中。遍历此level之后，boundaries[]就包含了全部的不同的key的记录，总数量记为n_diff_for_this_prefix。
#如果 A > n_diff_for_this_prefix， 则 A=n_diff_for_this_prefix。
然后把它们等分成A组，每组数量为 n_diff_for_this_prefix除以A。
然后从每一组中随机选出一个记录， 共选出A条记录。
顺着这A条记录向下，找到A个leaf page。在这个向下的过程中， 遇到boring record就跳过。然后分析每个leaf page中含有多少个不同的key。
分析完这A个leaf page， 每个page中不同的key的数量保存到 P1, P2, P3, P4 … PA中。
那么平均值 N_DIFF_AVG_LEAF 就是 (P1 + P2 + … + PA) / A。
Level LA中全部记录总数为TOTAL_LA，
Level LA中不同记录的数量为N_DIFF_LA
再假设全部leaf page的数量为N，
那么全部leaf page中不同的key的数量为 (N_DIFF_LA / TOTAL_LA ) *N * N_DIFF_AVG_LEAF。
其实对于index(a,b,c) ，需要执行4次上面的分析过程。第一次是a, 第二次是(a,b),第三次是(a,b,c)， 第四次是(a,b,c,i)。
mysql> SELECT * FROM innodb_index_stats WHERE TABLE_NAME='t' ;
+---------------+------------+------------+---------------------+--------------+------------+-------------+-----------------------------------+
| database_name | TABLE_NAME | index_name | last_update | stat_name | stat_value | sample_size | stat_description |
+---------------+------------+------------+---------------------+--------------+------------+-------------+-----------------------------------+
| mysql | t | PRIMARY | 2013-05-08 16:23:05 | n_diff_pfx01 | 0 | 1 | i |
| mysql | t | PRIMARY | 2013-05-08 16:23:05 | n_leaf_pages | 1 | NULL | NUMBER OF leaf pages IN the INDEX |
| mysql | t | PRIMARY | 2013-05-08 16:23:05 | SIZE | 1 | NULL | NUMBER OF pages IN the INDEX |
| mysql | t | a | 2013-05-08 16:23:05 | n_diff_pfx01 | 0 | 1 | a |
| mysql | t | a | 2013-05-08 16:23:05 | n_diff_pfx02 | 0 | 1 | a,b |
| mysql | t | a | 2013-05-08 16:23:05 | n_diff_pfx03 | 0 | 1 | a,b,c |
| mysql | t | a | 2013-05-08 16:23:05 | n_diff_pfx04 | 0 | 1 | a,b,c,i |
| mysql | t | a | 2013-05-08 16:23:05 | n_leaf_pages | 1 | NULL | NUMBER OF leaf pages IN the INDEX |
| mysql | t | a | 2013-05-08 16:23:05 | SIZE | 1 | NULL | NUMBER OF pages IN the INDEX |
+---------------+------------+------------+---------------------+--------------+------------+-------------+-----------------------------------+
9 ROWS IN SET (0.00 sec) |
还有一些优化和细节， 请看 代码 。
参考：
http://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/
http://blog.jcole.us/2013/01/10/the-physical-structure-of-records-in-innodb/
/mysql-5.6.10/storage/innobase/dict dict0stats.cc
/mysql-5.6.10/storage/innobase/include/dict0mem.h
