简介：统计信息是为优化器的 cost 估算提供数据撑持，其中很重要的一点需要便是等值查问(EQUALS, IN 等) 场景下的基数估算。概念统计信息是为优化器的 cost 估算提供数据撑持，其中很重要的一点需要便是等值查问(EQUALS, IN 等) 场景下的基数估算。思考以下 CaseCREATE TABLE mc_tac_template (
ID BIGINT ,
NAME varchar(50) NOT NULL,
GENDER varchar(10) NOT NULL,
PRIMARY KEY (ID),
KEY KEY_NAME USING BTREE (NAME),
KEY KEY_GENDER USING BTREE (GENDER)
)
SELECT * FROM User WHERE Name=’wy’ AND Gender=’female’ 咱们的客户同时为性别和姓名设置了索引，这时优化器就要基于各个条件过滤行数多寡来估算抉择不同索引的代价开销。就这个 case 而言，如果选到了 gender 的索引，查问过程很可能就不太妙了。如果统计信息能够提供准确基数，例如 Name=’wy’ 能够过滤出 5 行，Gender=’female’ 只能过滤出一半的数据，优化器就会晓得，此时抉择 KEY_NAME 是代价更小的抉择。为了撑持这里的估算过程，统计信息须要决定应用什么样的算法，这也决定了如何收集，如何估算。算法数据库中的基数估算相似于 Data Sketching，等值场景下的基数估算个别有两种抉择，基于 sample 或基于全量数据。SAMPLE 当数据量增长时，sample 是一种十分无效晋升估算效率的伎俩。但 sample 必须至多面对以下问题● 采样的随机化● 采样数据与整体数据间的差别估算○ 多少 sample 量能力确保误差率● 当新数据呈现时，如何采样采样随机化是个很事实的问题，例如存储中的采样有两种做法，一种按页采样，一种是每页都采一部分数据。第一种计划尽管十分高效，但随机性太差很容易导致估算的成果十分差，第二种计划尽管估算成果高一些，但在 IO 上相当于全量扫描了一遍。
在 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 这篇论文中，作者比拟了基于 Sample 的 GEE/AE 与面向全量数据的 HyperLogLog sketch 算法，HyperLogLog 的精确度完胜。当然这仅仅是在计算 NDV 的场景。当咱们须要某个繁多确定数据在集群中的特色时，sample 都很难答复该类问题。举个例子，数据的存在问题，即某数据是否在集群中存在，如果该数据不在 sample 集中存在，那既有可能整体中也不存在，也有可能只是没有被 sample 到。再例如通过采样估算 ndv 时，如果采样数据 (假如 100000 行) 中 ndv 靠近 100000，那么整体数据(假如 10000000 行) 的 ndv 有可能是 100000，或者也有可能是 10000000。NDV: number of the different valueSample 的数据集更适宜用于解答范畴条件下数据的特色问题。例如通过 sample 的数据来构建直方图，用于解决范畴条件的查问问题，或者通过 sample 集估算多表等值 Join 的基数问题等。这些问题不在本文的探讨范畴内，暂不开展。非 Sample● frequency：等值场景的基数估算就是获取某值在汇合中的数量，也就是一个获取 frequency 的问题 CountMin SketchCountMin Sketch 通常用于解决 frequency 问题。它有点像 Bloom filter，同样须要一个数组以及一个 Hash 函数的汇合，当遍历数据时，每个数据会被各个 Hash 函数 Map 到数组中的某个地位，并使该地位的计数器加 1。在估算环节，取该数据对应所有计数器所得的最小值。能够预感它肯定会确保估算值大于等于实在值，而后再通过一些伎俩确保误差率。具体的原理这里不再赘述。CountMin Sketch 具体原理见 An Improved Data Stream Summary:The Count-Min Sketch and its Applications
CountMin Sketch 最大的问题是当 Sketch 大小不适合时，很容易因 Hash collision 呈现适度收缩的估算。不论是增大 rows（即 Hash 函数）数量或 columns（即 Counter）的数量，都能够缩小错误率。CountMin Sketch 在解决大量反复数据时很有劣势，但在解决非歪斜数据时，很容易产生过于收缩的后果。当然，最开始 CountMin 也是用于解决热点数据获取这种场景。但在数据分布比拟平均的场景并不非常敌对。HyperLogLog+TopN 在 PolarDB-X 中，咱们衡量之后应用 HyperLogLog+TopN 的形式解决 frequency 问题。具体的做法是这样的。HyperLogLog 用于估算出精确的 NDV 值，TopN 用于解决数据歪斜。具体的算法大抵如下：if (topN.get(i) != 0) {return (long)(topN.get(i) / sampleRate);}return (rowcount / cardinality);HyperLogLog 须要扫描全量数据，TopN 能够通过 Sample 数据构建。这种数据结构在解决数据的散布整体较为均匀，仅有多数歪斜重大的数据场景中十分优良。通过 rowcount / cardinality 稳固大多数非歪斜数据，通过 TopN 解决歪斜数据，但 TopN 的 Sample 可能会导致歪斜数据呈现较大偏差。从优化器的需要思考，可能通过估算值显著的区别出歪斜与非歪斜数据，这曾经能够满足 Plan 的抉择需要。测试咱们基于模仿的随机数据，比照了 CountMin Sketch 与 HyperLogLog+TopN，在几个特定场景下的体现。次要察看的数据有以下两项：● 最大误差：估算值与实在值最大差别值● 误差平方差：代表误差范畴的稳固水平数据场景有以下三种：bound = 100000
// 平衡:
for (int i = 0; i < size; i++) {
rs[i] = r.nextInt(bound);}
// 一半数据歪斜到 1000 个 slot 中
if (r.nextBoolean()) {
rs[i] = r.nextInt(1000);} else {
rs[i] = r.nextInt(bound);}
// 一半数据歪斜至 100 个 slot 中
if (r.nextBoolean()) {
rs[i] = r.nextInt(100);} else {
rs[i] = r.nextInt(bound);}算法初始化参数如下：● CountMin Sketch 初始化参数 epsOfTotalCount = 0.0001,confidence=0.99，造成了 7*20000 的 long 数组，sketch 大概占 1M 空间● TopN 固定 sample 10W 个数据，保留约不超过 5000 个最大值。HyperLogLog 精确度在 1.04/sqrt(2^16) = 0.004，空间大概在 50K 以下测试的大抵后果如下:
在最大误差中，CountMin 次要来自于平衡数据的收缩。Hll + TopN 在 10W 的场景最大误差来自于繁多值被估算成了 rowcount/cardinality，但这个误差十分小。在 100W 和 1000W 的场景，Hll + TopN 的最大误差远大于 CountMin，但从整体上判断，HLL+TopN 的误差平方差相比而方更加稳固，这些误差次要来自于 TopN 中未记录的 Skew 数据（未 Sample 到或 TopN 容量有余）。整体上比拟来看，CountMin Sketch 随数据量增长，针对歪斜数据的估算会更精确，但非歪斜数据的估算会呈现较重大偏差，这体现在误差平方差在大数据场景始终放弃较高。Hll+TopN 非歪斜数据的估算中十分稳固且精确，歪斜数据的估算会随数据量增长或 sample 的非随机性减少而有较重大收缩。从等值条件基数估算的场景思考，如果要确保歪斜数据的精确度，应该要抉择 CountMin Sketch，如果要保障非歪斜数据的精确度，歪斜数据只有能辨认出就好，采纳 Hll+TopN 是更加实用的抉择。留神以上测试后果仅针对模仿的数据场景。采集尽管 CountMin 和 HyperLogLog 答复的问题不同(一个是 frequency, 一个是 ndv)，但实质上都是基于 Sketch 来形容整体数据。基于 Sketch 的算法除了内存占用小以外，还有个十分大的益处是多个 Sketch 能够合并，并用于形容多分片数据。大部分统计信息模块须要收集的数据是不须要思考多分片带来的影响的，比如说最大最小值，rowcount，null 值数量，列长度等等。但 ndv 不同，多个分片的 ndv 值无奈简略相加得出。但 HyperLogLog 的 Sketch 数据能够通过多分片合并的形式估算出整体的 ndv 值。CountMin 的 Sketch 也能够通过合并解决。CountMin 和 HyperLogLog 如果想要较高的精确度，必须要扫描全量的数据，但这会至多给 IO 带来微小的影响。Sketch 类型的算法能够针对各个分片数据建设不同的 Sketch，而后仅扫描有数据变更分片并更新其 Sketch，这样防止了扫描全量数据的同时，依然能够在全局失去准确的估算值。
在 Oracle 11g 中，对不沉闷的数据分片分成一组对立进行 sketch，这能够极大缩小 sketch 占用的内存空间结语 The approximate approach is often faster and more efficient–BY GRAHAM CORMODE
到目前为止，数据特色畛域未然开展了很长时间的钻研，十分多的工具被开发进去。本文次要简略介绍了其中一部分基于 Sketch 的技术在数据库等值查问场景中的区别与影响。能够看到，这些技术提供了不同场景下解决特定问题的能力，但并非银弹，审慎衡量的抉择工具，能力带来更佳的优化成果。参考● Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g∗● An Improved Data Stream Summary:The Count-Min Sketch and its Applications● Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates● HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm● Towards Estimation Error Guarantees for Distinct Values● Data Sketching● New Sampling-Based Summary Statistics for Improving Approximate Query Answers● A Comparison of Five Probabilistic View-Size Estimation Techniques in OLAP● http://content.research.neust… 欢送关注 PolarDB- X 知乎机构号，浏览更多技术好文。原文链接：https://click.aliyun.com/m/10… 本文为阿里云原创内容，未经容许不得转载。