本文基于当前最新的MySQL8.0.12版本，主要是讲下cost model 和 histogram的用法和相关代码

为什么需要配置cost model常量 ? 我们知道MySQL已经发展了好几十年的历史，但是在优化器中依然使用了hardcode的权重值来衡量io, cpu等资源情况，而这些权重值实际上是基于多年前甚至十来年前的经验设定的。想想看，这么多年硬件的发展多么迅速。几十上百个核心的服务器不在少数甚至在某些大型公司大规模使用，ssd早就成为主流，NVME也在崛起。高速RDMA网络正在走入寻常百姓家。这一切甚至影响到数据库系统的实现和变革。显而易见，那些hardcode的权值已经过时了，我们需要提供给用户可定义的方式，甚至更进一步的，能够智能的根据硬件环境自动设定。

MySQL5.7引入两个新的系统表, 通过这两个系统表暴露给用户来进行更新，如下：

你可以通过update语句来进行更新, 例如：

  2. Query OK, 1 row affected (0.05 sec)
  3.   Rows matched: 1  Changed: 1  Warnings: 0
  5.   root@(none) 04:07:13>select * from mysql.server_cost where cost_name = 'disk_temptable_create_cost';
  6.   +----------------------------+------------+---------------------+---------+---------------+
  7.   | cost_name                  | cost_value | last_update         | comment | default_value |
  8.   +----------------------------+------------+---------------------+---------+---------------+
  9.   | disk_temptable_create_cost |         40 | 2018-06-23 16:07:05 | NULL    |            20 |
  10.   +----------------------------+------------+---------------------+---------+---------------+
  11. 1 row in set (0.00 sec)
  14.   //更新后执行一次flush optimizer_costs操作来更新内存
  15.   //但老的session还是会用老的cost数据
  16.   root@(none) 10:10:12>flush optimizer_costs;
  17. Query OK, 0 rows affected (0.00 sec)

可以看到用法也非常简单，上面包含了两张表：server_cost及engine_cost，分别对server层和引擎层进行配置

相关代码:

全局cache Cost_constant_cache

全局cache维护了一个当前的cost model信息, 用户线程在lex_start时会去判断其有没有初始化本地指针，如果没有的话就去该cache中将指针拷贝到本地

初始化全局cache:

  1.   Cost_constant_cache::init
  2.   :
  4.   创建Cost_model_constants， 其中包含了两类信息: server层cost model和引擎层cost model, 类结构如下：
  7.   Cost_constant_cache ----> Cost_model_constants
  8.                        ---> Server_cost_constants
  9.                             //server_cost
  10.                        ---> Cost_model_se_info
  11.                             --->SE_cost_constants
  12.                             //engine_cost 如果存储引擎提供了接口函数get_cost_constants的话,则从存储引擎那取

从系统表读取配置，适用于初始化和flush optimizer_costs并更新cache：

  1. read_cost_constants()
  2.   |--> read_server_cost_constants
  3.   |--> read_engine_cost_constants

由于用户可以动态的更新系统表，执行完flush optimizer_costs后，有可能老的版本还在被某些session使用，因此需要引用计数，老的版本ref counter被降为0后才能被释放

线程cost model初始化

  • Cost_model_server

在每个线程的thd上，挂了一个Cost_model_server的对象THD::m_cost_model, 在lex_start()时，如果发现线程的m_cost_model没有初始化，就会去获取全局的指针，存储到本地：

  1.   Cost_model_server::init
  3.   const Cost_model_constants *m_cost_constants = cost_constant_cache->get_cost_constants();
  4.   // 会增加一个引用计数，以确保不会在引用时被删除
  6.   const Server_cost_constants *m_server_cost_constants = m_cost_constants->get_server_cost_constants();
  7.   // 同样获取的是全局指针

可见thd不创建自己的cost model, 只引用cache中的指针

Table Cost Model

struct TABLE::m_cost_model, 类型：Cost_model_table

