【GreatSQL优化器-13】直方图

天津储鑫盛钢材现货供应商  论坛元老 | 2025-2-14 14:44:17 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1014|帖子 1014|积分 3042

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
【GreatSQL优化器-13】直方图

一、直方图先容

GreatSQL的优化器负责将SQL查询转换为尽可能高效的执行计划，但由于数据环境不停变革有可能导致优化器对查询数据了解不够充足，可能无法生成最优的执行计划进而影响查询效率，因此推出了直方图(histogram)功能来办理该问题。
直方图用于统计字段值的分布情况，向优化器提供统计信息。利用直方图，可以对一张表的一列数据做分布统计，估算WHERE条件中过滤字段的选择率，从而帮助优化器更准确地估计查询过程中的行数，选择更高效的查询计划。
直方图以灵活的JSON的格式存储。ANALYZE TABLE会基于表巨细主动判断是否要进行取样操纵。
ANALYZE TABLE也会基于表中列的数据分布情况以及bucket的数量来决定是否要建立等宽直方图（singleton）照旧等高直方图（equi-height）。
下面用一个简单的例子来说明直方图是什么。
  1. greatsql> CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME);
  2. greatsql> INSERT INTO t1 VALUES (1,10,'2021-03-25 16:44:00.123456'),(2,1,'2022-03-26 16:44:00.123456'),(3,4,'2023-03-27 16:44:00.123456'),(5,5,'2024-03-25 16:44:00.123456'),(7,null,'2020-03-25 16:44:00.123456'),(8,10,'2020-10-25 16:44:00.123456'),(11,16,'2023-03-25 16:44:00.123456');
  3. greatsql> CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT);
  4. greatsql> INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15);
  5. greatsql> CREATE TABLE t3 (ccc1 INT, ccc2 varchar(100));
  6. greatsql> INSERT INTO t3 VALUES (1,'aa1'),(2,'bb1'),(3,'cc1'),(4,'dd1'),(null,'ee');
  7. greatsql> CREATE INDEX idx1 ON t1(c2);
  8. greatsql> CREATE INDEX idx2 ON t1(c2,date1);
  9. greatsql> CREATE INDEX idx2_1 ON t2(cc2);
  10. greatsql> CREATE INDEX idx3_1 ON t3(ccc1);
  12. 系统自动创建buckets：
  13. greatsql> ANALYZE TABLE t1 UPDATE HISTOGRAM ON c2,date1 WITH 3 BUCKETS;
  14. greatsql> SELECT json_pretty(histogram)result from information_schema.column_statistics where table_name = 't1';
  15. | {
  16.   "buckets": [
  17.     [
  18.       1, 最小值
  19.       5, 最大值
  20.       0.42857142857142855, 频率
  21.       3 key个数
  22.     ],
  23.     [
  24.       10,
  25.       10,
  26.       0.7142857142857143,
  27.       1
  28.     ],
  29.     [
  30.       16,
  31.       16,
  32.       0.8571428571428571,
  33.       1
  34.     ]
  35.   ],
  36.   "data-type": "int",
  37.   "null-values": 0.14285714285714285,
  38.   "collation-id": 8,
  39.   "last-updated": "2024-10-22 08:38:48.858099",
  40.   "sampling-rate": 1.0,
  41.   "histogram-type": "equi-height",
  42.   "number-of-buckets-specified": 3
  43. }                                                                                                                                     |
  44. | {
  45.   "buckets": [
  46.     [
  47.       "2020-03-25 16:44:00.000000",
  48.       "2021-03-25 16:44:00.000000",
  49.       0.42857142857142855,
  50.       3
  51.     ],
  52.     [
  53.       "2022-03-26 16:44:00.000000",
  54.       "2023-03-27 16:44:00.000000",
  55.       0.8571428571428571,
  56.       3
  57.     ],
  58.     [
  59.       "2024-03-25 16:44:00.000000",
  60.       "2024-03-25 16:44:00.000000",
  61.       1.0,
  62.       1
  63.     ]
  64.   ],
  65.   "data-type": "datetime",
  66.   "null-values": 0.0,
  67.   "collation-id": 8,
  68.   "last-updated": "2024-10-22 08:38:48.859681",
  69.   "sampling-rate": 1.0,
  70.   "histogram-type": "equi-height",
  71.   "number-of-buckets-specified": 3
  72. } |
  74. 用户手动指定buckets：
  75. greatsql> ANALYZE TABLE t2 UPDATE HISTOGRAM ON cc2 USING DATA '{"buckets": [[1, 0.25], [2, 0.5], [3, 0.625], [15, 0.75]], "data-type": "int", "null-values": 0.25, "collation-id": 8, "sampling-rate": 1.0, "histogram-type": "singleton", "number-of-buckets-specified": 4}';
  76. greatsql> select json_pretty(histogram)result from information_schema.column_statistics where table_name = 't2';
  77. | {
  78.   "buckets": [
  79.     [
  80.       1, 值
  81.       0.25 值占总数百分比
  82.     ],
  83.     [
  84.       2,
  85.       0.5
  86.     ],
  87.     [
  88.       3,
  89.       0.625
  90.     ],
  91.     [
  92.       15,
  93.       0.75
  94.     ]
  95.   ],
  96.   "data-type": "int",
  97.   "null-values": 0.25,
  98.   "collation-id": 8,
  99.   "last-updated": "2024-10-23 02:14:04.474196",
  100.   "sampling-rate": 1.0,
  101.   "histogram-type": "singleton",
  102.   "number-of-buckets-specified": 4
  103. }
