多维数据查询效率分析（3）

rule

　　快捷方式：
　　多维数据查询效率分析（1）
多维数据查询效率分析（2）
　　前面分析了在PostgreSQL和MySQL中进行多维数据查询的挑战。问题的根本在于，按行存储的数据库在行变得很大（wide table）的情况下，一旦索引无法完成所有的查询工作，就会受到行大小的影响。为了避免按行存储的缺陷，按列存储的数据库就被发明了出来。按行存储的数据库有很多，绝大部分都是要花钱的，开源的有MonetDB。和前面相同的数据量，相同的wide table的表设计，用MonetDB可以快上很多：



sql>select count(contact_id) from spike2 where a1 = 7;
+--------+
| L24    |
+========+
| 830569 |
+--------+
1 tuple (24.576ms)
sql>select count(contact_id) from spike2 where a1 = 7 and a2 = 5;
+--------+
| L25    |
+========+
| 164788 |
+--------+
1 tuple (105.352ms)
sql>select count(contact_id) from spike2 where a1 = 7 and a2 = 5 and a3 = 1;
+------+
| L26  |
+======+
| 4040 |
+------+
1 tuple (24.963ms)
　　从结果上来看，普遍是快上10倍，极端情况下要快上100倍。MonetDB之所以快，除了按行存储之外，还有一个秘诀是它会被SQL编译成小的关系代数操作。简单的关系代数操作就比如加法，这个操作就只做两个集合相加。每个“关系代数操作”都是用C甚至汇编优化的。普通的按行存储的数据库的实现其实是外层有个循环，循环体是一个解释器，解析过的SQL和行的记录是输入。而MonetDB的编译实现方式就避免了在循环里放置一个解释器。这样做的好处是有利于CPU做分支预测。因为解释器的代码相对于硬编码的“关系代数操作”来说要复杂得多，相应的分支预测失败率也高很多。
　　MonetDB的缺陷也是非常明显的。每个关系代数操作都要把其结果完全计算出来（Materialized），也就是要占用内存。比如你要SELECT A+B+C，那么A+B的每行的结果就会被计算出来，然后其结果再与C相加。计算越复杂，中间计算结果需要赞用的内存就更多。写MonetDB的教授们显然也是预料到了这方面的问题，带了个研究生研究如何把这个计算不用完全Materialized。研究结果就是一个叫X100的项目。写这个项目的博士生后来去开了公司，名字叫VectorWise。后来这个公司又给Actian并购了。这个X100项目很牛，它在计算A+B+C的时候不是把A+C的所有行都计算了，然后才计算+C，而是分成几kb的小段，把A+B+C连在一起计算。这样做的好处是利用了CPU的缓存，A+B的计算结果还没有从CPU的缓存中移出就被用来计算A+B+C了。

　　高级一些的按行存储的数据库都能比较好的处理内存不够用，需要到磁盘的场景。MonetDB不行，它是完全基于内存映射文件的，一旦需要swap到磁盘，性能就惨不忍睹。

　　那么在完全使用内存的情况下，可以处理多少数据呢？可以大概估算一下一列的大小：
　　5904385 integer => 23m raw data
10518813 integer => 41m raw data
10518813 date time / bigint => 71m raw data
9531627 integer => 37m raw data
9531627 varchar(128) => 37m + 320m raw data (320m is the dictionary, it varies)
　　值得注意的是null也是要占空间的。
　　基于这样的数据，在现在100多G内存的服务器上还是可以达到千万级别的数据处理能力的。对于不太大的数据库的近三个月交易数据还是能够处理得过来的。
　　所以说，如果你要处理的数据量，不超过100GB，那么MonetDB还是值得一试的。要是数据量更大，要么选择Vertica，VectorWise这样的商业产品，要么就得自己做Sharding了。还有一个趋势是，传统的按行存储的数据库也在融合按列存储的特性，出现了一些混合解决方案，比如PAX。总的一个来说，在这个领域，没有完美的，特别成熟的开源解决方案，有可能一方面是因为有这样需要的企业，都是有钱的主吧。另外一方面，普通的PostgreSQL和MySQL要是性能不是特别挑剔（本文限定的1s钟限制其实并不实用，跑个分析任务怎么不得几分钟啊），其实还是堪用的。