其值取自上述thd中存储的cost model对象

Cost_estimate

统一的对象类型cost_estimate来存储计算的cost结果，包含四个维度：

未来

目前来看，除非根据工作负载，经过充分的测试才能得出合理的配置值，但如何配置，什么是合理的值，个人认为应该是可以自动调整配置的。关键是找出配置和硬件条件的对应关系。 这也是我们未来可以努力的一个方向。

1. Cost Model官方文档 3. 官方博客2: A new dimension to MySQL query optimizations 5.Slide: MySQL Cost Model

Related Worklog:
WL#7209: Handler interface changes for new cost model WL#7315 Optimizer cost model: main memory management of cost constants

使用

MySQL里使用直方图是通过ANALYZE TABLE语法来执行：

  1.   ANALYZE [NO_WRITE_TO_BINLOG | LOCAL]
  2.   TABLE tbl_name
  3.   UPDATE HISTOGRAM ON col_name [, col_name] ...
  4.   [WITH N BUCKETS]
  6.   ANALYZE [NO_WRITE_TO_BINLOG | LOCAL]
  7.   TABLE tbl_name
  8.   DROP HISTOGRAM ON col_name [, col_name] ...

举个简单的例子：

  1.   我们以普通的sysbench表为例：
  3.   root@sb1 05:16:33>show create table sbtest1\G
  4.   *************************** 1. row ***************************
  5.   Table: sbtest1
  6.   Create Table: CREATE TABLE `sbtest1` (
  7.       `id` int(11) NOT NULL AUTO_INCREMENT,
  8.       `k` int(11) NOT NULL DEFAULT '0',
  9.       `c` char(120) NOT NULL DEFAULT '',
  10.       `pad` char(60) NOT NULL DEFAULT '',
  11.       PRIMARY KEY (`id`),
  12.       KEY `k_1` (`k`)
  13.       ) ENGINE=InnoDB AUTO_INCREMENT=200001 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
  14. 1 row in set (0.01 sec)
  17. # 创建直方图并存储到数据词典中
  19.   +-------------+-----------+----------+----------------------------------------------+
  20.   | Table       | Op        | Msg_type | Msg_text                                     |
  21.   +-------------+-----------+----------+----------------------------------------------+
  22.   | sb1.sbtest1 | histogram | status   | Histogram statistics created for column 'k'. |
  23.   +-------------+-----------+----------+----------------------------------------------+
  24. 1 row in set (0.55 sec)
  26.   root@sb1 05:17:03>ANALYZE TABLE sbtest1 UPDATE HISTOGRAM ON k,pad with 10 BUCKETS;
  27.   +-------------+-----------+----------+------------------------------------------------+
  28.   | Table       | Op        | Msg_type | Msg_text                                       |
  29.   +-------------+-----------+----------+------------------------------------------------+
  30.   | sb1.sbtest1 | histogram | status   | Histogram statistics created for column 'k'.   |
  32.   +-------------+-----------+----------+------------------------------------------------+
  33. 2 rows in set (7.98 sec)
  35.   删除pad列上的histogram:
  36.   root@sb1 05:17:51>ANALYZE TABLE sbtest1 DROP HISTOGRAM ON pad;
  37.   +-------------+-----------+----------+------------------------------------------------+
  38.   | Table       | Op        | Msg_type | Msg_text                                       |
  39.   +-------------+-----------+----------+------------------------------------------------+
  40.   | sb1.sbtest1 | histogram | status   | Histogram statistics removed for column 'pad'. |
  41.   +-------------+-----------+----------+------------------------------------------------+
  42. 1 row in set (0.06 sec)
  44.   root@sb1 05:58:12>ANALYZE TABLE sbtest1 DROP HISTOGRAM ON k;
  45.   +-------------+-----------+----------+----------------------------------------------+
  46.   | Table       | Op        | Msg_type | Msg_text                                     |
  47.   +-------------+-----------+----------+----------------------------------------------+
  48.   | sb1.sbtest1 | histogram | status   | Histogram statistics removed for column 'k'. |
  49.   +-------------+-----------+----------+----------------------------------------------+
  50. 1 row in set (0.08 sec)
  53. # 如果不指定bucket的话，默认Bucket的数量是100
  55.   root@sb1 05:58:27>ANALYZE TABLE sbtest1 UPDATE HISTOGRAM ON k;
  56.   +-------------+-----------+----------+----------------------------------------------+
  57.   | Table       | Op        | Msg_type | Msg_text                                     |
  58.   +-------------+-----------+----------+----------------------------------------------+
  59.   | sb1.sbtest1 | histogram | status   | Histogram statistics created for column 'k'. |
  60.   +-------------+-----------+----------+----------------------------------------------+
  61. 1 row in set (0.56 sec)

