浅析 MySQL 8.0 直方图原理

本文分享自华为云社区《【MySQL技术专栏】MySQL8.0直方图介绍》，作者：GaussDB 数据库。

背景

数据库查询优化器负责将 SQL 查询转换为尽可能高效的执行计划，但因为数据环境不断变化导致优化器对查询数据了解的不够充足，可能无法生成最优的执行计划进而影响查询效率，因此 MySQL8.0 推出了直方图(histogram)功能来解决该问题。

直方图用于统计字段值的分布情况，向优化器提供统计信息。利用直方图，可以对一张表的一列数据做分布统计，估算 where 条件中过滤字段的选择率，从而帮助优化器更准确地估计查询过程中的行数，选择更高效的查询计划。

本文将对直方图概念进行介绍，借助举例描述直方图的使用方式，对创建/删除直方图的原理进行浅析，并通过例子说明其应用场景。

MySQL8.0 直方图介绍

数据库中，查询优化器所生成执行计划的好坏关乎执行耗时的多少，优化器若是不清楚表中数据的分布情况，可能会导致无法生成最优的执行计划，造成执行时浪费时间。

假设一条 SQL 语句要查询相等间隔的两个不同时间段内出行的人数，若不知道每个时间段内的人数，优化器会假设人数在两个不同时间段内是均匀分布的。如果两个时间段内人数相差较大，这样优化器估算的统计数据就出现严重偏差，从而可能选择错误的执行计划。那么，如何使优化器比较清楚地知道数据统计情况进而生成好的执行计划呢？

一种解决方法就是，在列上建立直方图，从而近似地获取一列上的数据分布情况。利用好直方图，将会带来很多方面收益：

(1)查询优化：提供关于数据分布的统计信息，帮助优化查询计划，选择合适的索引和优化查询语句，从而提高查询性能；

(2)索引设计：通过分析数据的分布情况，帮助确定哪些列适合创建索引，以提高查询效率；

(3)数据分析：提供数据的分布情况，帮助用户了解数据的特征和趋势。

直方图分为两类：等宽直方图(singleton)和等高直方图(equi-height)。等宽直方图是每个桶保存一个值以及这个值累积频率：

SCHEMA_NAME: xxx//库名

TABLE_NAME: xxx//表名

COLUMN_NAME: xxx//列名

HISTOGRAM: {

"buckets":[

[

xxx, //桶中数值

xxx //取值频率

],

......

],

"data-type":"xxx", //数据类型

"null-values":xxx, //是否有 NULL 值

"collation-id":xxx,

"last-updated":"xxxx-xx-xx xx:xx:xx.xxxxxx", //更新时间

"sampling-rate":xxx, //采样率，1 表示采集所有数据

"histogram-type":"singleton", //桶类型，等宽

"number-of-buckets-specified":xxx //桶数量

}

等高直方图每个桶需要保存不同值的个数，上下限以及累积频率等：

SCHEMA_NAME: xxx

TABLE_NAME: xxx

COLUMN_NAME: xxx

HISTOGRAM: {

"buckets":[

[

xxx, //最小值

xxx, //最大值

xxx, //桶值出现的频率

xxx //桶值出现的次数

],

......

],

"data-type":"xxx",

"null-values":xxx,

"collation-id":xxx,

"last-updated":"xxxx-xx-xx xx:xx:xx.xxxxxx",

"sampling-rate":xxx,

"histogram-type":"equi-height", //桶类型，等高

"number-of-buckets-specified":xxx

}

MySQL8.0 直方图使用方式

创建和删除直方图时涉及 analyze 语句，常用语法格式为：

创建直方图：

ANALYZE TABLE tbl_name UPDATE HISTOGRAM ON col_name [, col_name] ... [WITH N BUCKETS]

删除直方图：

ANALYZE TABLE tbl_name DROP HISTOGRAM ON col_name [, col_name] ...

具体示例：

mysql> create table t1(c1 int,c2 int,c3 int,c4 int,c5 int,c6 int,c7 int,c8 int,c9 int,c10 int,c11 int,c12 int,c13 datetime,c14 int,c15 int,c16 int,primary key(c1));