复制代码
二、update_histogram代码解释

histogram.h/histogram.cc涉及直方图相关调用接口，等高直方图创建在equi_height.cc，等宽直方图创建在singleton.cc。
  1. bool update_histogram(THD *thd, Table_ref *table, const columns_set &columns,
  2.                       int num_buckets, LEX_STRING data, results_map &results) {
  3.   // UPDATE HISTOGRAM指定格式的直方图创建
  4.   if (data.str != nullptr) {
  5.     // Convert JSON to histogram
  6.     histograms::Histogram *histogram = Histogram::json_to_histogram();
  7.     // 直方图持久化
  8.     histogram->store_histogram(thd);
  9.   }
  10.   // Read data from the table into the Value_maps we have prepared.
  11.   // 根据随机抽样原则，从引擎抽样读取数据存入value_map,value_map结构为{唯一值，个数}，抽样率计算见表三
  12.   if (fill_value_maps(resolved_fields, sample_percentage, tbl, value_maps))
  13.     return true;
  14.   // 针对每个指定列创建直方图
  15.   for (const Field *field : resolved_fields) {
  16.     // 按照下面表一规则创建直方图，把value_map的key值分配到每个桶，分配原则见函数build_histogram
  17.     value_maps.at(field->field_index())->build_histogram();
  18.   }
  19. }
  21. // 等高直方图创建
  22. bool Equi_height<T>::build_histogram(const Value_map<T> &value_map,
  23.                                      size_t num_buckets) {
  24.   for (; freq_it != value_map.end(); ++freq_it) {
  25.   添加数据到桶的规则：
  26.   1、该数据不是key值的最后一条
  27.   2、剩余的key值个数>剩余空桶数量
  28.   3、添加数据进去不会导致桶大小溢出，因为不知道每个key分别有多少个对应value，这里bucket_max_values用总行数(扣除null值后)进行二分法后用贪婪算法算出来的，一旦发现桶不够用了马上转到下一次二分法重新装数据计算，二分法最多次数10次，因此算出来的桶的高度可能偏大。详细见FindBucketMaxValues函数
  29.     if (next != value_map.end() &&
  30.         distinct_values_remaining > empty_buckets_remaining &&
  31.         bucket_values + next->second <= bucket_max_values) {
  32.       continue;
  33.     }
  34.   // 计算数据个数占总数的百分比，※注意这里的总个数包含null值
  35.   double cumulative_frequency =
  36.         cumulative_values / static_cast<double>(total_values);
  37.   if (m_buckets.push_back(bucket)) return true;
  38.   }
  39. }
  41. // 等宽直方图创建
  42. bool Singleton<T>::build_histogram(const Value_map<T> &value_map,
  43.                                    size_t num_buckets) {
  44.   const ha_rows total_count =
  45.       value_map.get_num_null_values() + num_non_null_values;
  46.   for (const auto &node : value_map) {
  47.     cumulative_sum += node.second;
  48.     // 按照数据个数求占总数据的百分比，※注意这里的总个数包含null值
  49.     const double cumulative_frequency =
  50.         cumulative_sum / static_cast<double>(total_count);
  51.     m_buckets.push_back(SingletonBucket<T>(node.first, cumulative_frequency));
  52.   }                              
  53. }
复制代码
首先创建主动等高直方图
  1. greatsql> CREATE TABLE t4 (d1 INT, d2 int, d3 varchar(100));
  2. greatsql> INSERT INTO t4 VALUES (1,2,'aa1'),(2,1,'bb1'),(2,3,'cc1'),(3,3,'cc1'),(4,2,'ff1'),(4,4,'ert'),(4,2,'f5fg'),(null,2,'ee'),(5,30,'cc1'),(5,4,'fcc1'),(4,10,'cc1'),(6,4,'ccd1'),(null,1,'fee'),(1,2,'aa1'),(2,1,'bb1'),(2,3,'cc1'),(3,3,'cc1'),(4,2,'ff1'),(4,4,'ert'),(4,2,'f5fg'),(null,2,'ee'),(5,30,'cc1'),(5,4,'fcc1'),(4,10,'cc1'),(6,4,'ccd1'),(null,1,'fee'),(1,2,'aa1'),(2,1,'bb1'),(2,3,'cc1'),(3,3,'cc1'),(4,2,'ff1'),(4,4,'ert'),(4,2,'f5fg'),(null,2,'ee'),(5,30,'cc1'),(5,4,'fcc1'),(4,10,'cc1'),(6,4,'ccd1'),(null,1,'fee');
  4. 查看数据分布情况，发现d1存在数据倾斜。下面的格式即value_map的格式
  5. greatsql> SELECT d1,count(*) FROM t4 GROUP BY d1;
  6. +------+----------+
  7. | d1   | count(*) |
  8. +------+----------+
  9. |    1 |        3 |
  10. |    2 |        6 |
  11. |    3 |        3 |
  12. |    4 |       12 |
  13. | NULL |        6 |
  14. |    5 |        6 |
  15. |    6 |        3 |
  16. +------+----------+
  17. 7 rows in set (0.00 sec)