直方图统计信息存储于InnoDB数据词典中，可以通过information_schema表来获取

  1.   root@information_schema 05:34:49>SHOW CREATE TABLE INFORMATION_SCHEMA.COLUMN_STATISTICS\G
  2.   *************************** 1. row ***************************
  3.   View: COLUMN_STATISTICS
  4. Create View: CREATE ALGORITHM=UNDEFINED DEFINER=`mysql.infoschema`@`localhost` SQL SECURITY DEFINER VIEW `COLUMN_STATISTICS` AS select `mysql`.`column_statistics`.`schema_name` AS `SCHEMA_NAME`,`mysql`.`column_statistics`.`table_name` AS `TABLE_NAME`,`mysql`.`column_statistics`.`column_name` AS `COLUMN_NAME`,`mysql`.`column_statistics`.`histogram` AS `HISTOGRAM` from `mysql`.`column_statistics` where can_access_table(`mysql`.`column_statistics`.`schema_name`,`mysql`.`column_statistics`.`table_name`)
  5.   character_set_client: utf8
  6.   collation_connection: utf8_general_ci
  7. 1 row in set (0.00 sec)

从column_statistics表的定义可以看到，有一个名为mysql.column_statistics系统表，但被隐藏了，没有对外暴露

以下举个简单的例子：

  1.   root@sb1 05:58:55>ANALYZE TABLE sbtest1 UPDATE HISTOGRAM ON k WITH 4 BUCKETS;
  2.   +-------------+-----------+----------+----------------------------------------------+
  3.   | Table       | Op        | Msg_type | Msg_text                                     |
  4.   +-------------+-----------+----------+----------------------------------------------+
  5.   | sb1.sbtest1 | histogram | status   | Histogram statistics created for column 'k'. |
  6.   +-------------+-----------+----------+----------------------------------------------+
  7. 1 row in set (0.63 sec)
  9. # 查询表上的直方图信息
  11.   root@sb1 06:00:43>SELECT JSON_PRETTY(HISTOGRAM) FROM INFORMATION_SCHEMA.COLUMN_STATISTICS WHERE SCHEMA_NAME='sb1' AND TABLE_NAME = 'sbtest1'\G
  12.   *************************** 1. row ***************************
  13.   JSON_PRETTY(HISTOGRAM): {
  14.     "buckets": [
  15.       [
  16.       38671,
  17.       99756,
  18.       0.249795,
  19.       17002
  20.         ],
  21.       [
  22.         99757,
  23.       100248,
  24.       0.500035,
  25.       492
  26.         ],
  27.       [
  28.         100249,
  29.       100743,
  30.       0.749945,
  31.       495
  32.       [
  33.         100744,
  34.       172775,
  35.       1.0,
  36.       16630
  37.         ]
  38.         ],
  39.       "data-type": "int",
  41.       "collation-id": 8,
  42.       "last-updated": "2018-09-22 09:59:30.857797",
  43.       "sampling-rate": 1.0,
  44.       "histogram-type": "equi-height",
  45.       "number-of-buckets-specified": 4
  46.   }
  47. 1 row in set (0.00 sec)

从输出的json可以看到，在执行了上述语句后产生的直方图，有4个bucket，数据类型为Int, 类型为equi-height，即等高直方图(另外一种是等宽直方图，即SINGLETON)。每个Bucket中，描述的信息包括：数值的上界和下界, 频率以及不同值的个数。通过这些信息可以获得比较精确的数据分布情况，从而优化器来根据这些统计信息决定更优的执行计划。

如果列上存在大量的重复值，那么MySQL也可能选择等宽直方图，例如上例，我们将列k上的值更新为一半10一半为20， 那么出来的直方图数据如下：

如上，对于SINGLETON类型，每个bucket只包含两个值：列值，及对应的累计频率（即百分之多少的数据比当前Bucket里的值要小或相等）

注意这里的sampling-rate, 这里的值为1，表示读取了表上所有的数据来进行统计，但通常对于大表而言，我们可能不希望读太多的数据，因为可能产生过度的内存消耗，因此MySQL还提供了一个参数来限制内存的使用上限。

如果表上的DML不多，那直方图基本是稳定的，但频繁写入的话，那我们就可能需要去定期更新直方图，MySQL本身不会去主动更新。

优化器通过histogram来计算列的过滤性，大多数的谓词都可以使用到。具体参阅官方文档

关于直方图影响查询计划，这篇 及 这篇博客

相关代码

代码结构： 以MySQL8.0.12为例，主要代码在sql/histogram目录下:

  1.   ls sql/histograms/
  2.   equi_height_bucket.cc  
  3.   equi_height_bucket.h  
  4.   equi_height.cc  
  5.   equi_height.h  histogram.cc  
  6.   histogram.h  singleton.cc  
  7.   singleton.h  
  8.   value_map.cc  
  9.   value_map.h  
  10.   value_map_type.h
  13.   类结构：
  15.   namespace histograms
  16.   |---> Histogram  //基类
  17.            |--> Equi_height //等高直方图，模板类，实例化参数为数据类型，需要针对类型显示定义
  18.            // 见文件 "equi_height.cc"
  19.            |--> Singleton
  20.            //等宽直方图，只有值和其出现的频度被存储下来

创建及存储histogram:

处理histogram的相关函数和堆栈如下:

  1.   Sql_cmd_analyze_table::handle_histogram_command
  2.   |--> update_histogram  //更新histogram
  3.      |-->histograms::update_histogram  //调用namespace内的接口函数
  4.            a. 判断各个列：
  5.            //histograms::field_type_to_value_map_type:  检查列类型是否支持
  6.            //covered_by_single_part_index: 如果列是Pk或者uk，不会为其创建histogram
  7.            //如果是generated column, 则找到其依赖的列加入到set中
  8.            b. 判断取样的半分比，这主要受参数histogram_generation_max_mem_size限制，如果设的足够大，则会去读取全表数据进行分析
  9.            |-> fill_value_maps   //开始从表上读取需要分析的列数据
  10.                |->ha_sample_init
  11.                |->ha_sample_next
  12.                    |-->  handler::sample_next //读取下一条记录，通过随机数的方式来进行取样
  13.                Value_map<T>::add_values // 将读到的数据加入到map中
  14.                |->...
  15.                |->ha_sample_end
  17.            |-> build_histogram //创建histogram对象
  18.            a. 确定histogram类型：如果值的个数小于桶的个数，则使用Singleton，否则使用Equi_height类型
  19.                |->Singleton<T>::build_histogram
  20.                |->Equi_height<T>::build_histogram
  22.            |-> Histogram::store_histogram //将histogram信息存储到column_statistic表中
  23.                |-> dd::cache::Dictionary_client::update<dd::Column_statistics>
  25.   |--> drop_histogram //删除直方图

使用histogram

使用的方式就比较简单了:

获取列值过滤性的相关堆栈如下：

  1.   get_histogram_selectivity
  2.        |-->Histogram::get_selectivity
  3.            |->get_equal_to_selectivity_dispatcher
  4.            |->get_greater_than_selectivity_dispatcher
  5.            |->get_less_than_selectivity_dispatcher
  6.        |-->write_histogram_to_trace // 写到optimizer_trace中

MySQL支持多种操作类型对直方图的使用，包括：

  1.   col_name = constant
  2.   col_name <> constant
  3.   col_name != constant
  4.   col_name > constant
  5.   col_name < constant
  6.   col_name >= constant
  7.   col_name <= constant
  8.   col_name IS NULL
  9.   col_name IS NOT NULL
  10.   col_name BETWEEN constant AND constant
  11.   col_name NOT BETWEEN constant AND constant
  12.   col_name IN (constant[, constant] ...)
  13. col_name NOT IN (constant[, constant] ...)

通过直方图，我们可以根据列上的条件判断出列值的过滤性，来辅助选择更优的执行计划。在没有直方图之前我们需要通过在列上建立索引来获得相对精确的列值分布。但我们知道索引是有很大的维护开销的，而直方图则可以灵活的按需创建。

WL#8706 Persistent storage of Histogram data WL#8943 Extend ANALYZE TABLE with histogram support

优化rec_per_key

相关worklog: WL#7338: Interface for improved records per key estimates

MySQL通过rec_per_key 接口来估算记录的个数（暗示每个索引Key对应的记录个数），但在早前版本中这个数字是整数，对于小数会取整，不能表示准确的rec_per_key，从而影响到索引的选择，因此在5.7版本中，将其记录的值改成了float类型

引入数据cache状态计算开销

相关worklog:

WL#7168 API for estimates for how much of table and index data that is in memory buffer WL#7340 IO aware cost estimate function for data access

在之前的版本中，优化器是无法知道数据的状态，是否是cache在内存中，还是需要从磁盘读出来的，缺乏这部分信息，导致优化器统一认为数据属于磁盘的来计算开销。这可能导致低效的执行计划。

相关代码：

server层新增api，用于获取表或索引上有百分之多少的数据是存储在cache中的

而在innodb层，增加了一个全局变量buf_stat_per_index (对应类型为buf_stat_per_index_t) 来维护每个索引在内存中的leaf page个数, 其内部实现了一个lock-free的hash结构，Key值为(m_space_id) << 32 | m_index_id), 在读入page时或者内存中创建新page时， 如果对应的page是leaf page，就递增计数；当从page hash中移除时，则递减计数。