Query OK, 0 rows affected (0.01 sec)

mysql> insert into t1 values(1,2,3,4,5,6,7,8,9,10,11,12,'0000-01-01',14,15,16),(2,2,3,4,5,6,7,8,9,10,11,12,'0500-01-01',14,15,16),(3,2,3,4,5,6,7,8,9,10,11,12,'1000-01-01',14,15,16),(4,2,3,4,5,6,7,8,9,10,11,12,'1500-01-01',14,15,16),(5,2,3,4,5,6,7,8,9,10,11,12,'1500-01-01',14,15,16);

Query OK, 5 rows affected (0.00 sec)

Records: 5 Duplicates: 0 Warnings: 0

创建直方图：

mysql> analyze table t1 update histogram on c13;

+---------+-----------+----------+------------------------------------------------+

| Table | Op | Msg_type | Msg_text |

+---------+-----------+----------+------------------------------------------------+

| test.t1 | histogram | status | Histogram statistics created for column 'c13'. |

+---------+-----------+----------+------------------------------------------------+

1 row in set (0.01 sec)

查看直方图信息：

mysql> select json_pretty(histogram)result from information_schema.column_statistics where table_name = 't1' and column_name = 'c13'\G

*************************** 1. row ***************************

result: {

"buckets": [

[

"0000-01-01 00:00:00.000000", //统计的列值

0.2 //统计的相对频率，下同

],

[

"0500-01-01 00:00:00.000000",

0.4

],

[

"1000-01-01 00:00:00.000000",

0.6

],

[

"1500-01-01 00:00:00.000000",

1.0

]

],

"data-type": "datetime", //统计的数据类型

"null-values": 0.0, //NULL 值的比例

"collation-id": 8, //直方图数据的排序规则 ID

"last-updated": "2023-09-30 16:05:28.533732", //最近更新直方图的时间

"sampling-rate": 1.0, //直方图构建采样率

"histogram-type": "singleton", //直方图类型，等宽

"number-of-buckets-specified": 100 //桶数量

}

1 row in set (0.00 sec)

删除直方图：

mysql> analyze table t1 drop histogram on c13;

+---------+-----------+----------+------------------------------------------------+

| Table | Op | Msg_type | Msg_text |

+---------+-----------+----------+------------------------------------------------+

| test.t1 | histogram | status | Histogram statistics removed for column 'c13'. |

+---------+-----------+----------+------------------------------------------------+

1 row in set (0.00 sec)

MySQL8.0 直方图原理浅析

直方图原理整体框架可概括为下图所示：

直方图代码主要包含在 sql/histograms 路径下，带有 equi_height 前缀的相关文件涉及等高直方图，带有 singleton 前缀的相关文件涉及等宽直方图，带有 value_map 前缀的相关文件涉及保存统计值结构，histogram.h/histogram.cc 涉及直方图相关调用接口。

Sql_cmd_analyze_table::handle_histogram_command 为对直方图操作的整体处理入口，目前只支持在一张表上进行直方图相关操作。创建直方图的主要调用堆栈如下所示，update_histogram 为创建直方图的入口。

mysql_execute_command

->Sql_cmd_analyze_table::execute

->Sql_cmd_analyze_table::handle_histogram_command

->Sql_cmd_analyze_table::update_histogram

->histograms::update_histogram

->prepare_value_maps

->fill_value_maps

->build_histogram

->store_histogram

->dd::cache::Dictionary_client::update

->dd::cache::Storage_adapter::store

->dd::Column_statistics_impl::store_attributes

->histograms::Singleton<xxx>::histogram_to_json

对于创建流程展开描述，prepare_value_maps 中主要根据直方图列类型创建对应的 value_map 做准备，之后利用 histogram_generation_max_mem_size 参数值(限制生成直方图时所允许使用的最大内存大小)和单行数据大小计算后控制统计采样率，fill_value_maps 将反复读取数据填充到对应类型的 value_map 中，key 为列实际值，value 为其出现的次数。调用 build_histogram 以完成对直方图的构建，如果桶个数(num_buckets)比不同值个数(value_map.size())要大，则自动创建一个等宽直方图，否则创建一个等高直方图。两种直方图的创建逻辑分别在 Singleton<T>:: build_histogram 和 Equi_height<T>:: build_histogram 中。

