小蚂蚁说：直方图是一种按数据出现的频率来进行分类存储的方法，在数据库中直方图用来描述表中列数据的分布情况。蚂蚁金服的技术专家溪峰将在本文中分享直方图在OceanBase中的应用场景，以及直方图的收集方法，最后还会跟大家共同探讨直方图所存在的局限性。
图片

本文作者：溪峰

蚂蚁金服技术专家
新加坡国立大学博士
主要研究方向是分布式查询和优化

直方图的基本概念

优化器统计信息是描述数据库中表和列的元数据信息的集合，它主要用来估计谓词的选择率和中间查询结果的大小。优化器统计信息主要包括行级别的统计信息和列级别的统计信息：

行级别的统计信息

包括行的总数、行的平均长度、表在磁盘中占用了多少page等。

列级别的统计信息

包括列的最大值、最小值、列中空值个数、列中非空值个数、不同值个数（Number of Distinct Value， 或NDV）和直方图等。

直方图（Histogram）是一种常见的列级别的统计信息，那在优化器中直方图又是如何使用的呢？

直方图的应用场景

首先，让我们考虑如下的例子，假设我们有如下两张表：

OceanBase (root@test)> create table t1(a int primary key, b int);
Query OK, 0 rows affected (1.00 sec)
OceanBase (root@test)> create table t2(a int primary key, b int, c int);
Query OK, 0 rows affected (1.00 sec)
（代码可左右滑动观看）

其中t1有1000行数据，t2中有2550行数据，t2中b列值(NDV=8)的分布如下：

图片对于查询

explain select * from t1, t2 where t1.a = t2.c and t2.b = 1
（代码可左右滑动观看）

因为优化器没有为 t2 中的b列维护直方图信息，优化器会假设所有数据在该列的值上均匀分布， 估计 t2.b =1 的选择率的公式是：

选择率 = 1/NDV （公式一）
可以看到，优化器认为满足条件b=1的行数为319行（2550/8）, 进而选择了Merge Join的计划。

—优化器错误的估计了满足b=1的行数，错误的选择了Merge Join计划
OceanBase (root@test)> explain select * from t1, t2 where t1.a = t2.c and t2.b = 1;
| =====================================
|ID|OPERATOR |NAME|EST. ROWS|COST|

|0 |MERGE JOIN | |0 |1895|
|1 | TABLE SCAN |t1 |1000 |218 |
|2 | SORT | |319 |1495|
|3 | TABLE SCAN|t2 |319 |984 |

（代码可左右滑动观看）

实际上，满足b=1的行数只有10行，更好的计划应该是使用Nested Loop Join的计划。

公式一并没有考虑不同参数值对选择率的影响，这是导致计划出错的本质原因。换句话说，要想生成正确的执行计划，优化器就必须对b这一列的数据特征有更准确的刻画——直方图就是为了解决这类问题而存在的。

直方图（Histogram）是列级别统计信息的一种，它主要用来描述数据库中列值的分布情况，适用于数据分布不均匀的场景。有了直方图，数据库可以针对不同的参数值准确地计算出选择率，保证计划的正确性。

直方图有很多种不同的类型，OceanBase中实现了两种直方图，分别为频率直方图和等高直方图：

频率直方图

频率直方图为列中的每个不同值维护一个行数信息，这种直方图适用于NDV比较小的场景。可以想象，如果有一张表格记录了一家公司的全部员工信息（每一个人一行信息），对于“籍贯”这一栏，不同值的个数很小（全国约有40个省、直辖市和行政区)，我们可以为该列建立一个频率直方图，优化器通过该直方图可以知道该公司每个省或者直辖市的员工有多少人。

等高直方图

等高直方图收集的是一个数值分布的信息，适用于NDV比较大的场景。一般建立的过程是将全部的记录根据该列进行排序，然后把排好序的记录分成N个桶，其中每个桶内行数大约为M/N(M是总行数)。继续考虑上面的员工信息表，如果表中有一列是“年纳税总额”，我们可以对该列收集等高直方图，从而很容易准确的估计出该公司“年纳税总额超过10万”的人数。

继续考虑上述的例子, 我们首先使用Analyze语句对t2中b列收集直方图，指定的直方图的桶数目为20，此时优化器会为该列收集频率直方图（选择频率直方图的理由我们稍后分析）。

