Lucene 源码系列——查询原理（上）
第一小节 Lucene 常见查询的使用
从本篇文章开始介绍 Lucene 查询阶段的内容，由于 Lucene 提供了几十种不同方式的查询，但其核心的查询逻辑是一致的，该系列的文章通过 Query 的其中的一个子类 BooleanQuery，同时也是作者在实际业务中最常使用的，来介绍 Lucene 的查询原理。
查询方式
下文中先介绍几种常用的查询方式的简单应用：
- TermQuery
- BooleanQuery
- WildcardQuery
- PrefixQuery
- FuzzyQuery
- RegexpQuery
- PhraseQuery
- TermRangeQuery
- PointRangeQuery
TermQuery
图 1：
图 1 中的 TermQuery 描述的是，我们想要找出包含**域名（FieldName）为“content”，域值（FieldValue）中包含“a”的域（Field）**的文档。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/TermQueryTest.java。
BooleanQuery
图 2：
BooleanQuery 为组合查询，图 2 中给出了最简单的多个 TermQuery 的组合（允许其他查询方式的组合），上图中描述的是，我们期望的文档必须至少（根据 BooleanClause.Occur.SHOULD）满足两个 TermQuery 中的一个，如果都满足，那么打分更高。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/BooleanQueryTest.java。
WildcardQuery
该查询方式为通配符查询，支持两种通配符：
// 星号通配符 *
public static final char WILDCARD_STRING = '*';
// 问号通配符 ?
public static final char WILDCARD_CHAR = '?';
// 转义符号（escape character）
public static final char WILDCARD_ESCAPE = '\\';
星号通配符描述的是匹配零个或多个字符，问号通配符描述的是匹配一个字符，转义符号用来对星号跟问号进行转移，表示这两个作为字符使用，而不是通配符。
图 3：
问号通配符的查询：
图 4：
图 4 中的查询会匹配文档 3，文档 1。
星号通配符的查询：
图 5：
图 4 中的查询会匹配文档 0、文档 1、文档 2、文档 3。
转义符号的使用：
图 6：
图 4 中的查询会匹配文档 3。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/WildcardQueryTest.java。
PrefixQuery
该查询方式为前缀查询：
图 7：
图 7 中的 PrefixQuery 描述的是，我们想要找出包含域名为“content”，域值的前缀值为"go"的域的文档。
以图 3 为例子，图 7 的查询会匹配文档 0、文档 1。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/PrefixQueryTest.java。
FuzzyQuery
该查询方式为模糊查询，使用编辑距离来实现模糊匹配，下面的查询都是以图 3 作为例子：
图 8：
图 8 中的各个参数介绍如下：
- maxEdits：编辑距离的最大编辑值
- prefixLength：模糊匹配到的 term 的至少跟图 8 中的域值"god"有两个相同的前缀值，即 term 的前缀要以"go"开头
- maxExpansions：在 maxEidts 跟 prefixLength 条件下，可能匹配到很多个 term，但是只允许处理最多 20 个 term
- transpositions：该值在本篇文档中不做介绍，需要了解确定型有穷自动机的知识
图 8 中的查询会匹配文档 0、文档 1。
图 9：
图 9 中的方法最终会调用图 8 的构造方法，即 maxExpansions 跟 transpositions 的值会使用默认值：
- maxExpansions：默认值为 50
- transpositions：默认值为 true
图 9 中的查询会匹配文档 0、文档 1。
图 10：
图 10 中的方法最终会调用图 8 的构造方法，即 prefixLength、maxExpansions 跟 transpositions 的值会使用默认值：
- prefixLength：默认值为 0
- maxExpansions：默认值为 50
- transpositions：默认值为 true
图 10 中的查询会匹配文档 0、文档 1、文档 2、文档 3。
图 11：
图 11 中的方法最终会调用图 8 的构造方法，即 maxEdits、maxEprefixLength、maxExpansions 跟 transpositions 的值会使用默认值：
- maxEdits：默认值为 2
- prefixLength：默认值为 0
- maxExpansions：默认值为 50
- transpositions：默认值为 true
图 10 中的查询会匹配文档 0、文档 1、文档 2、文档 3。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/FuzzyQueryTest.java。
RegexpQuery
该查询方式为正则表达式查询，使用正则表达式来匹配域的域值：
图 12：
图 12 中的 RegexpQuery 描述的是，我们想要找出包含**域名（FieldName）为“content”，域值（FieldValue）中包含以"g"开头，以"d"结尾，中间包含零个或多个"o"的域（Field）**的文档。
图 12 中的查询会匹配文档 0、文档 1、文档 2。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/RegexpQueryTest.java。
PhraseQuery
图 13：
该查询方式为短语查询：
图 14：
图 14 中，我们定义了两个 Term，域值分别为"quick"、"fox"，期望获得的这样文档：文档中必须包含这两个 term，同时两个 term 之间的相对位置为 2 （3 - 1），并且允许编辑距离最大为 1，编辑距离用来调整两个 term 的相对位置（必须满足）。
故根据图 13 的例子，图 14 中的查询会匹配文档 0、文档 1、文档 2。
图 15：
图 15 中，我们另编辑距离为 0，那么改查询只会匹配文档 0、文档 1。
图 16：
图 16 中，我们另编辑距离为 4，此时查询会匹配文档 0、文档 1、文档 2、文档 3。
这里简单说下短语查询的匹配逻辑：
- 步骤一：找出同时包含"quick"跟"fox"的文档
- 步骤二：计算"quick"跟"fox"之间的相对位置能否在经过编辑距离调整后达到查询的条件
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/PhraseQueryTest.java。
TermRangeQuery
图 17：
该查询方式为范围查询：
图 18：
图 18 中的查询会匹配文档 1、文档 2、文档 3。
在后面的文章中会详细介绍 TermRangeQuery，对这个查询方法感兴趣的同学可以先看 Automaton，它通过确定型有穷自动机的机制来找到查询条件范围内的所有 term。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/TermRangeQueryTest.java。
PointRangeQuery
图 19：
该查询方式为域值是数值类型的范围查询（多维度查询）：
图 20：
PointRangeQuery 用来实现多维度查询，在图 19 中，文档 0 中域名为"coordinate"，域值为"2, 8"的 IntPoint 域，可以把该域的域值看做是直角坐标系中一个 x 轴值为 2，y 轴值为 8 的一个坐标点。
故文档 1 中域名为"coordinate"的域，它的域值的个数描述的是维度的维数值。
在图 20 中，lowValue 描述的是 x 轴的值在[1, 5]的区间，upValue 描述的 y 轴的值在[4, 7]的区间，我们期望找出由 lowValue 和 upValue 组成的一个矩形内的点对应的文档。
图 21：
图 21 中红框描述的是 lowValue 跟 upValue 组成的矩形。
故图 20 中的查询会匹配文档 1。
在后面的文章中会详细介绍 PointRangeQuery 的查询过程，对这个查询方法感兴趣的同学可以先看 Bkd-Tree 以及索引文件之 dim&&dii，这两篇文章介绍了在索引阶段如何存储数值类型的索引信息。
该查询方式的 demo 见：https://github.com/LuXugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/query/PointRangeQueryTest.java。
第二小节
在第一小节的文章中，我们介绍了几种常用查询方式的使用方法，从本篇文章开始，通过 BooleanQuery 来介绍查询原理。
查询原理流程图
图 1：
执行 IndexSearcher 的 search()方法
根据用户提供的不同参数 IndexSearcher 类提供了多种 search( )方法：
- 分页参数：当用户提供了上一次查询的 ScoreDoc 对象就可以实现分页查询的功能，该内容的实现方式已经在 Collector（二）中介绍，不赘述
- 排序参数：用户通过提供
Sort参数使得查询结果按照自定义的规则进行排序，默认使用 TopFieldCollector 对满足查询条件的结果进行排序。 - Collector 参数：用户通过提供 Collector 收集器来自定义处理那些满足查询条件的文档的方法，如果不提供，那么默认使用 TopFieldCollector 或者 TopScoreDocCollector，如果用户提供了 Sort 参数，那么使用前者，反之使用后者
- TopN 参数：用户通过提供该参数用来描述期望获得的查询结果的最大个数
至于使用上述不同的参数对应哪些不同的 search( )就不详细展开了，感兴趣的同学可以结合上述的参数介绍及源码中的几个 search( )方法，相信很容易能理解。
重写 Query
每一种 Query 都需要重写（rewrite）才能使得较为友好的接口层面（API level）的 Query 完善成一个"最终的（final）"Query，如果这个 Query 已经是"最终的"，就不需要重写，这个最终的 Query 在源码注释中被称为 primitive query。
图 2 中定义了一个 TermQuery（接口层面（API level）的 Query），它**显示的（explicit）**描述了满足查询条件的文档必须包含一个域名（FieldName）为"content"，域值（FIeldValue）中包含"a"的 term（对域值分词后的每一个结果称为 term）的域，我们称这种 TermQuery 是"最终"的 Query。在 TermQuery 中，我们能显示的知道，查询的 term 为"a"。
图 2：
图 3 中定义了一个 PrefixQuery（前缀查询，见第一小节），它描述了满足条件的文档必须包含一个域名为"content"，域值中包含前缀为"go"的 term 的域，相比较 TermQuery，这个查询没有显示的 在用户使用的接口层面（API level）描述我们要查询具体哪个 term，我们称之为这不是一个“最终”的 Query，故需要通过重写 Query 来完善成一个新的 Query，先找到以"go"为前缀的所有 term 集合，然后根据这些 term 重新生成一个 Query 对象，具体过程在下文中展开。
图 3：
注意的是上述的介绍只是描述了重写 Query 的其中一个目的。
根据第一小节中介绍的 9 种 Query，我们分别来讲解这些 Query 的重写过程。
TermQuery
TermQuery 不需要重写。
PointRangeQuery
数值类型的查询，它没有重写的必要。
BooleanQuery
BooleanQuery 的重写过程在 BooleanQuery 的文章中介绍，不赘述。
PhraseQuery
PhraseQuery 的重写会生成以下两种新的 Query：
- TermQuery：图 4 中的 PhraseQuery，它只有一个域名为“content”，域值为"quick"的 term，这种 PhraseQuery 可以被重写为 TermQuery，TermQuery 是所有的查询性能最好的查询方式（性能好到 Lucene 认为这种查询方式都不需要使用缓存机制，见 LRUQueryCache，可见这次的重写是一个完善的过程
图 4：
- PhraseQuery：图 5 中的 PhraseQuery 跟图 6 中的 PhraseQuery，他们的查询结果实际是一致的，因为对于图 5 的 PhraseQuery，它会在重写 PhraseQuery 后变成图 6 中的 PhraseQuery，也就是这种查询方式只关心 term 之间的相对位置，对于图 5 中的 PhraseQuery，在重写的过程中，"quick"的 position 参数会被改为 0，"fox"的 position 参数会被改为 2，由于本篇文章只是描述 PhraseQuery 的重写过程，对于为什么要做出这样的重写逻辑，在后面的文章中会展开介绍
图 5：
图 6：
FuzzyQuery、WildcardQuery、PrefixQuery、RegexpQuery、TermRangeQuery
这几种 Query 的重写逻辑是一致的，在重写的过程中，找到所有的 term，每一个生成对应的 TermQuery，并用 BooleanQuery 封装。
他们的差异在于不同的 Query 还会对 BooleanQuery 进行再次封装，不过这不是我们本篇文章关心的。
下面用一个例子来说明上面的描述：
图 7：
图 8：
图 8 中我们使用 TermRangeQuery 对图 7 中的内容进行查询。
图 9：
图 9 中我们使用 BooleanQuery 对图 7 中的内容进行查询。
图 8 中 TermRangeQuery 在重写的过程中，会先找到"bc" ~ "gc"之间的所有 term（查找方式见 Automaton），这些 term 即"bcd"、"ga"、"gc"，然后将他们生成对应的 TermQuery，并用 BooleanQuery 进行封装，所以图 8 中的 TermRangeQuery 相当于图 9 中的 BooleanQuery。
不得不提的是，TermRangeQuery 最终重写后的 Query 对象不仅仅如此，生成 BooleanQuery 只是其中最重要，最关键的一步，本篇文章中我们只需要了解到这个程度即可，因为在后面的文章会详细介绍 TermRangeQuery。
所有的 Query 在查询的过程中都会执行该流程点，但不是重写 Query 唯一执行的地方，在构建 Weight 的过程中，可能还会执行重写 Query 的操作。
生成 Weight
不同的 Query 生成 Weight 的逻辑各不相同，由于无法介绍所有的情况，故挑选了最最常用的一个查询 BooleanQuery 来作介绍。
图 10：
图 11：
图 10 跟图 11 分别是索引阶段跟查询阶段的内容，我们在查询阶段定义了一个 BooleanQuery，封装了 3 个 TermQuery，该查询条件描述的是：我们期望获得的文档中至少包含三个 term，"h"、"f"、"a"中的一个。
BooleanWeight
对于上述的例子中，该 BooleanQuery 生成的 Weight 对象如下所示：
图 12：
BooleanQuery 生成的 Weight 对象即 BooleanWeight 对象，它由三个 TermWeight 对象组合而成，TermWeight 即图 11 中封装的三个 TermQuery 对应生成的 Weight 对象。
TermWeight
图 13 中列出了 TermWeight 中至少包含的几个关键对象：
图 13：
Similarity
Similarity 描述的是当前查询使用的文档打分规则，当前 Lucene7.5.0 中默认使用 BM25Similarity。用户可以使用自定义的打分规则，可以在构造 IndexSearcher 后，执行 IndexSearcher 的 search()方法前，调用 IndexSearcher.setSimilarity(Similarity)的方法设置。Lucene 的文档打分规则在后面的文章中会展开介绍。
SimWeight
图 14：
图 14 中描述的是 SimWeight 中包含的几个重要的信息，这些信息在后面的流程中用来作为文档打分的参数，由于 SimWeight 是一个抽象类，在使用 BM25Similarity 的情况下，SimWeight 类的具体实现是 BM25Stats 类。
我们以下图中红框标识的 TermQuery 为例子来介绍 SimWeight 中的各个信息
图 15：
field
该值描述的是 TermQuery 中的域名，在图 15 中，field 的值即“content”。
idf
idf 即逆文档频率因子，它的计算公式如下：
(float) Math.log(1 + (docCount - docFreq + 0.5D)/(docFreq + 0.5D))
- docCount：该值描述是包含域名为“content”的域的文档的数量，从图 10 中可以看出，文档 0~文档 9 都包含，故 docCount 的值为 10
- docFreq：该值描述的是包含域值"h"的文档的数量，从图 10 中可以看出，只有文档 0、文档 8 包含，故 docFreq 的值为 2
- 0.5D：平滑值
boost
该值描述的是查询权值（即图 17 中打分公式的第三部分），boost 值越高，通过该查询获得的文档的打分会更高。
默认情况下 boost 的值为 1，如果我们期望查询返回的文档尽量是通过某个查询获得的，那么我们就可以在查询（搜索）阶段指定这个查询的权重，如下图所示：
图 16：
相比较图 15，在图 16 中，我们使用 BoostQuery 封装了 TermQuery，并显示的指定这个查询的 boost 值为 100。
图 16 中的查询条件表达了这么一个意愿：我们更期待在执行搜索后，能获得包含"h"的文档。
avgdl
avgdl（average document length，即图 17 中打分公式第二部分中参数 K 中的 avgdl 变量）描述的是平均每篇文档（一个段中的文档）的长度，并且使用域名为"content"的 term 的个数来描述平均每篇文档的长度。
例如图 7 中的文档 3，在使用空格分词器（WhitespaceAnalyzer）的情况下，域名为"content"，域值为"a c e"的域，在分词后，文档 3 中就包含了 3 个域名为"content"的 term，这三个 term 分别是"a"、"c"、"e"。
avgdl 的计算公式如下：
(float) (sumTotalTermFreq / (double) docCount)
- sumTotalTermFreq：域名为"content"的 term 的总数，图 7 中，文档 0 中有 1 个、文档 1 中有 1 个，文档 2 中有 2 个，文档 3 中有 3 个，文档 4 中有 1 个，文档 5 中有 2 个，文档 6 中有 3 个，文档 7 中有 1 个，文档 8 中有 8 个，文档 9 中有 6 个，故 sumTotalTermFreq 的值为（1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 8 + 6）= 28
- docCount：同 idf 中的 docCount，不赘述，该值为 10
cache
cache 是一个数组，数组中的元素会作为 BM25Similarity 打分公式中的一个参数 K（图 17 打分公式第二部分的参数 K），具体 cache 的含义会在介绍 BM25Similarity 的文章中展开，在这里我们只需要了解 cache 这个数组是在生成 Weight 时生成的。
weight
该值计算公式如下：
idf * boost
图 17 是 BM25Similarity 的打分公式，它由三部分组成，在 Lucene 的实现中，第一部分即 idf，第三部分即 boost，至此我们发现，在生成 Weight 的阶段，除了文档号跟 term 在文档中的词频这两个参数，我们已经获得了计算文档分数的其他条件，至于为什么需要文档号，不是本篇文章关系的部分，再介绍打分公式的文章中会展开介绍，另外 idf 跟 boost 即 SimWeight 中的信息，不赘述。
图 17：
图 17 源自于 << 这就是搜索引擎 >>，作者：张俊林。
TermContext
图 18：
图 18 中描述的是 TermContext 中包含的几个重要的信息，其中红框标注表示生成 Weight 阶段需要用到的值，这些信息通过读取索引文件.tip、tim 中的内容获得，其读取过程不再这里赘述（因为太复杂~），不过会在以后的文章中介绍，而每个变量的含义都在.tip、tim 中详细介绍了，不赘述。
图 19 中是索引文件。tim 的数据结构：
图 19：
上文中，计算 idf（DocCount、DocFreq）跟 avgdl（SumTotalTemFreq、DocCount）需要用到的信息在图 19 中用红框标注。
最后给出完整的 BooleanWeight 包含的主要信息：
图 20：
关于 Weight 的一些其他介绍
生成 Weight 的目的是为了不更改 Query 的属性，使得 Query 可以复用。
从 Weight 包含的主要信息可以看出，生成这些信息的目的就是为了文档打分，那如果我们不关心文档的打分，生成 Weight 的过程又是如何呢？
这个问题包含了两个子问题：
问题一：如何设置不对文档进行打分：
- 我们在执行 IndexSearcher 的 search()方法时，需要提供自定义的 Collector，并且通过 Collector.needsScores( )来设置为不对文档进行打分
问题二：生成的 Weight 有什么不同：
- 由于不需要对文档进行打分，所以不需要用到 TermContext，即 TermContext 为 null，同时也不需要 SimWeight，这两个信息都是为文档打分准备的
- 如果设置了查询缓存（queryCache，默认开启），那么在不对文档打分的前提下，我们还可以使用查询缓存机制，当然使用缓存机制的前提是有要求的，感兴趣可以看 LRUQueryCache
小结
基于篇幅，本篇只介绍了图 1 中的三个流程点 执行IndexSearcher的search()方法、重写Query、生成Weight，从本文的内容可以看出，想要深入了解查询逻辑的前提是熟悉索引文件的数据结构。
原文链接：
https://www.amazingkoala.com.cn/Lucene/Search/2019/0820/86.html
https://www.amazingkoala.com.cn/Lucene/Search/2019/0821/87.html