构建直方图完成后调用 store_histogram，将结果以 JSON 的形式存储在系统表中，通过 INFORMATION_SCHEMA.COLUMN_STATISTICS 对用户呈现，histogram_to_json 会将直方图结果转换为 Json_object 格式，例如 last-updated 使用 Json_datetime 格式保存、histogram-type 使用 Json_string 格式保存、sampling rate 使用 Json_double 格式保存等，再依次调用 json_object->add_clone 将各 json 类型字段保存。

删除直方图的主要堆栈如下所示。drop_histograms 逻辑中在删除直方图前会先尝试获取以检查对应直方图是否真的存在，不存在的话就提前终止逻辑，存在则删除。

mysql_execute_command

->Sql_cmd_analyze_table::execute

->Sql_cmd_analyze_table::handle_histogram_command

->Sql_cmd_analyze_table::update_histogram

->histograms::update_histogram

MySQL8.0 直方图优化场景

优化方面，如本文在前所描述的直方图作用，利用直方图信息估算 where 条件中各谓词的选择率，帮助选择最优的执行计划。例如，表存在如下所示数据倾斜场景。

mysql> select sys_id,order_status,count(*) from my_table_1 group by sys_id,order_status order by 1,2,3;

+--------+--------------+----------+

| sys_id | order_status | count(*) |

+--------+--------------+----------+

| 3 | 1 | 1 |

| 3 | 2 | 200766 |

| 3 | 3 | 3353 |

| 3 | 4 | 1325 |

| 5 | 1 | 13 |

| 5 | 2 | 2478373 |

| 5 | 3 | 43243 |

| 5 | 4 | 13529 |

| 6 | 2 | 171388 |

| 6 | 3 | 254 |

| 6 | 4 | 716 |

+--------+--------------+----------+

执行如下 SQL 语句时，因为存在数据倾斜而优化器未能准确估计导致执行计划选择错误，执行耗时约为 1.35s。

mysql> explain analyze select t1.id, t1.order_number, t1.create_time, t1.order_status from my_table_1 t1 left join my_table_2 t2 on t1.id = t2.order_id WHERE t1.sys_id = 5 and t1.order_status in (1) and t1.create_time >= '2022-09-10 00:00:00' and t1.create_time <= '2022-09-16 23:59:59' order by t1.id desc LIMIT 20\G

*************************** 1. row ***************************

EXPLAIN: -> Limit: 20 row(s) (cost=4163.10 rows=20) (actual time=1350.825..1350.825 rows=0 loops=1)

-> Nested loop left join (cost=4163.10 rows=49) (actual time=1350.825..1350.825 rows=0 loops=1)

-> Filter: ((t1.order_status = 1) and (t1.sys_id = 5) and (t1.create_time >= TIMESTAMP'2022-09-10 00:00:00') and (t1.create_time <= TIMESTAMP'2022-09-16 23:59:59')) (cost=215.79 rows=49) (actual time=1350.823..1350.823 rows=0 loops=1)

-> Index scan on t1 using PRIMARY (reverse) (cost=215.79 rows=8828) (actual time=0.088..1209.201 rows=2910194 loops=1)

-> Index lookup on t2 using idx_order_id (order_id=t1.id) (cost=0.63 rows=1) (never executed)

通过执行 ANALYZE table my_table_1 UPDATE HISTOGRAM ON order_status, sys_id, create_time 语句创建直方图后，再次执行上述 SQL 语句时，执行计划中的索引发生了变化，执行耗时为 0.11s。因此可以看出，优化器利用更准确的数据分布信息选择了更优的执行计划。