—在b列上收集直方图，指定桶的数目为20
OceanBase (root@test)> analyze table t2 update histogram on b with 20 buckets;
Query OK, 0 rows affected (0.37 sec)
—表比较小，NDV < 指定的桶的个数，所以采用了全表扫描的方式收集了频率直方图, 桶的个数是8
OceanBase (root@test)> select table_id, column_id, sample_size, density, bucket_cnt, histogram_type from oceanbase.__all_column_stat;
±--------------±----------±------------±---------±-----------±---------------+
| table_id | column_id | sample_size | density | bucket_cnt | histogram_type |
±--------------±----------±------------±---------±-----------±---------------+
| 1099511677778 | 17 | 100 | 0.000196 | 8 | 1 |
±--------------±----------±------------±---------±-----------±---------------+
—频率直方图的桶的信息
OceanBase (root@test)> select tenant_id, table_id, partition_id, column_id, endpoint_num, endpoint_value from oceanbase.__all_histogram_stat;
±----------±--------------±-------------±----------±-------------±---------------+
| tenant_id | table_id | partition_id | column_id | endpoint_num | endpoint_value |
±----------±--------------±-------------±----------±-------------±---------------+
| 1 | 1099511677778 | 0 | 17 | 10 | 1 |
| 1 | 1099511677778 | 0 | 17 | 30 | 2 |
| 1 | 1099511677778 | 0 | 17 | 70 | 3 |
| 1 | 1099511677778 | 0 | 17 | 150 | 4 |
| 1 | 1099511677778 | 0 | 17 | 310 | 5 |
| 1 | 1099511677778 | 0 | 17 | 630 | 6 |
| 1 | 1099511677778 | 0 | 17 | 1270 | 7 |
| 1 | 1099511677778 | 0 | 17 | 2550 | 8 |
±----------±--------------±-------------±----------±-------------±---------------+
（代码可左右滑动观看）

可以看到直方图记录了满足b=1的行数为10行（endpoint_value 等于1时 endpoint_num 为10)，这时，我们再看看一下优化器是否能够利用直方图提供的信息生成正确的执行计划：

— 有了直方图，优化器估计b=1的行数为10行
OceanBase (root@test)> explain select * from t2 where b = 1;
|===================================
|ID|OPERATOR |NAME|EST. ROWS|COST|

|0 |TABLE SCAN|test|10 |784 |

（代码可左右滑动观看）

针对b=1的条件，优化器给出了正确的行数估计（10行）。那么对于其他的值呢？

—有了直方图，优化器估计b=8的行数为1280
OceanBase (root@test)> explain select * from t2 where b = 8;
| ===================================
|ID|OPERATOR |NAME|EST. ROWS|COST|

|0 |TABLE SCAN|test|1280 |1500 |

（代码可左右滑动观看）

同样，优化器正确的估计出了满足b=8的行数为1280（2550减去1270）行。在建立了直方图后，我们再次查看优化器为之前的SQL生成的执行计划：

OceanBase (root@test)> explain select * from t1, t2 where t1.a = t2.c and t2.b = 1;
| =========================================
|ID|OPERATOR |NAME|EST. ROWS|COST|

|0 |NESTED-LOOP JOIN| |0 |1882|
|1 | TABLE SCAN |t2 |10 |1520|
|2 | TABLE GET |t1 |1 |36 |

（代码可左右滑动观看）

由于优化器准确的估计到t2.b=1返回的行数比较少（10行），因此选择了overhead更小的Nested-Loop Join。

直方图的收集

细心的读者可能会发现在上面收集直方图的过程中，我们只是指定了直方图的桶的个数，那么优化器是如何选择直方图类型的呢？

答案是优化器会根据相关列的NDV值以及用户指定的直方图的桶个数（默认是254个）来选择直方图的类型——如果直方图桶的个数不小于NDV，那么OceanBase会选择频率直方图；否则OceanBase会选择等高直方图。

另外一个容易想到的问题是直方图的收集代价问题。很显然，直方图的信息含量大，可以帮助优化器生成正确的执行计划，但由于信息量大，直方图的收集过程很耗时，而且桶数越多，信息越准确，相对应的收集代价也越高，对所有表进行全表扫描的收集方式显然会占用大量的系统资源。数据库如何平衡直方图收集代价与准确率之间的矛盾呢？

OceanBase采用的是自适应的方式来收集直方图信息。一般来说：

当表比较小的时候，OceanBase使用全表扫描的方式来收集直方图。

当表比较大的时候，OceanBase使用采样的方式来收集直方图，在保证不占用过多的系统资源的前提下会计算出一个合理的采样比例来确保直方图的准确性。

刚才我们介绍了直方图的一种典型的使用场景，实际应用中，围绕直方图还有很多有趣的问题需要考虑。例如，我们以前介绍过OceanBase中有一个计划缓存模块，会缓存优化器生成的执行计划。

假如计划生成的过程中使用了直方图信息，在计划匹配时，系统该如何处理不同用户参数对计划的影响呢？

再比如，我们提到了针对大表直方图的收集，OceanBase使用了采样的方式，那么还有没有其他手段可以进一步降低直方图的收集代价呢？限于篇幅，我们留待以后再跟大家讨论。

直方图的局限性

抛开一些具体的实现问题，直方图是不是解决选择率问题的万能钥匙呢？答案是否定的——一个典型的场景是对Join选择率的估计。

当优化器需要估计两表关联后的结果行数时，一个直观的方案是使用直方图分别估计两表的选择率，进而估计关联后的总行数。这个方案假设了数据之间是没有数据相关性（correlation）的，而相关性广泛存在于实际系统中。因此，很多时候使用独立直方图估计join选择率的结果并不理想。

那么实际系统是如何解决join选择率的问题的呢？这个问题我们有机会再跟大家详聊。