复制代码
等高直方图不同桶装的最多数据个数bucket_max_values
桶个数总行数(扣掉null值)每个桶最多数据个数233213331243395339接着创建主动等宽直方图
  1. -- 先创建等高直方图，t4表扣掉null值一共33行，这里创建出来每个桶最多装12行数据。
  2. greatsql> ANALYZE TABLE t4 UPDATE HISTOGRAM ON d1 WITH 3 BUCKETS;
  3. greatsql> SELECT json_pretty(histogram)result FROM information_schema.column_statistics WHERE table_name = 't4';
  4. | {
  5.   "buckets": [
  6.     [
  7.       1,
  8.       3,
  9.       0.3076923076923077, 计算公式9/39 ※注意这里的总个数包含null值
  10.       3
  11.     ],
  12.     [
  13.       4,
  14.       4,
  15.       0.6153846153846154,
  16.       1
  17.     ],
  18.     [
  19.       5,
  20.       6,
  21.       0.8461538461538461,
  22.       2
  23.     ]
  24.   ],
  25.   "data-type": "int",
  26.   "null-values": 0.15384615384615385,
  27.   "collation-id": 8,
  28.   "last-updated": "2024-10-24 03:15:54.463774",
  29.   "sampling-rate": 1.0,
  30.   "histogram-type": "equi-height",
  31.   "number-of-buckets-specified": 3
  32. } |
  34. -- 先创建等高直方图，t4表扣掉null值一共33行，这里创建出来每个桶最多装9行数据。
  35. greatsql> ANALYZE TABLE t4 UPDATE HISTOGRAM ON d1 WITH 5 BUCKETS;
  36. greatsql> SELECT json_pretty(histogram)result FROM information_schema.column_statistics WHERE table_name = 't4';
  37. | {
  38.   "buckets": [
  39.     [
  40.       1,
  41.       2,
  42.       0.23076923076923078,
  43.       2
  44.     ],
  45.     [
  46.       3,
  47.       3,
  48.       0.3076923076923077,
  49.       1
  50.     ],
  51.     [
  52.       4,
  53.       4,
  54.       0.6153846153846154,
  55.       1
  56.     ],
  57.     [
  58.       5,
  59.       5,
  60.       0.7692307692307693,
  61.       1
  62.     ],
  63.     [
  64.       6,
  65.       6,
  66.       0.8461538461538461,
  67.       1
  68.     ]
  69.   ],
  70.   "data-type": "int",
  71.   "null-values": 0.15384615384615385,
  72.   "collation-id": 8,
  73.   "last-updated": "2024-10-24 06:42:40.102386",
  74.   "sampling-rate": 1.0,
  75.   "histogram-type": "equi-height",
  76.   "number-of-buckets-specified": 5
  77. } |
复制代码
数值个数占比133/39269/393312/3941224/395630/396333/39下面看一个sampling-rate小于1的例子
  1. -- 先创建等高直方图，t4表扣掉null值一共33行，这里创建出来每个桶最多装12行数据。
  2. greatsql> ANALYZE TABLE t4 UPDATE HISTOGRAM ON d1 WITH 6 BUCKETS;
  3. greatsql> select json_pretty(histogram)result from information_schema.column_statistics where table_name = 't4';
  4. | {
  5.   "buckets": [
  6.     [
  7.       1,
  8.       0.07692307692307693 计算公式3/39 ※注意这里的总个数包含null值
  9.     ],
  10.     [
  11.       2,
  12.       0.23076923076923078
  13.     ],
  14.     [
  15.       3,
  16.       0.3076923076923077
  17.     ],
  18.     [
  19.       4,
  20.       0.6153846153846154
  21.     ],
  22.     [
  23.       5,
  24.       0.7692307692307693
  25.     ],
  26.     [
  27.       6,
  28.       0.8461538461538461
  29.     ]
  30.   ],
  31.   "data-type": "int",
  32.   "null-values": 0.15384615384615385,
  33.   "collation-id": 8,
  34.   "last-updated": "2024-10-24 06:53:37.256033",
  35.   "sampling-rate": 1.0,
  36.   "histogram-type": "singleton",
  37.   "number-of-buckets-specified": 6
  38. } |
复制代码
四、总结

从上面直方图创建的步骤我们认识了直方图的类型和创建方法，包括主动和手动两种，以及等宽和等高直方图的区别，学会了查看直方图的桶个数和数据，如果表是一张大表的话，想让样本尽可能多的被抽样，那么系统变量histogram_generation_max_mem_size就设置大一点，这样精确度更高，当然相对的更占硬盘资源。下一节讲直方图的应用。

Enjoy GreatSQL
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

天津储鑫盛钢材现货供应商

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表