【GreatSQL优化器-14】直方图应用

【GreatSQL优化器-14】直方图应用

一、直方图介绍

GreatSQL的优化器负责将SQL查询转换为尽可能高效的执行筹划，但由于数据情况不停变化有可能导致优化器对查询数据了解不够充足，可能无法天生最优的执行筹划进而影响查询服从，因此推出了直方图(histogram)功能来解决该问题。
直方图用于统计字段值的分布情况，向优化器提供统计信息。利用直方图，可以对一张表的一列数据做分布统计，估算where条件中过滤字段的选择率，从而帮助优化器更准确地估计查询过程中的行数，选择更高效的查询筹划。
下面用一个简朴的例子来说明直方图怎么应用在优化器。

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');
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 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
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. }
45. greatsql> EXPLAIN SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t1.c2<5;
46. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
47. | id | select_type | table | partitions | type | possible_keys     | key  | key_len | ref  | rows | filtered | Extra                                          |
48. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
49. |  1 | SIMPLE      | t3    | NULL       | ALL  | idx3_1            | NULL | NULL    | NULL |    5 |   100.00 | NULL                                           |
50. |  1 | SIMPLE      | t1    | NULL       | ALL  | PRIMARY,idx1,idx2 | NULL | NULL    | NULL |    7 |    43.67 | Range checked for each record (index map: 0x7) |
51. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
53.                 "plan_prefix": [
54.                 ],
55.                 "table": "`t1`",
56.                 "best_access_path": {
57.                   "considered_access_paths": [
58.                     {
59.                       "rows_to_scan": 7,
60.                       "filtering_effect": [
61.                         {
62.                           "condition": "(`t1`.`c2` < 5)", 对t1.c2的过滤系数估计用到了直方图
63.                           "histogram_selectivity": 0.342857 这里过滤系数算出来为0.342857，即直方图第一个桶小于5的数据占的百分比
64.                         }
65.                       ],
66.                       "final_filtering_effect": 1,
67.                       "access_type": "scan",
68.                       "resulting_rows": 7,
69.                       "cost": 0.95,
70.                       "chosen": true
71.                     }
72.                   ]
73.                 },

复制代码

表一：等高直方图数据分布频率盘算方式
操作op符合条件区间在第一个桶符合条件区间不在第一个桶盘算公式get_equal_to_selectivitybucket_frequency = 当前找到的频率bucket_frequency = 当前频率-上一个桶频率bucket_frequency / 不同值个数get_less_than_selectivityprevious_bucket_cumulative_frequency = 0.0 found_bucket_frequency =当前找到的频率revious_bucket_cumulative_frequency =上一个桶频率 found_bucket_frequency=当前频率-上一个桶频率value值在区间左边： previous_bucket_cumulative_frequency value值在区间中间： previous_bucket_cumulative_frequency +(found_bucket_frequency * get_distance_from_lower(value))get_greater_than_selectivityfound_bucket_frequency=当前找到的频率found_bucket_frequency=当前频率-上一个桶频率value值在区间左边： found_bucket_frequency+下一个桶频率 value值在区间中间： get_distance_from_upper() * found_bucket_frequency+下一个桶频率表二：等宽直方图数据分布频率盘算方式
操作op符合条件区间在第一个桶符合条件区间不在第一个桶get_equal_to_selectivity当前频率当前频率-上一个桶频率get_less_than_selectivity0.0上一个桶频率get_greater_than_selectivityget_non_null_values_fraction()get_non_null_values_fraction() - 上一个桶频率表三：等高直方图get_distance_from_upper盘算公式
操作op盘算公式说明longlong范例(upper_inclusive - value) / (upper_inclusive - get_lower_inclusive() + 1.0)upper_inclusive指的是区间最大值ulonglong范例(upper_inclusive - value) / (upper_inclusive - get_lower_inclusive() + 1.0)upper_inclusive指的是区间最大值其他范例1.0 - get_distance_from_lower(value)get_distance_from_lower盘算见表四表四：等高直方图get_distance_from_lower盘算公式
操作op盘算公式说明double范例(value - get_lower_inclusive()) / (get_upper_inclusive() - get_lower_inclusive())lower_inclusive指的是区间最小值其他范例(value - lower_inclusive) / (get_upper_inclusive() - lower_inclusive + 1.0)lower_inclusive指的是区间最小值三、实际例子说明

接下来看几个例子来说明上面的代码。
首先创建等高直方图，看看效果。
[code]greatsql> ANALYZE TABLE t1 UPDATE HISTOGRAM ON c2 WITH 3 BUCKETS;greatsql> EXPLAIN SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t1.c2 ANALYZE TABLE t1 UPDATE HISTOGRAM ON c2 WITH 5 BUCKETS;greatsql> select json_pretty(histogram)result from information_schema.column_statistics where table_name = 't1';| {  "buckets": [    [      1,      0.14285714285714285    ],    [      4,      0.2857142857142857    ],    [      5,      0.42857142857142855    ],    [      10,      0.7142857142857143    ],    [      16,      0.8571428571428571    ]  ],  "data-type": "int",  "null-values": 0.14285714285714285,  "collation-id": 8,  "last-updated": "2024-10-25 02:18:36.107382",  "sampling-rate": 1.0,  "histogram-type": "singleton",  "number-of-buckets-specified": 5} greatsql> EXPLAIN SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t1.c2CREATE TABLE t3 (ccc1 INT, ccc2 int,ccc3 datetime(6));greatsql>INSERT INTO t3 VALUES (1,2,'2021-03-25 16:44:00.123456'),(2,10,'2021-03-25 16:44:00.123456'),(3,4,'2022-03-25 16:44:00.123456'),(4,6,'2023-03-25 16:44:00.123456'),(null,7,'2024-03-25 16:44:00.123456'),(4,3,'2024-04-25 16:44:00.123456'),(null,8,'2025-03-25 16:44:00.123456'),(3,4,'2022-06-25 16:44:00.123456'),(5,4,'2021-11-25 16:44:00.123456');greatsql>CREATE TABLE t4 (d1 INT, d2 int, d3 varchar(100));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');greatsql>CREATE INDEX idx3_2 ON t3(ccc2);greatsql>CREATE INDEX idx3_3 ON t3(ccc3);greatsql>CREATE INDEX idx4_2 ON t4(d2);首先看一下没有建立直方图之前的效果，这里t4用了全表扫描。greatsql>  EXPLAIN SELECT * FROM t4 join t3 ON t4.d1=t3.ccc1 and t4.d2=t3.ccc2 where t4.d1 ANALYZE TABLE t4 UPDATE HISTOGRAM ON d1 WITH 5 BUCKETS;-- 可以看到效果已经变为更优的t3作为驱动表了，这里看出直方图对于估计效果更为精确。greatsql>  EXPLAIN SELECT * FROM t4 join t3 ON t4.d1=t3.ccc1 and t4.d2=t3.ccc2 where t4.d1