听说过时序数据库吗？( 三 ) _时序数据库

如何联合索引查询？
所以给定查询过滤条件 age=18 的过程就是先从term index找到18在term dictionary的大概位置，然后再从term dictionary里精确地找到18这个term，然后得到一个posting list或者一个指向posting list位置的指针。然后再查询 gender=女的过程也是类似的。最后得出 age=18 AND gender=女就是把两个 posting list 做一个“与”的合并。
这个理论上的“与”合并的操作可不容易。对于mysql来说，如果你给age和gender两个字段都建立了索引，查询的时候只会选择其中最selective的来用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉。那么要如何才能联合使用两个索引呢？有两种办法：

使用skip list数据结构。同时遍历gender和age的posting list，互相skip；
使用bitset数据结构，对gender和age两个filter分别求出bitset，对两个bitset做AN操作。

PostgreSQL 从 8.4 版本开始支持通过bitmap联合使用两个索引，就是利用了bitset数据结构来做到的。当然一些商业的关系型数据库也支持类似的联合索引的功能。Elasticsearch支持以上两种的联合索引方式，如果查询的filter缓存到了内存中（以bitset的形式），那么合并就是两个bitset的AND 。如果查询的filter没有缓存，那么就用skip list的方式去遍历两个on disk的posting list 。
利用 Skip List 合并:

文章插图

以上是三个posting list 。我们现在需要把它们用AND的关系合并，得出posting list的交集。首先选择最短的posting list，然后从小到大遍历。遍历的过程可以跳过一些元素，比如我们遍历到绿色的13的时候，就可以跳过蓝色的3了，因为3比13要小。
整个过程如下：
Next -> 2Advance(2) -> 13Advance(13) -> 13Already on 13Advance(13) -> 13 MATCH!!!Next -> 17Advance(17) -> 22Advance(22) -> 98Advance(98) -> 98Advance(98) -> 98 MATCH!!!最后得出的交集是[13,98]，所需的时间比完整遍历三个posting list要快得多。但是前提是每个list需要指出Advance这个操作，快速移动指向的位置。什么样的list可以这样Advance往前做蛙跳？skip list：

文章插图

从概念上来说，对于一个很长的posting list，比如：
[1,3,13,101,105,108,255,256,257]
我们可以把这个list分成三个block：
[1,3,13] [101,105,108] [255,256,257]
然后可以构建出skip list的第二层：
[1,101,255]
1,101,255分别指向自己对应的block 。这样就可以很快地跨block的移动指向位置了。
Lucene自然会对这个block再次进行压缩。其压缩方式叫做Frame Of Reference编码。示例如下：

文章插图

考虑到频繁出现的term（所谓low cardinality的值），比如gender里的男或者女。如果有1百万个文档，那么性别为男的posting list里就会有50万个int值。用Frame of Reference编码进行压缩可以极大减少磁盘占用。这个优化对于减少索引尺寸有非常重要的意义。当然mysql b-tree里也有一个类似的posting list的东西，是未经过这样压缩的。
因为这个Frame of Reference的编码是有解压缩成本的。利用skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的block的过程，从而节省了cpu 。
利用bitset合并
Bitset是一种很直观的数据结构，对应posting list如：
[1,3,4,7,10]
对应的bitset就是：
[1,0,1,1,0,0,1,0,0,1]
每个文档按照文档id排序对应其中的一个bit 。Bitset自身就有压缩的特点，其用一个byte就可以代表8个文档。所以100万个文档只需要12.5万个byte 。但是考虑到文档可能有数十亿之多，在内存里保存bitset仍然是很奢侈的事情。而且对于个每一个filter都要消耗一个bitset，比如age=18缓存起来的话是一个bitset，18<=age<25是另外一个filter缓存起来也要一个bitset 。
所以秘诀就在于需要有一个数据结构：

可以很压缩地保存上亿个bit代表对应的文档是否匹配filter；
这个压缩的bitset仍然可以很快地进行AND和 OR的逻辑操作。

Lucene使用的这个数据结构叫做 Roaring Bitmap 。

文章插图

其压缩的思路其实很简单。与其保存100个0，占用100个bit 。还不如保存0一次，然后声明这个0重复了100遍。
这两种合并使用索引的方式都有其用途。Elasticsearch对其性能有详细的对比（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps）。简单的结论是：因为Frame of Reference编码是如此高效，对于简单的相等条件的过滤缓存成纯内存的bitset还不如需要访问磁盘的skip list的方式要快。