mysql> explain analyze select t1.id, t1.order_number, t1.create_time, t1.order_status from my_table_1 t1 left join my_table_2 t2 on t1.id = t2.order_id WHERE t1.sys_id = 5 and t1.order_status in (1) and t1.create_time >= '2022-09-10 00:00:00' and t1.create_time <= '2022-09-16 23:59:59' order by t1.id desc LIMIT 20\G

*************************** 1. row ***************************

EXPLAIN: -> Limit: 20 row(s) (cost=38385.46 rows=20) (actual time=114.217..114.217 rows=0 loops=1)

-> Nested loop left join (cost=38385.46 rows=62764) (actual time=114.216..114.216 rows=0 loops=1)

-> Sort: t1.id DESC, limit input to 20 row(s) per chunk (cost=28200.86 rows=62668) (actual time=114.215..114.215 rows=0 loops=1)

-> Filter: (t1.order_status = 1) (cost=28200.86 rows=62668) (actual time=114.207..114.207 rows=0 loops=1)

-> Index range scan on t1 using idx_sys_id_create_time, with index condition: ((t1.sys_id = 5) and (t1.create_time >= TIMESTAMP'2022-09-10 00:00:00') and (t1.create_time <= TIMESTAMP'2022-09-16 23:59:59')) (cost=28200.86 rows=62668) (actual time=0.326..112.912 rows=31142 loops=1)

-> Index lookup on t2 using idx_order_id (order_id=t1.id) (cost=0.62 rows=1) (never executed)

另外，当 where 条件中变量值不同时，优化器也根据数据分布情况选择了准确的执行计划，使得执行效率提高。

mysql> explain format=tree select t1.id, t1.order_number, t1.create_time, t1.order_status from my_table_1 t1 left join my_table_2 t2 on t1.id = t2.order_id WHERE t1.sys_id = 5 and t1.order_status in (2) and t1.create_time >= '2020-10-01 00:00:00' and t1.create_time <= '2020-10-09 23:59:59' order by t1.id desc LIMIT 20\G

*************************** 1. row ***************************

EXPLAIN: -> Limit: 20 row(s) (cost=13541.27 rows=20)

-> Nested loop left join (cost=13541.27 rows=44)

-> Filter: ((t1.order_status = 2) and (t1.sys_id = 5) and (t1.create_time >= TIMESTAMP'2020-10-01 00:00:00') and (t1.create_time <= TIMESTAMP'2020-10-09 23:59:59')) (cost=15.79 rows=44)

-> Index scan on t1 using PRIMARY (reverse) (cost=15.79 rows=338)

-> Index lookup on t2 using idx_order_id (order_id=t1.id) (cost=0.25 rows=1)

1 row in set (0.00 sec)

mysql> explain format=tree select t1.id, t1.order_number, t1.create_time, t1.order_status from my_table_1 t1 left join my_table_2 t2 on t1.id = t2.order_id WHERE t1.sys_id = 5 and t1.order_status in (4) and t1.create_time >= '2020-10-01 00:00:00' and t1.create_time <= '2020-10-09 23:59:59' order by t1.id desc LIMIT 20\G

*************************** 1. row ***************************

EXPLAIN: -> Limit: 20 row(s) (cost=30559.31 rows=20)

-> Nested loop left join (cost=30559.31 rows=55852)

-> Sort: t1.id DESC, limit input to 20 row(s) per chunk (cost=24966.26 rows=55480)

-> Filter: (t1.order_status = 4) (cost=24966.26 rows=55480)

-> Index range scan on t1 using idx_sys_id_create_time, with index condition: ((t1.sys_id = 5) and (t1.create_time >= TIMESTAMP'2020-10-01 00:00:00') and (t1.create_time <= TIMESTAMP'2020-10-09 23:59:59')) (cost=24966.26 rows=55480)

-> Index lookup on t2 using idx_order_id (order_id=t1.id) (cost=0.25 rows=1)

1 row in set (0.00 sec)

所以，通过所提供的统计信息，帮助优化查询计划进而提高查询性能是如前所述应用直方图的一个收益点。

点击关注，第一时间了解华为云新鲜技术~