之前一直想看一下lucene range查询的底层原理, 先上网找了下相关资料, 发现非常混乱, 主要是因为lucene的范围查询曾经经历过两个不同的阶段:
- 阶段1: <lucene6.0版本, 用的是类似于trie树的索引结构.
- 阶段2: >=lucene6.0版本, 用的是bkd的索引结构.
网上很多人在自己没搞明白的情况下各种转载甚至魔改, 比如说要解析lucene8.0的范围查询, 然后却贴了一张lucene5.0以前版本的trie树截图, 最开始让我非常摸不着头脑...
这次我希望把两个版本的范围查询原理都搞明白并整理成2篇博客, 以读源码为主, 参考资料为辅, 最大程度保证正确性.
这篇讲的是<lucene6.0版本的原理, 是基于trie树的.
温馨提示: 如果想跟读相关代码, 需要看lucene5.0的代码, 可以用gradle/maven直接引入5.0的jar包看源码即可.
首先我们定义一下问题, 我们这里把范围查询的范围缩小到只讨论数值范围查询. 文本类型的范围查询在lucene中也是支持的, 但是算法比较简单, 这里就不讨论了.
如果我们不采用任何算法, 直接把数值当做文本类型做索引的话, 其实也是可以搜索的, 但是只能做term query, 没法做range query, 因为把数值当成文本的话首先排序就不对.
如给定数值集合1,2,3,12,22,30, 如果当成文本进行索引那么索引的顺序为1,12,2,22,3,30, 索引的顺序首先就不能反应数字的大小, 在这种情况下做范围查询显然是错的.
因此第一个要解决的问题是:
数字->字符串
思路1
给数字前面统一补0, 统一长度. 如 1,2,3,12,22,30 -> 01,02,03,12,22,30, 但是这样的话, 需要补多少0取决于存的数值最大有多大. 如果我们在里面加上一个很大的数, 如1,2,3,12,22,30,10000000, 就必须得补上很多个0, 显然很浪费存储空间.
思路2
因为文本类型数据的本质就是ascii byte[], 因此可以直接把数字转化为ascii byte[], 只要在此过程中保证转化后的结果能反应数字大小就可以. 即如果a>b, 那么transform(a)>transform(b). lucene 采用的就是这个思路, 因为这里转化的细节对我们理解整个算法影响不大, 因此可以暂时略过, 我们只要知道, 所有数字都能转化为ascii byte[], 且保持大小关系不变就行了.
现在我们可以把数字转化为ascii byte[], 且保持大小不变, 就意味着我们可以直接把数字当文本索引了.
现在即可以做term query, 也可以做range query了.
做range query的思路就是因为索引本身的token词典是有序的, 比如索引词典为1,2,3,12,22,30, 我想查找范围2,20, 首先对索引词典做term query查找, 找到2的位置, 然后继续往后遍历, 直到到达某个位置>20为止, 这样就找到了符合的token集合2,3,12. 然后取2,3,12各自的倒排链表的并集就得到了range query的结果.
本质就是把range query改写成了若干个term query的并集. 即 range2, 20 => term(2) OR term(3) OR term(12)
这样虽然是支持range query了, 但是还有个问题, 就是在大数据量的情况下, 改写后的term query的并集非常有可能拥有特别多的条件, 比如在索引中数据连续的情况下, range2,20非常有可能会变成:
代码语言：txt复制term(2) OR term(3) OR term(4) OR term(5) OR term(6) OR term(7) OR ... OR term(20)这就很可怕了, 因为如果我们搜索一个range1000, 2000, 一下就产生了1000个term query, 每个term query都会对硬盘做一次随机读取, 这样性能上肯定会有问题的.
因此第二个要解决的问题是:
范围拆分
范围拆分问题主要针对我们前面说的range query拆分为多个term query产生的term query数量过多. 经过优化可以让我们范围拆分后生成的term query数量大大减少.
其主要思想是trie树. 作者Uwe Schindler利用trie树的思想发明了一种索引结构, 当我们存储索引的时候, 除了正常存储每个数字及其对应的倒排表, 还要存储每个数字的前缀对应的倒排表.
这里我们先来定义一个概念:
粒度
粒度用来指数字的粗糙程度.
粒度为1的数字世界就是我们平时正常的数字世界, 比如从0开始数整数, 我们会数出0,1,2,3,4,5,6 ...
粒度为10的数字世界是这样的, 从0开始数整数, 我们会数出0, 10, 20, 30, 40
粒度为100的数字世界是这样的, 从0开始数整数, 我们会数出0, 100, 200, 300, 400
有了粒度的概念, 我们就知道, 同一个数字, 在不同的粒度世界里, 其对应的数字是不同的, 比如123:
在粒度为1的世界里, 就是123.
在粒度为10的世界里, 会转化为120.
在粒度为100的世界里, 会转化为100.
按照这个逻辑, 我们可以把123这个数字投射为多个term:
代码语言：txt复制1/123
10/120
100/100斜杠左边代表粒度, 右边代表在该粒度下的取值.
前缀索引
现在我们要对数字集合421, 423, 445, 446, 448, 521, 522, 632, 633, 634, 641, 642, 644建立倒排表, 假设每个数字既作为查询词, 又作为docID(即搜索范围500,600则返回文档列表521,522).
我们把每个数字按照粒度1,10,100,1000,10000投射为5个term, 然后索引.
建立索引的结果如下:
代码语言：txt复制1/421 : [421]
1/423 : [423]
1/445 : [445]
1/446 : [446]
1/448 : [448]
1/521 : [521]
1/522 : [522]
1/632 : [632]
1/633 : [633]
1/634 : [634]
1/641 : [641]
1/642 : [642]
1/644 : [644]
10/420 : [421, 423]
10/440 : [445, 446, 448]
10/520 : [521, 522]
10/630 : [632, 633, 634]
10/640 : [641, 642, 644]
100/400 : [421, 423, 445, 446, 448]
100/500 : [521, 522]
100/600 : [632, 633, 634, 641, 642, 644]
1000/0 : [421, 423, 445, 446, 448, 521, 522, 632, 633, 634, 641, 642, 644]
10000/0 : [421, 423, 445, 446, 448, 521, 522, 632, 633, 634, 641, 642, 644]现在我们建立了一个含有多个粒度的索引, 假设要进行范围查询, 查找range423, 642, 按照我们之前做范围查询的方法, 应该是查询:
代码语言：txt复制term(423) OR term(445) OR term(446) OR term(448) OR term(521) OR term(522) OR term(632) OR term(633) OR term(634) OR term(641) OR term(642)当然, 现在因为我们引入了粒度的概念, 其实是查询:
代码语言：txt复制term(1/423) OR term(1/445) OR term(1/446) OR term(1/448) OR term(1/521) OR term(1/522) OR term(1/632) OR term(1/633) OR term(1/634) OR term(1/641) OR term(1/642)现在除了这样傻傻的把所有粒度为1的term都列出来, 还有没有其他方法了? 看看下面的图思考下:
image.png没错, 观察这颗trie树会发现, 其实我们现在不需要再傻傻的查询所有粒度为1的term了.
比如term(1/445) OR term(1/446) OR term(1/448), 其实完全等效于 term(10/440), 我们之前建立的倒排索引的文档列表也体现了这一点:
10/440 : [445, 446, 448]而term(1/521) OR term(1/522) 完全等效于term(100/500) :
100/500 : [521, 522]同理, term(1/632) OR term(1/633) OR term(1/634) 等效于term(10/630):
10/630 : [632, 633, 634]因为, 现在我们可以把query:
代码语言：txt复制term(1/423) OR term(1/445) OR term(1/446) OR term(1/448) OR term(1/521) OR term(1/522) OR term(1/632) OR term(1/633) OR term(1/634) OR term(1/641) OR term(1/642)优化为:
代码语言：txt复制term(1/423) OR term(10/440) OR term(100/500) OR term(10/630) OR term(1/641) OR term(1/642)这下需要访问的倒排表数量降了近1倍, 如果对于更大的范围查询, 差距会更加明显.
我们刚刚是通过看图的方式直观的看出这一转化的, 那么有没有算法可以自动得出呢? 那必须是可以的:
SplitRange
SplitRange是这样一个算法, 他会把原来的一个粒度为1的范围查询, 分解为一组多个粒度的范围查询.
如给定范围423, 642, 会产生结果:
代码语言：txt复制1/[423, 429]
1/[640, 642]
10/[430, 490]
10/[600, 630]
100/[500, 500]可以看出来, 这一组不同粒度的范围加起来, 代表的就是423, 642
这个算法对应lucene的NumericUtils.splitRange(), 不过我们这里为了方便, 用的是10进制作为粒度, 而lucene用的是2进制.
我们会发现, 仅仅通过SplitRange还不能得出我们想要的优化后的term列表, 因为还缺一个算法:
检索算法
现在我们有了前缀索引和SplitRange算法, 还缺少一个检索算法把整体串起来.
- 利用SplitRange对423,642进行范围转换, 得到:
1/[423, 429]
1/[640, 642]
10/[430, 490]
10/[600, 630]
100/[500, 500]- 在倒排索引中抽取粒度匹配且范围匹配的term.
1/[423, 429] -> 1/423
1/[640, 642] -> 1/641, 1/642
10/[430, 490] -> 10/440
10/[600, 630] -> 10/630
100/[500, 500] -> 100/500- 得到query.
term(1/423) OR term(1/641) OR term(1/642) OR term(10/440) OR term(10/630) OR term(100/500)
// 这一步的结果顺序与之前我们自己手动生成的略有不同, 但是term的组成是完全相同的- 把所有倒排表取并集然后排序得到最终结果.
[423, 445, 446, 448, 521, 522, 632, 633, 634, 641, 642]这块逻辑主要对应lucene的NumericRangeQuery中的查询逻辑.
补充说明
到现在, 我们已经了解数值型范围查询的算法核心思想了.
但是讲解的过程中为了方面理解, 都是用10进制作为粒度来说明的, 实际lucene处理的时候是用2进制, 不过思想是完全一样的. 作者在理解算法的过程中, 一开始使用10进制实现了一套算法, 然后稍加修改, 就改成了和lucene一样的2进制的.
这里大概说一下lucene使用的2进制粒度的概念.
我们之前说过, 123按10进制粒度可以投射为:
代码语言：txt复制1/123
10/120
100/100类似的, 假设现在有一个二进制数字1111111111111111111111111111111. 那么它按照1<<8作为粒度可以投射为:
1/01111111,11111111,11111111,11111111
1<<8/01111111,11111111,11111111,00000000
1<<16/01111111,11111111,00000000,00000000
1<<24/01111111,00000000,00000000,00000000嗯, 就是这样, 好像也不需要多余的解释了. 思想和10进制的完全一样, 只是二进制的不方便看而已.
ref
lucene5.0源码
https://www.elastic.co/blog/apache-lucene-numeric-filters
https://www.semanticscholar.org/paper/Generic-XML-based-framework-for-metadata-portals-Schindler-Diepenbroek/ed52c201366045e8ca8a90e6839b483e17c9bce5
