ComputeColStats UDF中 近似算法的介绍(续)

摘要：在前一篇文章的最后提到，对于准确率的提升是后续需要做的事情之一。接下来看看对于提升准确率，还有哪些事情可以做。一，回顾首先回顾下前一篇文章最后得到的结果，如下：执行时间先忽略，只看准确率。对于上面８个字段，有些在sample为２５（采样比例１／２５）的情况下还是相当准确的，比如odps_task_type，start_time；而有些则存在一定差距，比如project_name，fuxi_ceil_mem等；还有些存在比较大的差距，比如odps_inst_id，fuxi_avg_cpu。

在前一篇文章的最后提到，对于准确率的提升是后续需要做的事情之一。接下来看看对于提升准确率，还有哪些事情可以做。

一，回顾

首先回顾下前一篇文章最后得到的结果，如下：

b01

执行时间先忽略，只看准确率。对于上面８个字段，有些在sample为２５（采样比例１／２５）的情况下还是相当准确的，比如odps_task_type，start_time；而有些则存在一定差距，比如project_name，fuxi_ceil_mem等；还有些存在比较大的差距，比如odps_inst_id，fuxi_avg_cpu。同样的采样算法，同样的估计算法，对于不同的数据会得到截然不同的结果。这种差异相信决大部分来自于数据本身。

下面就从数据本身来看下到底差异是如何出现的。

二，数据差异

不同的字段存储的数据不同，不同数据可能会存在唯一值上的差异。比如说对于主键，比如说对于纬度直，两者肯定在DistinctValue的分布上肯定是完全不同的。

1，如果该字段为主键，那么RowCount（X轴）和DistinctValue（Y轴）关系类似下图：

b02

这是一条斜率为1的直线。

对于这种情况，目前的算法肯定可以非常准确的估算出DistinctValue值。

2，如果该字段为纬度值（唯一值非常少），那么RowCount（X轴）和DistinctValue（Y轴）关系类似下图：

b03

随着RowCount的增加，DistinctValue也在增加，但到了某个点后DistinctValue基本保持不变。

3，如果该字段为一般字段，随着RowCount的增加而DistinctValue也缓慢增加，类似下图：

b04

三，数据差异导致的DistinctValue的计算误差？

上面一部分列举了三种可能的RowCount和DistinctValue关系。第一种类型是比较简单的，也能很准确的估算出DistinctValue值。而对于第二种和第三种则要困难的多，从测试的结果来看是这样的。

我们采样的前提是，采样算法能保证采样是随机的，每条数据被访问的几率是相同的。但实际上这样的前提是不存在的。这也是目前对第三种的估算也可能存在较大差异的原因。因为按道理来说，其实第三种我们也应该能很好的预估才对。目前的采样算法并不是随机的，数据本身分布对采样的结果影响极大。为了性能和实现起来简单，目前采样的算法是隔n条取1条的方式实现的，并不是真正意义上的随机采样。

针对同一次估算过程，我尝试过不同的拟合回归算法，结果并没有特别的不同，问题并不是在算法上，而是在数据本身上。下面通过对存在较大误差的fuxi_avg_cpu来看下，不同的采样比例下的RowCount和DistinctValue关系的差异。

b05

b06

b07

b08

上面几张图对下对比，能看得出来在不同的采样比例下图形的状态会有很大的变化。差异这么大的话想要比较准确的预估显然是不太现实的。

四，总结

目前看来DistinctValue估算的差异大部分原因是因为采样，想要提高准确率增加采样比例就可以了。而具体回归的算法，则没那么重要了。