引言
在之前的文章中，我们频繁提到了一个叫做records_per_key的统计信息，它在代价估计，Join Reorder算法中都发挥着极其重要的作用。但我们之前只讲了这些统计信息是如何使用的，而在这篇文章中，将对MySQL中统计信息是如何计算，更新的做一个简单的介绍。
关于统计信息在MySQL优化器中起到的作用，感兴趣的同学可以看之前的两篇文章：
本文基于MySQL 8.0.34版本的源代码。
InnoDB统计信息
在mysql库中有两个表：innodb_table_stats和innodb_index_stats，这两个表是InnoDB进行统计信息持久化的表。我们先创建一个表test_stat，这个表以为主键，并且在上建立了二级索引，并且插入一些数据：
CREATE TABLE test_stat (
id int,
col1 int,
col2 int,
col3 int,
PRIMARY KEY (id, col1),
KEY index_col2_col3 (col2, col3)
);
insert into test_stat values (1, 1, 1, 1), (1, 2, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1);
在innodb_table_stats表上查询：
MySQL > select * from mysql.innodb_table_stats where table_name = 'test_stat';
+---------------+------------+---------------------+--------+----------------------+--------------------------+
| database_name | table_name | last_update | n_rows | clustered_index_size | sum_of_other_index_sizes |
+---------------+------------+---------------------+--------+----------------------+--------------------------+
| test | test_stat | 2024-02-21 19:12:16 | 4 | 1 | 1 |
+---------------+------------+---------------------+--------+----------------------+--------------------------+
在innodb_table_stats中记录了库名、表名、最近一次的更新时间、行数、聚簇索引的总页数，其他索引的页数总和。
在innodb_index_stats表上查询：
MySQL > select * from mysql.innodb_index_stats where table_name = 'test_stat';
+---------------+------------+-----------------+---------------------+--------------+------------+-------------+-----------------------------------+
| database_name | table_name | index_name | last_update | stat_name | stat_value | sample_size | stat_description |
+---------------+------------+-----------------+---------------------+--------------+------------+-------------+-----------------------------------+
| test | test_stat | PRIMARY | 2024-02-21 19:12:16 | n_diff_pfx01 | 2 | 1 | id |
| test | test_stat | PRIMARY | 2024-02-21 19:12:16 | n_diff_pfx02 | 4 | 1 | id,col1 |
| test | test_stat | PRIMARY | 2024-02-21 19:12:16 | n_leaf_pages | 1 | NULL | Number of leaf pages in the index |
| test | test_stat | PRIMARY | 2024-02-21 19:12:16 | size | 1 | NULL | Number of pages in the index |
| test | test_stat | index_col2_col3 | 2024-02-21 19:12:16 | n_diff_pfx01 | 2 | 1 | col2 |
| test | test_stat | index_col2_col3 | 2024-02-21 19:12:16 | n_diff_pfx02 | 3 | 1 | col2,col3 |
| test | test_stat | index_col2_col3 | 2024-02-21 19:12:16 | n_diff_pfx03 | 3 | 1 | col2,col3,id |
| test | test_stat | index_col2_col3 | 2024-02-21 19:12:16 | n_diff_pfx04 | 4 | 1 | col2,col3,id,col1 |
| test | test_stat | index_col2_col3 | 2024-02-21 19:12:16 | n_leaf_pages | 1 | NULL | Number of leaf pages in the index |
| test | test_stat | index_col2_col3 | 2024-02-21 19:12:16 | size | 1 | NULL | Number of pages in the index |
+---------------+------------+-----------------+---------------------+--------------+------------+-------------+-----------------------------------+
在这个表中记录了库名、表名、索引名、最后一次更新的时间以及索引的统计信息(stat_name、stat_value、sample_size、stat_description)。
索引的统计信息共有三种：
n_leaf_pages：索引B+树中叶子页的数量
size：索引B+树的总页数
n_diff_pfxNN：不同前缀列的Cardinality(不重复的值的个数)
这里以index_col2_col3的n_diff_pfx02为例，根据stat_description可知，这个值统计的是的Cardinality，从之前插入的数据可知，共有三种不同的取值，因此对应的stat_value为3，sample_size指计算Cardinality所采样的页面数，这个将在后面详细介绍。
现在，我们来考虑一个问题，innodb_table_stats和innodb_index_stats中，哪些数据是容易获得的，哪些是难获得的。
库名、表名、索引名、上一次更新的时间都是很容易获得的。
而对于索引的总页数和叶子页的数量，可以通过MySQL文件结构中相应的信息计算出来。
但对于n_rows和n_diff_pfxNN，似乎就很难获得了，要想获得准确值就必须全表扫描，但这肯定不现实。我们接下来就重点介绍MySQL是如何计算这两个统计信息的。
统计算法
既然不能全表扫描，那就可以考虑采样，一个最简单的采样方式就是：假设我们要统计id列的Cardinality，那么随机采样n个B+树的leaf page，发现平均每个页有m个distinct id，那么总的id列的Cardinality就为 m * n_leaf_pages 。这种采样方式很简单，但却会带来非常大的误差。以下面的B+树为例：
这是一个简单的二层B+树。可以发现，其中四个leaf page都只包含一个distinct值，如果随机采样，那么极大概率会采样到这四个leaf page上，造成估计值的不准确。
那么如何解决这个问题呢？从这个B+树上我们其实可以有所启发，我们只要采样第四个leaf page不就可以了么，其他的leaf page根本就不关键，甚至没必要采样。换句话说，我们不关心那些数据高度一致的leaf page，只关心数据变化很大的leaf page。
如果有学过蒙特卡洛积分的同学，会发现这种思路其实就是重要性采样。我们人为地对采样分布进行干预，使得数据变化慢的地方采样数少，数据变化快的地方采样数高，以此来减少估计的方差。
现在的问题就变成了如何找到这些数据变化快的leaf page，并且通过对这些leaf page进行采样以估计出Cardinality和n_rows。
源码分析
有关统计信息更新的代码主要位于dict_stats_update_persistent()函数中。 在这个函数中，会首先计算表的聚簇索引（主键索引）的统计信息，并将结果保存在index->stat_xxxx变量中。index->stat_n_diff_key_vals[]数组保存了该索引在不同前缀长度下的Cardinality估计值。那么，对于表级别的统计信息n\_rows，其实就是完整主键的Cardinality估计值。详细逻辑可以看下述代码：
/** Calculates new estimates for table and index statistics. This function
is relatively slow and is used to calculate persistent statistics that
will be saved on disk.
@return DB_SUCCESS or error code */
static dberr_t dict_stats_update_persistent(
dict_table_t *table) /*!< in/out: table */
{
dict_index_t *index;
dict_table_stats_lock(table, RW_X_LATCH);
/* analyze the clustered index first */
// table的第一个索引是聚簇索引
index = table->first_index();
...
// 对聚簇索引进行analyze
dict_stats_analyze_index(index);
// 获得聚簇索引有多少列
ulint n_unique = dict_index_get_n_unique(index);
// 统计信息中的n_rows就是聚簇索引有多少不同的值
table->stat_n_rows = index->stat_n_diff_key_vals[n_unique - 1];
// 聚簇索引的大小在analyze过程中会通过读B+tree获得
table->stat_clustered_index_size = index->stat_index_size;
// analyze其他索引，将其他索引的页面数总和初始化为0
table->stat_sum_of_other_index_sizes = 0;
for (index = index->next(); index != nullptr; index = index->next()) {
ut_ad(!dict_index_is_ibuf(index));
...
// analyze其他二级索引
if (!(table->stats_bg_flag & BG_STAT_SHOULD_QUIT)) {
dict_stats_analyze_index(index);
}
table->stat_sum_of_other_index_sizes += index->stat_index_size;
}
...
return (DB_SUCCESS);
}
在dict_stats_update_persistent()函数中，我们发现， 对于任意一个表，它的所有索引的n_diff_pfxNN计算出来了，n_rows自然也就计算出来了，所以，其实其实只要解决n_diff_pfxNN的计算问题，统计信息的计算问题也就解决了。
因此，我们重点看n_diff_pfxNN的计算函数：dict_stats_analyze_index() 。在这个函数，给出了采样数量的计算方式，并且如果发生长时间锁等待，会尝试更小的采样数量。
/** Calculates new statistics for a given index and saves them to the index
members stat_n_diff_key_vals[], stat_n_sample_sizes[], stat_index_size and
stat_n_leaf_pages. This function could be slow. */
static void dict_stats_analyze_index(
dict_index_t *index) /*!< in/out: index to analyze */
{
// 获取采样数量，如果针对这个表指定了采样数量，则使用指定的采样数量，如果没有指定，则使用全局默认的
uint64_t n_sample_pages = N_SAMPLE_PAGES(index);
// 如果有长时间锁等待导致超时，就换一个更小的采样数量重试
while (n_sample_pages > 0 &&
!dict_stats_analyze_index_low(n_sample_pages, index)) {
/* aborted. retrying. */
ib::warn(ER_IB_MSG_STATS_SAMPLING_TOO_LARGE)
<< "Detected too long lock waiting around " << index->table->name << "."
<< index->name
<< " stats_sample_pages. Retrying with the smaller value "
<< n_sample_pages << ".";
/* Certain delay is needed for waiters to lock the index next. */
std::this_thread::sleep_for(std::chrono::milliseconds(100));
}
}
dict_stats_analyze_index()函数实际上会调用 dict_stats_analyze_index_low()函数进行analyze，我们先来看一下dict_stats_analyze_index_low()的伪代码：
dict_stats_analyze_index_low(N)
// 对每一个前缀
for each n_prefix
// 寻找一个足够好的的level
search for good enough level:
// 在这个level上进行分析，在实现上是对这个level进行全表扫描
dict_stats_analyze_index_level()
// 如果这个level不足够好，则找下一个level
if we are not satisfied with the level, search next lower level
// 找到了一个足够好的level
we have found a good enough level here
// 在这个level上开始计算统计信息
dict_stats_analyze_index_for_n_prefix(that level, stats collected above)
// 从这个level进行dive，搜集叶子结点上的统计信息
dive below some records and analyze the leaf page there:
dict_stats_analyze_index_below_cur()
从这个伪代码我们发现算法有两个关键点：
找到一个足够好的level（见下文)。
从这个足够好的level进行dive以搜集叶子结点的统计信息。
这里的level是指B+树的层数，leaf page的level设为0。下面的图是一个B+树的示意图，为了简单起见，这里省略了不同层之间的连接关系。我们从这个图去模拟一下统计信息的计算过程。
假设level n就是我们找到的足够好的level，在这个level中共有p条数据，其中有q个distinct值，我们准备采样m个leaf page，那么就把这q个distinct值平均分成m个seg，在每个seg中，都进行一次dive，找到数据快速变化的page，并且统计到这些leaf page平均每个page有t条distinct记录。那么最后的Cardinality估计值就是：
n_leaf_pages * (q/p) * t
其中乘以(q/p)的原因是: 在这个level中，只有比例为(q/p)的pages的leaf page存在变化的数据，例如在level n中，两个5之间子树的leaf page中的数据肯定都是5，因此这些子树的数据是不会贡献Cardinality的。所以只有(q/p)的pages的leaf page会存在变化的数据。
足够好的Level
到这里我们就体会到这个level的重要性了，level取得太大，统计出来的值会偏差很大，因为(q/p)这个因子的估计会很不准确，取得太低，又会导致计算量的增加，因为判断一个level是否足够好需要把这个level遍历一遍。因此，MySQL判断一个level是否足够好的依据是：这个level是否存在n_sample_pages * 10个distinct值。这个判断依据平衡了性能和估计准确度。采样的页数是可配置的，默认是20个页。每个表可以通过ALTER TABLE指定自己的采样页数。
dict_stats_analyze_index_low()函数的主要逻辑就是在寻找足够好的level。 详细逻辑可以看如下源代码：
/** Calculates new statistics for a given index and saves them to the index
members stat_n_diff_key_vals[], stat_n_sample_sizes[], stat_index_size and
stat_n_leaf_pages, based on the specified n_sample_pages.
@param[in,out] n_sample_pages number of leaf pages to sample. and suggested
next value to retry if aborted.
@param[in,out] index index to analyze.
@return false if aborted */
static bool dict_stats_analyze_index_low(uint64_t &n_sample_pages,
dict_index_t *index) {
// leaf page的level为0
ulint root_level;
ulint level;
// 当前level是否被analyze
bool level_is_analyzed;
ulint n_uniq;
ulint n_prefix;
uint64_t total_recs;
uint64_t total_pages;
// 足够好的level所需要的distinct值
const uint64_t n_diff_required = n_sample_pages * 10;
bool succeeded = true;
mtr_t mtr;
ulint size;
DBUG_TRACE;
...
// 获取b+树的总page数
size = btr_get_size(index, BTR_TOTAL_SIZE, &mtr);
// 获取b树的叶子page数
if (size != ULINT_UNDEFINED) {
index->stat_index_size = size;
size = btr_get_size(index, BTR_N_LEAF_PAGES, &mtr);
}
...
// 更新索引级别的统计信息：n_leaf_pages
index->stat_n_leaf_pages = size;
...
mtr_sx_lock(dict_index_get_lock(index), &mtr, UT_LOCATION_HERE);
auto wait_start_time = std::chrono::steady_clock::now();
// 获取跟结点的level
root_level = btr_height_get(index, &mtr);
// 获取该索引有几列
n_uniq = dict_index_get_n_unique(index);
// 如果B+树只有一个根结点，全表扫描即可
// analyze这个索引总共需要采样n_sample_pages * n_uniq个leaf page，如果这个值大于了n_leaf_pages，
// 那么也可以全表扫描
if (root_level == 0 || n_sample_pages * n_uniq >
std::min<ulint>(index->stat_n_leaf_pages, 1e6)) {
...
(void)dict_stats_analyze_index_level(
index, 0 /* leaf level */, index->stat_n_diff_key_vals, &total_recs,
&total_pages, nullptr /* boundaries not needed */, wait_start_time,
&mtr);
...
for (ulint i = 0; i < n_uniq; i++) {
index->stat_n_sample_sizes[i] = total_pages;
}
...
return true;
}
// n_diff_on_level记录了该level对于不同长度的前缀索引有多少distinct值
uint64_t *n_diff_on_level = ut::new_arr_withkey<uint64_t>(
ut::make_psi_memory_key(mem_key_dict_stats_n_diff_on_level),
ut::Count{
n_uniq});
// n_diff_boundaries记录了发生变化的分界线，便于后期划分seg
boundaries_t *n_diff_boundaries = ut::new_arr_withkey<boundaries_t>(
UT_NEW_THIS_FILE_PSI_KEY, ut::Count{
n_uniq});
// n_diff_data保存了用来计算Cardinality所需的输入数据
n_diff_data_t *n_diff_data = ut::new_arr_withkey<n_diff_data_t>(
UT_NEW_THIS_FILE_PSI_KEY, ut::Count{
n_uniq});
total_recs = 1;
level = root_level;
level_is_analyzed = false;
// 从root level开始向下遍历，寻找足够好的level，由于索引前缀长度越长，足够好的level更大，
// 因此，这里是逆序遍历
for (n_prefix = n_uniq; n_prefix >= 1; n_prefix--) {
...
// 找到了足够好的level，跳转
if (level_is_analyzed &&
(n_diff_on_level[n_prefix - 1] >= n_diff_required || level == 1)) {
goto found_level;
}
// 没有找到足够好的level，继续寻找
if (level_is_analyzed && level > 1) {
/* if this does not hold we should be on
"found_level" instead of here */
ut_ad(n_diff_on_level[n_prefix - 1] < n_diff_required);
level--;
level_is_analyzed = false;
}
// 不断在B+树上向下寻找足够好的level
/* descend into the tree, searching for "good enough" level */
for (;;) {
...
// 计算该level是否足够好
const uint64_t prev_total_recs = total_recs;
if (!dict_stats_analyze_index_level(
index, level, n_diff_on_level, &total_recs, &total_pages,
n_diff_boundaries, wait_start_time, &mtr)) {
/* The other index->lock waiter is near to timeout.
We should reduce requested pages for safety. */
ut_ad(prev_total_recs <= n_sample_pages);
n_sample_pages = prev_total_recs / 2;
/* abort */
succeeded = false;
goto end;
}
level_is_analyzed = true;
if (level == 1 || n_diff_on_level[n_prefix - 1] >= n_diff_required) {
break;
}
level--;
level_is_analyzed = false;
}
// 找到了足够好的level，执行dict_stats_analyze_index_for_n_prefix开始dive。
found_level:
n_diff_data_t *data = &n_diff_data[n_prefix - 1];
data->level = level;
data->n_recs_on_level = total_recs;
data->n_diff_on_level = n_diff_on_level[n_prefix - 1];
data->n_leaf_pages_to_analyze =
std::min(n_sample_pages, n_diff_on_level[n_prefix - 1]);
if (!dict_stats_analyze_index_for_n_prefix(index, n_prefix,
&n_diff_boundaries[n_prefix - 1],
data, wait_start_time, &mtr)) {
/* The other index->lock waiter is near to timeout.
We should reduce requested pages for safety. */
ut_ad(data->n_leaf_pages_to_analyze <= n_sample_pages);
n_sample_pages = data->n_leaf_pages_to_analyze / 2;
/* abort */
succeeded = false;
goto end;
}
}
end:
...
return succeeded;
}
Dive 采样
在找到足够好的level后，将该level的所有distinct记录均分成n_sample_pages个segments或者distinct个segments(当distinct记录数小于n_sample_pages时)。在每个segment中，随机选取一条记录向下dive。这部分的逻辑在dict_stats_analyze_index_for_n_prefix()函数中。
dive的过程是直接遍历每一层Page上的记录，找到Page上第一条non-boring的记录，然后继续向下dive，直到leaf page。如果一条记录跟它的下一条记录的n_prefix列的值不完全同，则这条记录是non-boring的记录。这意味着它的下层page中存在变化的数据。这部分的逻辑在dict_stats_analyze_index_below_cur() 函数中。
以下是这两个函数的源代码，有兴趣的同学可以看一下：
static bool dict_stats_analyze_index_for_n_prefix(
dict_index_t *index, ulint n_prefix, const boundaries_t *boundaries,
n_diff_data_t *n_diff_data,
std::chrono::steady_clock::time_point &wait_start_time, mtr_t *mtr) {
...
/* Position pcur on the leftmost record on the leftmost page
on the desired level. */
pcur.open_at_side(true, index, BTR_SEARCH_TREE | BTR_ALREADY_S_LATCHED, true,
n_diff_data->level, mtr);
pcur.move_to_next_on_page();
page = pcur.get_page();
const rec_t *first_rec = pcur.get_rec();
...
// 获取这个level的最后一条记录的rec
const uint64_t last_idx_on_level =
boundaries->at(static_cast<unsigned>(n_diff_data->n_diff_on_level - 1));
rec_idx = 0;
n_diff_data->n_diff_all_analyzed_pages = 0;
n_diff_data->n_external_pages_sum = 0;
for (i = 0; i < n_diff_data->n_leaf_pages_to_analyze; i++) {
// 在这个level中，要进行n_leaf_pages_to_analyze次dive，因此划分为n_leaf_pages_to_analyze个seg
const uint64_t n_diff = n_diff_data->n_diff_on_level;
const uint64_t n_pick = n_diff_data->n_leaf_pages_to_analyze;
// seg的左端点和右端点
const uint64_t left = n_diff * i / n_pick;
const uint64_t right = n_diff * (i + 1) / n_pick - 1;
// 随机选取
const uint64_t rnd = ut::random_from_interval(left, right);
// 获取边界，即数据发生变化的记录的id
const uint64_t dive_below_idx = boundaries->at(rnd);
// 移动B+树上cursor
while (rec_idx < dive_below_idx && pcur.is_on_user_rec()) {
pcur.move_to_next_user_rec(mtr);
rec_idx++;
}
...
// 开始进行dive
uint64_t n_diff_on_leaf_page;
uint64_t n_external_pages;
dict_stats_analyze_index_below_cur(pcur.get_btr_cur(), n_prefix,
&n_diff_on_leaf_page, &n_external_pages);
// 为了避免相邻两次dive统计到连续的相同的两个数据，因此减1进行修正
if (n_diff_on_leaf_page > 0) {
n_diff_on_leaf_page--;
}
// 更新数据
n_diff_data->n_diff_all_analyzed_pages += n_diff_on_leaf_page;
n_diff_data->n_external_pages_sum += n_external_pages;
}
pcur.close();
if (i < n_diff_data->n_leaf_pages_to_analyze) {
/* return how much progressed */
n_diff_data->n_leaf_pages_to_analyze = i;
return false;
}
return true;
}
static void dict_stats_analyze_index_below_cur(const btr_cur_t *cur,
ulint n_prefix, uint64_t *n_diff,
uint64_t *n_external_pages) {
...
/* descend to the leaf level on the B-tree */
// 不断在B树上下降，直到leaf page
for (;;) {
block = buf_page_get_gen(page_id, page_size, RW_S_LATCH,
nullptr /* no guessed block */, Page_fetch::NORMAL,
UT_LOCATION_HERE, &mtr);
page = buf_block_get_frame(block);
if (btr_page_get_level(page) == 0) {
/* leaf level */
break;
}
/* else */
/* search for the first non-boring record on the page */
// 在这个page上寻找第一个non-boring记录，所谓non-boring其实就是数据发生变化的记录
offsets_rec =
dict_stats_scan_page(&rec, offsets1, offsets2, index, page, n_prefix,
QUIT_ON_FIRST_NON_BORING, n_diff, nullptr);
// 如果找不到，那么不用继续向下了，直接返回
if (*n_diff == 1) {
mtr_commit(&mtr);
/* page has all keys equal and the end of the page
was reached by dict_stats_scan_page(), no need to
descend to the leaf level */
mem_heap_free(heap);
/* can't get an estimate for n_external_pages here
because we do not dive to the leaf level, assume no
external pages (*n_external_pages was assigned to 0
above). */
return;
}
// 如果找到了，则从这个地方开始继续dive向下
page_id.set_page_no(btr_node_ptr_get_child_page_no(rec, offsets_rec));
}
// 遍历这个page，统计有多少distinct数据
offsets_rec =
dict_stats_scan_page(&rec, offsets1, offsets2, index, page, n_prefix,
srv_stats_include_delete_marked
? COUNT_ALL_NON_BORING_INCLUDE_DEL_MARKED
: COUNT_ALL_NON_BORING_AND_SKIP_DEL_MARKED,
n_diff, n_external_pages);
#if 0
DEBUG_PRINTF(" %s(): n_diff below page_no=%lu: " UINT64PF "\n",
__func__, page_no, n_diff);
#endif
mtr_commit(&mtr);
mem_heap_free(heap);
}
最后完成采样之后，就会按照n_leaf_pages * (q/p) * t
公式进行计算，得到n_diff_pfxNN统计量，对不同前缀长度的索引列都进行一遍上述流程，就可以得到完整的统计信息了。
更新时机
一般来说，只要表的统计信息是可以持久化的，都是通过dict_stats_update_persistent()函数进行统计信息更新，那么统计信息什么时候更新呢？
统计信息更新时机可以大致分为两种，第一种在ANALYZE语句，ALTER语句，TRUNCATE语句等执行时主动调用dict_stats_update_persistent()函数进行更新，第二种是在后台的dict_stats_thread线程中自动更新。
第一种情况很好理解，ANALYZE语句是主动更新统计信息的DDL语句，而TRUNCATE语句，ALTER语句等都会大量改变表内数据，因此也需要直接进行统计信息的更新。
第二种情况是通过dict_stats_thread后台线程进行更新。在MySQL中，recalc_pool是一个数组，保存了需要重新计算统计信息的表。dict_stats_thread的任务就是从recalc_pool中不断获取需要计算统计信息的表，执行dict_stats_update_persistent()函数。
接下来，我们看一下，一个表什么时候会被加入到recalc_pool中。在每次执行insert语句，update语句，delete语句修改一行时，都会调用row_update_statistics_if_needed()函数。在该函数中，会把modified_counter加一。如果发现modified_counter大于了当前表中总行数的1/10，则会把它加入到recalc_pool。
static inline void row_update_statistics_if_needed(
dict_table_t *table) /*!< in: table */
{
uint64_t counter;
uint64_t n_rows;
...
// 获取了改变了的行数
counter = table->stat_modified_counter++;
// 获取n_rows
n_rows = dict_table_get_n_rows(table);
// 对于统计信息可以持久化的表
if (dict_stats_is_persistent_enabled(table)) {
// 如果改变了的行数大于表总行数的1/10，加入到recal_pool中。
if (counter > n_rows / 10 /* 10% */
&& dict_stats_auto_recalc_is_enabled(table)) {
dict_stats_recalc_pool_add(table);
table->stat_modified_counter = 0;
}
return;
}
// 对于统计信息不可以持久化的表
// 如果改变了的行数大于（16 + 总行数/16），则更新统计信息。
if (counter > 16 + n_rows / 16 /* 6.25% */) {
ut_ad(!dict_sys_mutex_own());
/* this will reset table->stat_modified_counter to 0 */
dict_stats_update(table, DICT_STATS_RECALC_TRANSIENT);
}
}
Index Dive
Index dive是InnoDB存储引擎中估计范围内记录数的算法。在《浅析MySQL代价估计器》中，我们说到Index Range Scan做扫描行数的估计会用到Index dive算法，因此我们在这里也对这个算法进行介绍。
算法
Index dive算法其实非常简单，用下面这个例子来说明：
假如我们要估计key在(15,30)之间的记录数，在B+树中查找key = 15和key = 30两条数据，可以得到两条path。这两条path在level m发生了diverge(diverge代表在下一个level两条path会指向不同的page)。在level m-1发生了diverge_lot(diverge_lot意味着在下一个level，两条path指向的page不是相邻的)。当发生了diverge_lot后，意味着下一个level的记录数估计可能不可以精准计算出来了。
这时候就分两种情况，假设level m-2中，两条path之间的页面数小于10，那么就会逐个page去调用page_get_n_recs()函数获取记录数，这时候的估计还是准确的。如果两条path的页面数大于10，那么会读取前10个page，统计平均一个page有多少记录数。然后乘以在这个level中，两条path之间的page数（level m-2中两条path之间的page数其实就是level m-1中两条path之间的记录数）。
源码分析
这部分逻辑的源码在ha_innobase::records_in_range()中，感兴趣的同学可以去阅读一下。
直方图
直方图（histogram）是MySQL 8.0中新引入的，我们先通过一个例子简单看一下直方图的使用，先创建两张简单的表，：
create table t1 (id int primary key, col1 int);
create table t2 (id int primary key, col1 int);
然后向表t1，t2里插入相同的1k条数据：
delimiter //
create procedure batch_insert_t1 (end int)
begin
declare num int;
set num = 1;
while num < end do
insert into t1 values (num,num,num);
set num = num + 1;
end while;
end //
delimiter ;
call batch_insert_t1(1000);
# t2也相同操作
...
对于SQL：
select * from t1, t2 where t1.id = t2.id and t2.col1 > 1000 and t1.col1 < 1000;
按照我们在Join Reorder算法中所讲，如果考虑到predicate(断言)：t2.col1 >1000，那么如果先读t2表，使用predicate一过滤，只获得零条数据，再与表t1进行Join，肯定是最快的。我们尝试执行一下：
MySQL > explain select * from t1, t2 where t1.id = t2.id and t2.col1 > 1000 and t1.col1 < 1000;
+----+-------------+-------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | t1 | NULL | ALL | PRIMARY | NULL | NULL | NULL | 999 | 33.33 | Using where |
| 1 | SIMPLE | t2 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | t1.id | 1 | 33.33 | Using where |
+----+-------------+-------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
发现MySQL选择先读t1，然后将读出的每条数据在t2表上进行eq_ref获得匹配数据，这样的执行计划肯定不是最优的。
那么，MySQL为什么没有找到最优的执行计划呢？这是因为MySQL不知道t1表和t2表在col1上的数据分布，换言之，MySQL根本无法利用好t2.col1 > 1000这条predicate。
想要MySQL利用好t2.col1 > 1000这条predicate，最简单的方法是在t2.col1上建立索引，但索引会占用磁盘空间，并且降低insert，delete等语句的执行效率，如果我们只是想多一些统计信息辅助MySQL优化器获得更好的执行计划，那么直方图是一个很好的选择。
接下来，我们尝试建立直方图，并且再次执行SQL：
MySQL > analyze table t2 update histogram on col1;
+--------------+-----------+----------+-------------------------------------------------+
| Table | Op | Msg_type | Msg_text |
+--------------+-----------+----------+-------------------------------------------------+
| histogram.t2 | histogram | status | Histogram statistics created for column 'col1'. |
+--------------+-----------+----------+-------------------------------------------------+
MySQL > explain select * from t1, t2 where t1.id = t2.id and t2.col1 > 1000 and t1.col1 < 1000;
+----+-------------+-------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | t2 | NULL | ALL | PRIMARY | NULL | NULL | NULL | 999 | 0.10 | Using where |
| 1 | SIMPLE | t1 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | t2.id | 1 | 33.33 | Using where |
+----+-------------+-------+------------+--------+---------------+---------+---------+-------+------+----------+-------------+
可以发现，MySQL这次选择先读t2表，再读t1。对比前后的执行计划，可以发现对t2表的filtered由33.33降到了0.1，这正是直方图发挥的作用。
执行计划的filtered衡量了经过where_cond过滤后所剩的行数的占比，如果没有直方图，那么MySQL使用默认的占比：
| preidcate类型 | filtered(%) |
|---|---|
| \= | 10 |
| <> 或者 != | 90 |
| < 或者 > | 33.33 |
| Between | 11.11 |
| IN | Min(条目*10, 50) |
在没有直方图时，两个表上都只有一个 “< 或者 >” 类型的predicate，因此filtered为33.33%，意味着如果从表中读到100条记录，那么估计会有33.33条记录满足predicate。而添加了直方图后，明显得到了更准确的估计。
直方图类型
直方图其实就是把数据“分桶”，最简单的直方图的是等宽直方图，如下图所示：
等宽直方图，引用自http://mysql.taobao.org/monthly/2021/05/03/
如果有了这张直方图，我们就可以很清晰地知道如果有predicate是col1 > 100，那么它会过滤掉所有的数据。但这种直方图会严重地受到数据分布的影响而产生大的偏差。在MySQL中，实现了Singleton和等高直方图两种。
Singleton记录了每个distinct value出现的频次，能够提供最为精确的分布信息，但内存占用很高。
等高直方图保证了每个区间内的数据量是一致的，但区间范围大小是不一致的，能够有效解决数据分布不均匀带来的偏差。
等高直方图，引用自http://mysql.taobao.org/monthly/2021/05/03/
统计算法
首先我们先来想一个问题，直方图的统计算法会像InnoDB统计信息的统计算法一样精确么？其实是不能的。
InnoDB统计信息的统计算法能使用重要性采样原理的根本原因是B+树的有序特性，但在建立直方图的列上并不存在索引，也就不存在有序性，因此，只能从leaf page上随机采样。
源码分析
直方图的创建，查询的源码分析在本文就不过多展开了。只是简单地说一下原理。
直方图的创建本质上就是随机采样，维护一个Value_maps记录出现的distinct值和出现的频次，最后根据所使用的直方图类型创建出所需的直方图，相关代码在update_histogram()函数中。
而直方图的查询本质上就是根据where_cond中predicate去计算filtered（其实就是selectivity），主要逻辑在 Histogram::get_selectivity_dispatcher()函数中，该函数会根据不同的preidcate类型在直方图上计算filtered。
更新时机
对于直方图，除非显式地执行analyze table table_name update histogram on col_name;语句，否则不会更新。
其他统计信息
在MySQL中，还有一些其他统计信息，例如在前面的浅析代价估计器一文中提到，在table_scan的cost时，会根据page在buffer pool还是在disk上给出不同的代价估计值。因此，我们将MySQL中用到的其它统计信息总结到这里。
table_in_mem_estimate
这个统计信息描述了该表在内存中的占比估计。对于InnoDB表而言，就是它的主键索引的page在内存中的占比估计。
在InnoDB中，buf_stat_per_index_t类维护了每个index在buffer pool中缓存了多少页，该类的主要数据结构就是一个无锁哈希表，key是index id，而value是该index在buffer pool中缓存了多少页。 在每次page的IO完成时，都会更新对buf_stat_per_index_t进行更新。
index_in_mem_estimate
对于索引页，同样需要估计索引在内存中的占比，该统计信息的统计方式和table_in_mem_estimate统计信息的统计方式相同。
总结
首先我们用一个表格来总结这些统计信息一般用在什么地方：
在本文中，对MySQL中常见的统计信息进行了简单地介绍，统计信息的好坏直接决定了MySQL能否找到好的执行计划，在实践中也可以看到很多由于统计信息不准导致的慢SQL，希望本文能够有助于大家理解MySQL中的统计信息的统计方式。最后，如果有错漏之处，还请大家指出。
附：
通过一个例子来看optimizer trace的使用：
建表，插入数据：
CREATE TABLE t1 (
id int PRIMARY KEY AUTO_INCREMENT,
col1 int,
col2 int
);
CREATE TABLE t2 (
id int PRIMARY KEY AUTO_INCREMENT,
col1 int,
col2 int,
KEY index_col1 (col1)
);
CREATE TABLE t3 (
id int PRIMARY KEY AUTO_INCREMENT,
col1 int,
col2 int,
KEY index_col2 (col2)
);
# 插入一些数据
delimiter //
create procedure insertData()
begin
declare num int;
set num = 1;
while num <= 100000 do
insert into t1 values (null, rand() * 5000, rand() * 5000);
insert into t2 values (null, rand() * 5000, rand() * 5000);
insert into t3 values (null, rand() * 5000, rand() * 5000);
set num = num + 1;
end while;
end //
delimiter ;
开启optimizer trace，执行SQL：
set optimizer_trace = 'enabled=on';
EXPLAIN SELECT *
FROM t1, t2, t3
WHERE t1.id = t2.col1
AND t3.col1 = t2.col1
AND t2.id > 95000
AND t3.col2 > 4900;
+----+-------------+-------+------------+--------+--------------------+---------+---------+--------------+-------+----------+--------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+--------+--------------------+---------+---------+--------------+-------+----------+--------------------------------------------+
| 1 | SIMPLE | t2 | NULL | range | PRIMARY,index_col1 | PRIMARY | 4 | NULL | 1 | 100.00 | Using where |
| 1 | SIMPLE | t1 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | test.t2.col1 | 1 | 100.00 | NULL |
| 1 | SIMPLE | t3 | NULL | ALL | index_col2 | NULL | NULL | NULL | 97660 | 4.09 | Using where; Using join buffer (hash join) |
+----+-------------+-------+------------+--------+--------------------+---------+---------+--------------+-------+----------+--------------------------------------------+
查询optimizer trace
mysql> SELECT trace FROM information_schema.optimizer_trace \G
打印出来的optimizer_trace非常长，建议大家可以找个json viewer方便分析：
整个steps其实就分为三个部分，preparation（Query_block::prapre()），optimizatoin（JOIN::optimize()），explain/execution（执行时记录的trace）。
preparation
其中，在preparation中，主要进行了：
bind
子查询的重写
派生表的重写
会将重写过的SQL进行记录：
optimization
optimziation进行的步骤就非常多，这里主要包括了
condition_processing：condition的处理
substitute_generated_columns：虚拟列的替换
table_dependenceis：表之间的依赖
ref_optimzier_key_uses：分析哪些key能够用来ref
row_estimation：单表access path分析
considered_execution_plans：join reorder
attaching_conditions_to_tables：将conditions和表进行连接
finalizing_table_conditions：去除掉冗余的predicate
refine_plan：对执行计划做refine
其中，我们主要关注row_estimation和considered_execution_plans，这两步对执行计划的影响最大：
从这里面，我们看到很多熟悉的Access Path，其实这步就是对每一个表进行Access Path的分析。
在considered_execution_plans中，就是对Join order进行枚举，可以看到considered_execution_plans->0对应了枚举到t3，然后在rest_of_plan中枚举到t2，进一步枚举到t3。
Execution/Explain
主要是在执行时记录trace，会记录例如子查询的执行信息等。
完整的json
{
"steps": [
{
"join_preparation": {
"select#": 1,
"steps": [
{
"expanded_query": "/* select#1 */ select `t1`.`id` AS `id`,`t1`.`col1` AS `col1`,`t1`.`col2` AS `col2`,`t2`.`id` AS `id`,`t2`.`col1` AS `col1`,`t2`.`col2` AS `col2`,`t3`.`id` AS `id`,`t3`.`col1` AS `col1`,`t3`.`col2` AS `col2` from `t1` join `t2` join `t3` where ((`t1`.`id` = `t2`.`col1`) and (`t3`.`col1` = `t2`.`col1`) and (`t2`.`id` > 95000) and (`t3`.`col2` > 4900))"
}
]
}
},
{
"join_optimization": {
"select#": 1,
"steps": [
{
"condition_processing": {
"condition": "WHERE",
"original_condition": "((`t1`.`id` = `t2`.`col1`) and (`t3`.`col1` = `t2`.`col1`) and (`t2`.`id` > 95000) and (`t3`.`col2` > 4900))",
"steps": [
{
"transformation": "equality_propagation",
"resulting_condition": "((`t2`.`id` > 95000) and (`t3`.`col2` > 4900) and multiple equal(`t1`.`id`, `t2`.`col1`, `t3`.`col1`))"
},
{
"transformation": "constant_propagation",
"resulting_condition": "((`t2`.`id` > 95000) and (`t3`.`col2` > 4900) and multiple equal(`t1`.`id`, `t2`.`col1`, `t3`.`col1`))"
},
{
"transformation": "trivial_condition_removal",
"resulting_condition": "((`t2`.`id` > 95000) and (`t3`.`col2` > 4900) and multiple equal(`t1`.`id`, `t2`.`col1`, `t3`.`col1`))"
}
]
}
},
{
"substitute_generated_columns": {
}
},
{
"table_dependencies": [
{
"table": "`t1`",
"row_may_be_null": false,
"map_bit": 0,
"depends_on_map_bits": [
]
},
{
"table": "`t2`",
"row_may_be_null": false,
"map_bit": 1,
"depends_on_map_bits": [
]
},
{
"table": "`t3`",
"row_may_be_null": false,
"map_bit": 2,
"depends_on_map_bits": [
]
}
]
},
{
"ref_optimizer_key_uses": [
{
"table": "`t1`",
"field": "id",
"equals": "`t2`.`col1`",
"null_rejecting": true
},
{
"table": "`t1`",
"field": "id",
"equals": "`t3`.`col1`",
"null_rejecting": true
},
{
"table": "`t2`",
"field": "col1",
"equals": "`t1`.`id`",
"null_rejecting": true
},
{
"table": "`t2`",
"field": "col1",
"equals": "`t3`.`col1`",
"null_rejecting": true
}
]
},
{
"rows_estimation": [
{
"table": "`t1`",
"table_scan": {
"rows": 100254,
"cost": 56.25
}
},
{
"table": "`t2`",
"range_analysis": {
"table_scan": {
"rows": 100254,
"cost": 10083.8
},
"potential_range_indexes": [
{
"index": "PRIMARY",
"usable": true,
"key_parts": [
"id"
]
},
{
"index": "index_col1",
"usable": false,
"cause": "not_applicable"
}
],
"setup_range_conditions": [
],
"group_index_range": {
"chosen": false,
"cause": "not_single_table"
},
"skip_scan_range": {
"chosen": false,
"cause": "not_single_table"
},
"analyzing_range_alternatives": {
"range_scan_alternatives": [
{
"index": "PRIMARY",
"ranges": [
"95000 < id"
],
"index_dives_for_eq_ranges": true,
"rowid_ordered": true,
"using_mrr": false,
"index_only": false,
"in_memory": 1,
"rows": 9072,
"cost": 909.685,
"chosen": true
}
],
"analyzing_roworder_intersect": {
"usable": false,
"cause": "too_few_roworder_scans"
}
},
"chosen_range_access_summary": {
"range_access_plan": {
"type": "range_scan",
"index": "PRIMARY",
"rows": 9072,
"ranges": [
"95000 < id"
]
},
"rows_for_plan": 9072,
"cost_for_plan": 909.685,
"chosen": true
}
}
},
{
"table": "`t3`",
"range_analysis": {
"table_scan": {
"rows": 97660,
"cost": 9824.35
},
"potential_range_indexes": [
{
"index": "PRIMARY",
"usable": false,
"cause": "not_applicable"
},
{
"index": "index_col2",
"usable": true,
"key_parts": [
"col2",
"id"
]
}
],
"setup_range_conditions": [
],
"group_index_range": {
"chosen": false,
"cause": "not_single_table"
},
"skip_scan_range": {
"chosen": false,
"cause": "not_single_table"
},
"analyzing_range_alternatives": {
"range_scan_alternatives": [
{
"index": "index_col2",
"ranges": [
"4900 < col2"
],
"index_dives_for_eq_ranges": true,
"rowid_ordered": false,
"using_mrr": false,
"index_only": false,
"in_memory": 1,
"rows": 1990,
"cost": 696.76,
"chosen": true
}
],
"analyzing_roworder_intersect": {
"usable": false,
"cause": "too_few_roworder_scans"
}
},
"chosen_range_access_summary": {
"range_access_plan": {
"type": "range_scan",
"index": "index_col2",
"rows": 1990,
"ranges": [
"4900 < col2"
]
},
"rows_for_plan": 1990,
"cost_for_plan": 696.76,
"chosen": true
}
}
}
]
},
{
"considered_execution_plans": [
{
"plan_prefix": [
],
"table": "`t3`",
"best_access_path": {
"considered_access_paths": [
{
"rows_to_scan": 1990,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "range",
"range_details": {
"used_index": "index_col2"
},
"resulting_rows": 1990,
"cost": 895.76,
"chosen": true
}
]
},
"condition_filtering_pct": 100,
"rows_for_plan": 1990,
"cost_for_plan": 895.76,
"rest_of_plan": [
{
"plan_prefix": [
"`t3`"
],
"table": "`t2`",
"best_access_path": {
"considered_access_paths": [
{
"access_type": "ref",
"index": "index_col1",
"rows": 20.7008,
"cost": 14418.1,
"chosen": true
},
{
"rows_to_scan": 9072,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "range",
"range_details": {
"used_index": "PRIMARY"
},
"resulting_rows": 9072,
"cost": 3.6156e+06,
"chosen": false
}
]
},
"condition_filtering_pct": 9.04902,
"rows_for_plan": 3727.71,
"cost_for_plan": 15313.9,
"rest_of_plan": [
{
"plan_prefix": [
"`t3`",
"`t2`"
],
"table": "`t1`",
"best_access_path": {
"considered_access_paths": [
{
"access_type": "eq_ref",
"index": "PRIMARY",
"rows": 1,
"cost": 870.271,
"chosen": true,
"cause": "clustered_pk_chosen_by_heuristics"
},
{
"rows_to_scan": 100254,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "scan",
"using_join_cache": true,
"buffers_needed": 1,
"resulting_rows": 100254,
"cost": 3.73718e+07,
"chosen": false
}
]
},
"condition_filtering_pct": 100,
"rows_for_plan": 3727.71,
"cost_for_plan": 16184.1,
"chosen": true
}
]
},
{
"plan_prefix": [
"`t3`"
],
"table": "`t1`",
"best_access_path": {
"considered_access_paths": [
{
"access_type": "eq_ref",
"index": "PRIMARY",
"rows": 1,
"cost": 696.5,
"chosen": true,
"cause": "clustered_pk_chosen_by_heuristics"
},
{
"rows_to_scan": 100254,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "scan",
"using_join_cache": true,
"buffers_needed": 1,
"resulting_rows": 100254,
"cost": 1.99506e+07,
"chosen": false
}
]
},
"condition_filtering_pct": 100,
"rows_for_plan": 1990,
"cost_for_plan": 1592.26,
"rest_of_plan": [
{
"plan_prefix": [
"`t3`",
"`t1`"
],
"table": "`t2`",
"best_access_path": {
"considered_access_paths": [
{
"access_type": "ref",
"index": "index_col1",
"rows": 20.7008,
"cost": 14418.1,
"chosen": true
},
{
"rows_to_scan": 9072,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "range",
"range_details": {
"used_index": "PRIMARY"
},
"resulting_rows": 9072,
"cost": 3.6156e+06,
"chosen": false
}
]
},
"added_to_eq_ref_extension": false
},
{
"plan_prefix": [
"`t3`",
"`t1`"
],
"table": "`t2`",
"best_access_path": {
"considered_access_paths": [
{
"access_type": "ref",
"index": "index_col1",
"rows": 20.7008,
"cost": 14418.1,
"chosen": true
},
{
"rows_to_scan": 9072,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "range",
"range_details": {
"used_index": "PRIMARY"
},
"resulting_rows": 9072,
"cost": 3.6156e+06,
"chosen": false
}
]
},
"condition_filtering_pct": 9.04902,
"rows_for_plan": 3727.71,
"cost_for_plan": 16010.4,
"chosen": true
}
]
}
]
},
{
"plan_prefix": [
],
"table": "`t2`",
"best_access_path": {
"considered_access_paths": [
{
"access_type": "ref",
"index": "index_col1",
"usable": false,
"chosen": false
},
{
"rows_to_scan": 9072,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "range",
"range_details": {
"used_index": "PRIMARY"
},
"resulting_rows": 9072,
"cost": 1816.88,
"chosen": true
}
]
},
"condition_filtering_pct": 100,
"rows_for_plan": 9072,
"cost_for_plan": 1816.88,
"pruned_by_heuristic": true
},
{
"plan_prefix": [
],
"table": "`t1`",
"best_access_path": {
"considered_access_paths": [
{
"access_type": "ref",
"index": "PRIMARY",
"usable": false,
"chosen": false
},
{
"rows_to_scan": 100254,
"filtering_effect": [
],
"final_filtering_effect": 1,
"access_type": "scan",
"resulting_rows": 100254,
"cost": 10081.7,
"chosen": true
}
]
},
"condition_filtering_pct": 100,
"rows_for_plan": 100254,
"cost_for_plan": 10081.7,
"pruned_by_heuristic": true
}
]
},
{
"attaching_conditions_to_tables": {
"original_condition": "((`t1`.`id` = `t3`.`col1`) and (`t2`.`col1` = `t3`.`col1`) and (`t2`.`id` > 95000) and (`t3`.`col2` > 4900))",
"attached_conditions_computation": [
],
"attached_conditions_summary": [
{
"table": "`t3`",
"attached": "((`t3`.`col2` > 4900) and (`t3`.`col1` is not null))"
},
{
"table": "`t1`",
"attached": "(`t1`.`id` = `t3`.`col1`)"
},
{
"table": "`t2`",
"attached": "((`t2`.`col1` = `t3`.`col1`) and (`t2`.`id` > 95000))"
}
]
}
},
{
"finalizing_table_conditions": [
{
"table": "`t3`",
"original_table_condition": "((`t3`.`col2` > 4900) and (`t3`.`col1` is not null))",
"final_table_condition ": "((`t3`.`col2` > 4900) and (`t3`.`col1` is not null))"
},
{
"table": "`t1`",
"original_table_condition": "(`t1`.`id` = `t3`.`col1`)",
"final_table_condition ": null
},
{
"table": "`t2`",
"original_table_condition": "((`t2`.`col1` = `t3`.`col1`) and (`t2`.`id` > 95000))",
"final_table_condition ": "(`t2`.`id` > 95000)"
}
]
},
{
"refine_plan": [
{
"table": "`t3`",
"pushed_index_condition": "(`t3`.`col2` > 4900)",
"table_condition_attached": "(`t3`.`col1` is not null)"
},
{
"table": "`t1`"
},
{
"table": "`t2`",
"pushed_index_condition": "(`t2`.`id` > 95000)",
"table_condition_attached": null
}
]
}
]
}
},
{
"join_explain": {
"select#": 1,
"steps": [
]
}
}
]
}
作者简介
田镜祺，AliSQL内核研发人员。当前主要从事SQL优化执行、DDL相关的研发和RDS运维工作。