为了减少性能的影响，计数器是通过lock-free hash的结构存储的，对应的结构为ut_lock_free_hash_t。 基本的实现思路是：hash是一个定长的数组，数组元素为(key, val), 根据Key计算一个hash值再模上array size, 找到对应的槽位, 如果槽位被占用了，则向右查找一个空闲的slot。 当数组满了的时候，会创建一个新的更大的数组，在数据还没Move到这个新hash之前，所有的search都需要查询两个数组。当所有的记录到迁移到新数组，并且没有线程访问老的数组时，就可以把老的hash删除掉了。

在hash中存储的counter本身，也考虑到多核和numa架构，避免同时更新引起的cpu cache失效。在大量core的场景下这个问题可能很明显。Innodb封装计数操作到类ut_lock_free_cnt_t中，使用数组维护counter, 按照cpu no作为index更新，需要获取counter值时则累加数组中的值。

这个Lock free hash并不是个通用场景的hash结构：例如处理冲突的时候，可能占用其他key的槽位，hash不够用时，需要迁移到新的array中。实际上mysql本身实现了一个lf_hash，在扩展Hash时无需迁移数据，有空单独开篇博客讲一下。

你可以从information_schema.innodb_cached_indexes表中读取到每个索引cache的page个数。

当定义好接口，并且Innodb提供相应的统计数据后，优化器就可以利用这些信息来计算开销：

  • Cost_model_table::page_read_cost