直方图简介

直方图是一种特殊类型的列统计信息，通过将数据保存到一系列有序的桶中来描述其列的数据分布特征，优化器可以依据直方图来估算出更准确的行数。

在默认情况下，优化器会认为列的数据是分布均匀的，之后会根据这一特征来进行行数估计，但是在真实的场景中，大多数表的数据分布都是不均匀的，这种情况就需要使用直方图。

在 OceanBase 数据库优化器中，列的直方图信息存储在视图 ALL_TAB_HISTOGRAMS、DBA_TAB_HISTOGRAMS 和 USER_TAB_HISTOGRAMS 中，包含以下信息：

• 直方图的基本信息（包括 tenant_id、table_id、partition_id、column_id）

• 直方图的统计信息类型（信息级别分为 GLOBAL、PARTITION 和 SUBPARTITION）

• 直方图中每个桶累积的数据量（包含当前桶及其之前的桶的总和）

• 直方图中每个桶里面的最大的 Value 值

• 直方图中每个桶里面的最大 Value 值的频次

直方图的类型

OceanBase 数据库优化器支持三种直方图：频率直方图、Topk 直方图和混合直方图。

在频率直方图中，每个不同的列值对应于直方图的单个桶，要求指定的桶的个数不低于列的 NDV 值。

Topk 直方图是频率直方图的变体，基于 Lossy Counting 算法，通过取部分数据特征来估算整体的数据分布，要求它所记录的数据数与总数据数的比例不低于 1-(1/bucket_size)。

混合直方图主要通过采集指定的的数据量进行直方图构建，是对频率直方图和 Topk 直方图的功能补充。

频率直方图

在频率直方图中，每个不同的列值对应于直方图的单个桶。因为每个值都有自己的专用桶，所以一些桶可能有很多值，而另一些则很少。频率直方图的类比是对硬币进行分类，例如一个钱袋里面一共有 4 种不同面值（0.1 元、0.2 元、0.5 元、1 元）的 20 枚硬币，我们按照分类将所有 0.1 元的硬币放在第一个桶，所有 0.2 元的硬币放在第二个桶，所有 0.5 元的硬币放在第三个桶，所有 1 元的硬币放在第四个桶，所得到如下频率直方图，综合频率直方图的特性，要求指定的桶的个数不低于列的 NDV 值。

Topk 直方图

Topk 直方图是频率直方图的变体，当我们指定的桶个数不足以装下所有 NDV 时，就会考虑选择使用 Topk 直方图，Topk 直方图本质是忽略频次低的数据，主要考虑频次高的数据分布。例如，一个钱袋里面一共有 4 种不同面值（0.1 元、0.2 元、0.5 元、1 元）的 100 枚硬币，其中 0.1 元的硬币仅仅只有 1 枚，同时我们只有 3 个桶来装硬币，因此就可以忽略 0.1 元的硬币，只考虑剩下三种硬币的分布，得到如下 Topk 直方图。

由于 Topk 直方图是通过取部分数据特征来估算整体的数据分布，因此为了保证误差不会太大，要求 Topk 直方图记录的数据数与总数据数的比例不低于 1–(1/bucket_size)；比如上述场景中，指定桶个数为 3，一共有 100 枚硬币，Topk 直方图记录了 99 枚，那么显然 99/100 > 2/3，满足要求。目前 OceanBase 数据库优化器主要通过 Lossy Counting 算法来实现 Topk 直方图。

混合直方图

针对于一种数据量很大的大表场景，指定的直方图桶个数低于 NDV 值，同时 Topk 直方图也无法满足最低的数据占比，这个时候就需要一种更加均衡的直方图来描述数据分布的特征，由此引入了混合直方图。混合直方图主要通过采集指定的的数据量进行直方图构建，与频率直方图和 Topk 直方图的不同的是，一个桶里面可能装多个不同的 Value 值，将采集到的数据量按照桶个数分段，将每一分段内的所有数据都放到对应的一个桶中，达到用更少的桶来描述更大数据量的数据分布，其中桶内的最大的 Value 值将作为 endpoint_value，同时会多一个 endpoint_repeat_cnt 来记录 endpoint_value 的频次。

例如，同样的有 100 枚硬币：0.1 元有 10 枚、0.2 元有 10 枚、0.5 元有 15 枚、1 元有 15 枚、2 元有 25 枚、5 元有 10 枚、10 元有 15 枚，由此计算得出 Topk 直方图覆盖的数据占比是 (25+15+15+15)/100=0.7，而 Topk 覆盖数据占比的最小阈值是 1-1/N =3/4=0.75，未达到该阈值，不满足 Topk 直方图的条件，那么在指定桶个数为 4 时（桶个数低于列的 NDV 值，不满足频率直方图的条件）建立的混合直方图如下。

直方图的选择策略

OceanBase 数据库优化器在对列采集信息形成直方图时，会考虑桶的数量对优化器性能的影响（桶数量过多会对查找性能和数据存储带来负面影响），所以一般默认一个列的 NDV 的值最好小于等于直方图桶个数（bucket_size），默认值为 254。

1. 如果指定列上不同值的 NDV（Number of Distinct Values）个数小于等于 254，则使用频率直方图。

2. 如果大于 254，则优先使用 TopK 直方图。具体方法为：统计列的信息后，按照桶对应的频次从大到小排序，舍弃序号大于 254 的桶，但必须确保这 254 个桶中统计的数据数量与总数据数量的比例不低于 1 - (1/bucket_size)，默认值为 99.6%。

3. 如果不满足 2 中的条件，则使用混合直方图。通过重新定义桶，使每个桶能够描述更多的数据，同时引入新的值来详细描述桶的定义，包括桶的末端值（endpoint_value）和末端值的频次（endpoint_repeat_cnt）。