BlinkDB及其问题

BlinkDB是UCBerkeley和MIT的Sam一起做出来的一个基于Sampling的系统，系统大致成型的时间在2012年前后，该论文也投过DB的会议一路被拒，最后发表于操作系统会议EuroSys并且拿到了最佳论文奖。

和其他那些投database会议被拒然后系统会议发出来的文章相同的原因是Database会议质疑这篇文章的原创性。不同的是我觉得这篇文章所描述的系统的可用性也同样有问题。鉴于这些只是我个人的观点，大家有兴趣不妨读读原论文再做自己的判断。

我PhD的时候东西比较杂，但是最主要的还是Database Sampling和Probabilistic Database。前者我把该领域从1980年起到2007年的数据库三大会SIGMOD, VLDB, ICDE上发表的论文，差不多200篇，都读过。为了让问题通俗易懂，我就不用数学公式来叙述了，我的描述就不会很严谨，但是作为通俗读物应该也可以凑合看了。

Sampling在database最早起源于198x年，首先被研究的问题是，如果有个sample在手，我可不可以更快的回答SQL查询，当然结果是近似的。这样可以省时间。答案是是的，对某些查询比较容易，某些则很难。后面理论很多，最难的一般来说是Join和Not In这样的查询，还有像Min Max Mean这样的函数。举个简单的例子。比如说微软有10万员工，我想知道微软一年到底发了多少工资。我可以随机选100个员工，然后把这100个员工的工资加起来，结果放大1000倍，我就可以认为这个数字是微软发的总工资的一个近似值。

这个近似值可能比较准确也可能不太准确。不准确取决于两个因素：Variance和Bias。Variance叫方差，意思是随机样品和实际值之间的距离。这个东西随着Sample的大小越来越大，就越来越小，1000个员工来估计肯定比100个准确。Bias中文直白的意思是偏倚，就是说如果你的Sample不够随机，比如说你总是去挑领导进来，级别高的进来，那么估计出来的总工资肯定偏高啊，反之亦然。

通常我们追求没有bias的办法来采样，但是variance不可避免，且和sample大小有关。这个东西流行开来之后有人就质疑，因为大家都假设有sample在了。所以有一堆人去研究怎么获得这些sample，那就是另外一个坑。研究的结果发现sample的代价不低。比如说最长见的resovoir sampling需要对整个表都扫一遍。这样一来，很多人就质疑这些用sample的办法是不是实际。代价高了不如直接执行整个查询了。

人类总是聪明的，有聪明的人就想到了一个办法，我们可以采样一次，然后让无数多个查询共享这一个sample。这个办法催生了又一圈的论文。而BlinkDB的核心思想就是对大数据预先采样，存Sample。这样当查询过来的时候就可以用现有的技术去给出结果。我不觉得BlinkDB系统有什么创新性因为其所使用的技术不论是采样还是查询都是老的东西。

共享Sample其实有严重的副作用。天下没有免费的午餐。这是为什么很多人会发论文灌水但是却无法真正用Sampling做一个系统。他们不敢做。这个副作用也是目前整个Sampling研究领域很多人都知道，但是大家都没有特别好的解决办法，所以很多资深做sampling的人刻意回避的东西。换句话，这也是我自己独立发现这些问题以后深感自己才疏学浅解决无望而离开这个领域的主要原因。

从这个角度讲，我觉得做BlinkDB的人起码都不是在sampling这个领域做得比较深的人，不知道这个领域的界限在哪里。只是随便从领域里面抓了一些采样和做近似查询的办法，凑出一个系统来。这个Sample共享的副作用不太好描述，我就不从数学上严格的去描述，举个例子吧。我们考虑两种不同的情况，10000个人去对系统做查询：

（1）系统提供独立的sample

（2）系统共享了一个sample

如果我们再极端一点，假设这10000个人的SQL语句是一样的。并且假设系统提供了95%的置信区间。在第一种情况下，10000个人都错的概率是0.05的10000次方，无限接近于0. 这里我们使用了sample的独立性。第二种情况下呢，既然数据是一样，查询是一样，结果当然也是一样的。所以10000个人同时错的概率还是0.05.

在数据分析里面，10000个人同时错的概率0.05，就是高风险了。当然我举了一个极端的例子。但是通俗一点说，数据共享给不同的查询之间带来了相关性。这些相关性导致这些查询结果同时错的概率不再是独立概率算出来的那个低风险的了。一颗蟑螂屎坏掉一锅赤豆粥。一个sample拿出来是坏的，一堆的查询都给搞坏了。一个实际的分析系统，倘若不能有效的告诉用户实际面对的答案错误的风险到底有多高的话，这个系统在实际分析过程中就会很麻烦了。

当然我们可以说，一个查询一个独立的sample代价太高。大家都共享危险太大。所以可以一个sample用到一定程度以后换新的。但是取得sample的代价本身并不低。而数学上严格描述这种风险，又很困难。纯粹基于Sample的系统用于决策，风险高，不实用，也容易误导人。我曾经试图尝试去发明一种简洁易懂的方法，做了很久，限于天资有限和数学上的底子不够深厚，一直未能有进展。几年后不得不放弃。

我之所以想要说BlinkDB这个系统既无创新，也不实用，理由一方面在于这个系统只是已有的方法的堆积，没有太多新鲜东西，更重要的还是这个系统的作者们，其实不是搞Sampling的，对这个领域的认识本身也很浅薄。所以这只是一片拼凑出来的论文，既不够创新也不实用。