一、简介
数据库中的“核算信息”是一个描绘数据库中表和列信息的数据集合。优化器价值模型（Optimizer Cost Model）依赖于查询中涉及到的表、列、谓词等方针的核算信息来选取方案，优化器能够利用核算信息来优化方案的挑选，所以核算信息是价值模型中选取最优执行方案的要害。
核算信息包含表核算信息（Table Level Statistics）和列核算信息（Column Level Statistics）两种类型。各家数据库不必定会搜集全部下列所列的核算信息，但会依据各家的实践状况搜集进行搜集。
1. 表级核算信息
-
表的基本信息
-
表的核算信息类型（信息级别分为GLOBAL、PARTITION和SUBPARTITION）
-
表的行数
-
表所占用的宏块数
-
表所占用的微块数
-
表的均匀行长
-
表的搜集核算信息时刻
-
表的核算信息是否锁定
2. 列级核算信息
-
列的基本信息（包含tenant_id、table_id、partition_id、column_id）
-
列的核算信息类型（信息级别分为GLOBAL、PARTITION和SUBPARTITION）
-
列中不同的值的数量NDV（Number of Distinct Values）
-
列中NULL值的数量
-
列的最大值和最小值
-
列的采样数据量巨细
-
列的直方图的稠密度
-
列的直方图桶个数
-
直方图类型（频率直方图/等高直方图/TopK 直方图/混合直方图）
在普通的核算信息中，CBO会默许方针列数据在其最小与最大值间是均匀散布的，并以此为依据预估条件挑选率及成果集 cardinality，然后挑选执行方案。但在实践中，明显有些数据不是均匀散布的，会呈现所谓的“数据歪斜”，此刻发生的执行方案很可能就不是最佳的，甚至会发生较差的执行方案。
直方图的引进就是用来处理数据歪斜的问题。直方图是一种特别的列核算信息，它详细描绘了列的数据散布状况。直方图搜集信息后，CBO 不会再以为列上是均匀散布的，能够依据实践状况预估条件挑选率及成果集 cardinality，挑选正确的执行方案。
二、常见的核算信息直方图模型
1. 频率直方图
列中有多少 distinct 值，数据字典中就会存储多少条记载。endpoint value 记载这些 distinct 值，endpoint number 则记载到此 distinct 值停止共有多少条记载。此刻 endpoint number 是一个累加值，能够用一条记载的 endpoint number 减去前一条记载的 endpoint number 得到这条记载对应的 endpoint value 值的记载数。频率直方图一般适用于 distinct 值比较少的表，直方图桶的个数 >= NDV （Number of Distinct Value），即直方图的桶数大于等于列上的不同值的数量的场景。
2. 等高直方图
关于这类直方图，Oracle 首要依据方针列对方针表的一切记载从小到大排序，然后用总记载数除以需求运用的 Bucket 数，来决议每个 Bucket 中需求描绘的已排好序的记载数。此刻 endpoint number 记载的是 Bucket 号，Bucket 号从 0 开始一直到 N。0 号 Bucket 对应的 endpoint value 记载方针列最小值，其他 Bucket 对应的 endpoint value 则记载到此 Bucket 停止方针列的最大值。
为节约空间，关于相邻的仅 endpoint number 不同，而 endpoint value 相同的记载，Oracle 会在数据字典中兼并存储。假设 endpoint number=2 和 3 的 Bucket 对应 endpoint value 都为 P，数据字典中只会记载 endpoint number=3，endpoint value=P。因而，Height Balanced 类型直方图数据字典中的 endpoint number 可能是不接连的。
这种兼并跋文载在数据字典的 endpoint value，Oracle 称为 popular value。明显 popular value 记载的 endpoint number 值与上一条记载的 endpoint number 值相差越大，popular value 在方针列中所占份额越大，对应的 cardinality 也就越大，这应该也是将其称为 popular value 的原因。
3. Top-k 直方图
频率直方图的一个变种，针对 k 个直方图覆盖数据占比超越必定阈值的状况。很少呈现的 distinct 值在直方图里会被疏忽掉。
4. 混合直方图
混合直方图结合了根据高度的直方图和频率直方图的特征，但与频率直方图和 Top-k 直方图的不同的是，一个桶里面可能装多个不同的 value 值，将搜集到的数据量按照桶个数分段，将每一分段内的一切数据都放到对应的一个桶中，到达用更少的桶来描绘更大数据量的数据散布，其中桶内的最大的 value 值将作为 endpoint_value，同时会多一个 endpoint_repeat_cnt 来记载 endpoint_value 的频次。该办法使优化器能够在某些状况下获得更好的挑选性估量。
单纯的等高直方图现在在数据库内运用的很少，许多优化方案都是在等高直方图的基础上加入了对空泛（非接连值超越必定阈值的区间视为空泛），高频值以及第二高频值表示，并确保每一个值只呈现在一个区间内的近似等高直方图。
关于频率直方图、Top-k 直方图和混合直方图在不同场景下的运用逻辑如下：
直方图信息列上数据散布呈现歪斜的状况下，对单表的成果集巨细预测供给了相对准确的成果，可是在做相关查询时却不能供给相关成果集巨细的准确性判别。
在相关查询的状况下又呈现了别的一种判别成果集巨细的办法 Count-Min Sketch。它是一种能够处理等值查询，Join 巨细估量等的数据结构，并且能够供给很强的准确性保证。自 2003 年文献 An improved data stream summar: The count-min sketch and its applications 中提出以来，由于其创立和运用的简单性获得了广泛的运用。
Count-Min Sketch 保护了一个 d*w 的计数数组，关于每一个值，用 d 个独立的 hash 函数映射到每一行的一列中，并对应修正这 d 个位置的计数值。
这样在查询一个值呈现了多少次的时候，仍旧用 d 个 hash 函数找到每一行中被映射到的位置，取这 d 个值的最小值作为估量值。
KaiwuDB供给的列级核算信息包含行数、不同值的数量、NULL 值的数量等。关于列上数据散布不均匀的状况也能够供给直方图核算信息。KaiwuDB 的直方图也是一个近似等高直方图，关于列的不同值小于等于 200 的场景，能够供给类似频率直方图的效果，关于高频值也能表示，可是在处理区间上的不同值的数量上，现在根据 HyperLoglog 的算法不太准确。
小于等于 200 个 bucket：
大于 200 个 bucket：
刺进 10 万个 1 到 10000 的随机值，201, 202, 203, 204, 205, 206 的重复值都增加到 1000 以上，删去 400 到 2000 之间的值，然后创立核算信息和直方图。
三、总结
根据本钱的优化模型（CBO）是现在联系型数据库最干流的优化模型，而核算信息则是 CBO 的基础，必定程度上核算信息的准确性是 CBO 能否发生最优执行方案的要害。核算信息的搜集主要以表级核算信息和列级核算信息为主，在列上数据散布不均匀的状况下，直方图信息的准确性就尤为重要，现在主要以等高直方图、频率直方图和相应的变形直方图为主。
别的，核算信息的准确性虽然是影响发生最优执行方案的要害，可是核算信息的核算也会消耗系统资源。一般状况下相同策略下参加核算的数据越多核算信息越能准表描绘表上数据的实在散布状况，但价值是消耗的资源越多，核算的时刻越长。
通常状况下，会对表上的数据进行采样来搜集核算信息，或许经过增量搜集核算信息的方式来提高搜集核算信息的效率。在参加核算的数据确定的状况下，会经过大略的估量来决议运用哪种策略来搜集核算信息，然后能够更有效的描绘数据散布状况。
关于数据频频变动的表，核算信息的有效性是重点。怎么有效断定核算信息的有效性，以及怎么经过变动的数据修正核算信息是核算信息研讨的难点。别的，关于某些交融型的多模数据库里的某些特别的表，能够依据表自身的特性，尝试新的核算信息策略。如时序数据表，表上的数据有必定的规律性，有些表甚至是增加了降采样规则的，新的策略能够依据降采样的规则来生成或许代替核算信息。
总之，关于传统的联系型数据库，核算信息的搜集是必不可少的部分，核算信息的好坏直接影响执行方案的质量。关于交融型的数据库里的新型的表，能够根据新的策略来核算估算表的数据散布，然后到达核算信息的效果。
