直方图简介

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

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

在 OceanBase 数据库优化器中，列的直方图信息存储在内部表 __all_histogram_stat_v2 中，它包含了以下信息：

• 直方图的基本信息（包括 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 和 p 指标选择直方图。直方图的选择策略如下图所示。

指标含义如下：

• NDV：指定一个列上不同 Value 值的个数。

• bucket_size： 指定的直方图桶个数，默认为 254。

• p：Topk 直方图期望的最低百分比阈值，计算公式为 (1-(1/bucket_size)) * 100。如果使用默认值 254，则对应的最低百分比阈值为 99.6。

有关 bucket_size 的取值，请参见 method_opt。