Lucene 查询原理解析

发布网友

共1个回答

热心网友

前言

笔者在日常使用 Elasticsearch 的过程中，经常需要对一些慢查询做一些分析。由于对 Elasticsearch 底层引用的 Lucene 一知半解，常常在解读 Elasticsearch 的 profile 信息时备受困扰，故在此对 Lucene 的底层原理做一些深入的了解，希望能有助于排查工作中遇到的查询性能问题。

本文主要介绍 Lucene 的查询过程和基本原理，从原理和源码级别对查询过程做了描述和分析，可以让你对 Lucene 底层的查询逻辑和过程有个整体的了解。基于此目的，部分细节可暂不做深入探究（如部分索引文件的数据结构等），不影响整体的认知。

说明：本文基于 Lucene 版本 7.2.1，对应 Elasticsearch 版本 6.2.3（公司在用的ES版本），不同的版本可能有些许差异。

一、查询类型

在了解 Lucene 的查询流程之前，我们先认识一下 Lucene 中的几个重要的查询类型。

Lucene 7.2.1 中有以下 Query (具体介绍见org.apache.lucene.search.Query)

https://lucene.apache.org/core/7_2_1/core/org/apache/lucene/search/Query.html

下面列出一些常见的 query 及对其基本用途做个简单描述：

TermQuery

A Query that matches documents containing a term. This may be combined with other terms with a BooleanQuery.

指定某个字段（field）包含某个值。等同于关系型数据库中的 where col = v。

BooleanQuery

A Query that matches documents matching boolean combinations of other queries, e.g. TermQuerys, PhraseQuerys or other BooleanQuerys.

一个可包含多个 query 的组合，如 "TermQuery" + "PhraseQuery" 或者其他 bool 类型的 Query。

WildcardQuery

Implements the wildcard search query. Supported wildcards are *, which matches any character sequence (including the empty one), and ?, which matches any single character. '\' is the escape character.

通配符查询，可以使用*、?这样的通配符，表示匹配任意个字符。注意：wildcard 查询很慢，为了避免极慢的查询（extremely slow）,最好不要使用以“*”开头的 wildcard 查询。

（Elasticsearch实践）wildcard 的使用在生产环境上应该特别注意，当数据量达到一定的规模，对一个 text 字段做 wildcard 查询时，及其损耗 CPU 性能，容易引发 CPU 尖刺，给 ES 的集群稳定性代理一定的影响，严重的话可能引起整个集群的崩塌，慎重！故应该尽量避免这种场景或使用其他替代方案。

Case: 订单号、手机号或者某些较短文本的匹配

可以使用“ngram分词” + TermsQuery 查询的方式满足查询场景，且在数据量较大时，极大地提升查询性能（空间换时间）。

PhraseQuery

A Query that matches documents containing a particular sequence of terms. A PhraseQuery is built by QueryParser for input like "new york".

顾名思义，短语匹配：一个文档字段中的值包含一整个短语（有可能是多个 term），如“new york”这个短语，会构建“new york”的短语匹配查询，只有按顺序出现（new在前，york 在后），才可以命中该文档。

当然，可以调整“slop”的值为 1，意为可以移动一个短语的次数，即，可以将“york往前移动一个位置”，那么这个查询条件将会同时匹配“new york” 和 “york new”命中的文档

PrefixQuery

A Query that matches documents containing terms with a specified prefix. A PrefixQuery is built by QueryParser for input like app*.

前缀匹配查询，简单理解可以认为是 PhraseQuery 的更细化的场景。

MultiPhraseQuery

可以理解成 PhraseQuery（短语匹配查询）的一种更泛化或更为通用的版本。如搜索“Microsoft app*”，使用 MultiPhraseQuery 构建，会先生成“Microsoft”这个TermQuery，再生成满足“app”这个前缀的所有 Term 查询，最后将他们合并在一起做查询。

FuzzyQuery

Implements the fuzzy search query. The similarity measurement is based on the Damerau-Levenshtein (optimal string alignment) algorithm, though you can explicitly choose classic Levenshtein by passing false to the transpositions parameter.

At most, this query will match terms up to 2 edits. Higher distances (especially with transpositions enabled), are generally not useful and will match a significant amount of the term dictionary. If you really want this, consider using an n-gram indexing technique (such as the SpellChecker in the suggest module) instead.

官方建议，编辑值不要大于 2，生产环境上可以使用 n-gram 分词器对指定字段分词，否则会在查询过程中命中大量的文档，从而对最终的查询性能产生较大的影响。

使用编辑距离（莱文斯坦距离）算法计算相似度的查询

编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

RegexpQuery

正则模糊匹配，这个查询在生产环境并不建议使用，应尽量避免。原因同“wildcardQuery”，此处不做赘述

TermRangeQuery

A Query that matches documents within an range of terms.

指定term短语范围的查询，一般字符串范围按照 ascII 码排序。

PointRangeQuery

range queries against single or multidimensional points such as IntPoint.

坐标点的范围查询，常见于经纬度范围查询。

ConstantScoreQuery

A query that wraps another query and simply returns a constant score equal to 1 for every document that matches the query. It therefore simply strips of all scores and always returns 1.

包装了其他的查询，评分都为常量值 1

二、查询流程

先上一个 Lucene 查询的流程图：

1. 查询入口IndexSearcher.search

search 的入口，该类重载了多个 search 方法。

值得说明的是其中重载了 searchAfter、多线程并发 search 等方法，对不同的查询场景做了优化，

如 searchAfter 主要应对深度分页问题，多线程并发 search 其实是使用传入的 ExecuteService 在多个段文件上并发 search，最后做合并。

不论多线程与否，search 的核心逻辑在于对每个段文件的查询、算分。故后续只对单线程场景下做解析。

2. Query 重写

查询流程中，每一种 query 都会继承Query类并重写rewrite方法，以减小底层接口接受入参场景的复杂度。底层的 Lucene 接口通常只需接收“简单的”查询条件（官方称之为primitive querie）。

源码如下

public?abstract?class?Query?{??//?其他代码省略...??/**?Expert:?called?to?re-write?queries?into?primitive?queries.?For?example,???*?a?PrefixQuery?will?be?rewritten?into?a?BooleanQuery?that?consists???*?of?TermQuerys.???*/??public?Query?rewrite(IndexReader?reader)?throws?IOException?{????return?this;??}??//?其他代码省略...}

常见的几个重写 query 如下

这几种 query 的查询逻辑是一致的（都使用了 MultiTermQuery 的rewrite方法），整理处理思路为:

根据对应的“模糊”字段（fuzzy、wildcard、正则等）找到所有对应的 term，生成 n 个 TermQuery，并用 BooleanQuery 将他们组合在一起即可。过多细节此处不赘述。

此处得出的结论是：各种模糊查询在底层都会转化成多个 TermQuery 的组合。

PhraseQuery 改写中有一个特殊情况：如果当前字段的分词结果就才一个（比如：name: “手机”），那么使用 PhraseQuery 查询 name = "xx" 的时候，可以直接转为 TermQuery（就才一个分词结果，要么命中，要么不命中）

BoolQuery 的 rewrite 逻辑主要是处理must、must_not、should、filter这几种查询条件的各种组合情况，对其做一个预处理。如：

数值类型，无需重写

无需重写（Lucene认为性能极好，以至于都不需要做缓存）

TermQuery

PointRangeQuery

BooleanQuery

PhraseQuery

模糊查询 Query：FuzzyQuery、WildcardQuery、PrefixQuery、RegexpQuery、TermRangeQuery

只有一个 filter 查询条件传入，那么会重写成ConstantScoreQuery（filter 无需评分）；

两个相同字段的 must（或 should）查询，那么会合并这两个查询，并将它们的 boost 相加；

如果同一个字段同时出现在 must 查询和 filter 查询中，那么 filter 查询中的条件可去除（因为 must 已经对该条件做了过滤 + 评分了，无需再 filter 一遍）；

甚至 must 和 filter 中的条件本身就是互斥的：must(isDelete == 1) && filter(isDelete != 1)，这样Lucene会直接抛出异常return new MatchNoDocsQuery("FILTER or MUST clause also in MUST_NOT");

还有很多种情况，此处不一一罗列。

3. 生成打分权重 weight

这个阶段主要是为了生成打分的 weight。

我们以 BooleanWeight 举例，其数据结构如下：

final?class?BooleanWeight?extends?Weight?{??/**?The?Similarity?implementation.?*/??final?Similarity?similarity;?//?相关度算法??final?BooleanQuery?query;?//?当前的查询??final?ArrayList<Weight>?weights;?//?当前查询的多个条件的Weight??final?boolean?needsScores;?//?是否需要打分}

假设我们有如下的查询（Elasticsearch 的 DSL）

文档：（空格分隔）{????"id":?"1",????"content":?"a?b?c?d?e"}查询语句：GET?test_index/_search{??"explain":?true,??"query":?{????"bool":?{??????"should":?[????????{??????????"term":?{????????????"content":?{??????????????"value":?"a"????????????}??????????}????????},????????{??????????"term":?{????????????"content":?{??????????????"value":?"b"????????????}??????????}????????},????????{??????????"term":?{????????????"content":?{??????????????"value":?"c"????????????}??????????}????????}??????]????}??}}

那么这里的 BooleanQuery 中的 weight 是三个 TermWeight：

这个流程的核心逻辑在于如何给各个查询条件构造 weight，以便于后续打分时使用。

整体的 BooleanWeight 组成如下（以termWeight(a)为例，这个图很重要，可以细看一下红框中每个字段的组成）：

DocCount - 含有“content”这个字段的文档数量

DocFreq - 词频，出现指定 term 的数量，如“a b a c a b”中，a 的词频 = 3，b 的词频 = 2，c 的词频 = 1

sumTotalTermFreq

域名为"content"的 term 的总数，如 ?id=1, content = "a b c", ?id = 2, content = "a c" 那么总词频 = 3 + 2 = 5

其中，计算红框中的 idf 和 avgdl 两个值的所需参数可从 tip, tim 文件中读取（Lucene 的底层存储文件，可暂不深究，后续另开文章详细介绍）。

至此，TermWeight中最重要的SimWeight字段构建完毕（详见上图），其中的 idf 和 avgdl 也可计算出来，weight 阶段结束

4. 生成 bulkScorer

继续如上的查询语句：

GET?test_index/_search{??"explain":?true,??"query":?{????"bool":?{??????"should":?[????????{??????????"term":?{????????????"content":?{??????????????"value":?"a"????????????}??????????}????????},????????{??????????"term":?{????????????"content":?{??????????????"value":?"b"????????????}??????????}????????},????????{??????????"term":?{????????????"content":?{??????????????"value":?"c"????????????}??????????}????????}??????]????}??}}

在已经得出所有weights的情况下（上述第三步骤得出），调用org.apache.lucene.search.BooleanWeight#booleanScorer方法，其中核心代码如下：

List<Scorer>?prohibited?=?new?ArrayList<>();????Iterator<BooleanClause>?cIter?=?query.iterator();????for?(Weight?w??:?weights)?{??????BooleanClause?c?=??cIter.next();??????if?(c.isProhibited())?{????????//?使用当前weight算分????????Scorer?scorer?=?w.scorer(context);????????if?(scorer?!=?null)?{??????????prohibited.add(scorer);????????}??????}}

简单描述其逻辑：对所有的 weights 依次进行 scorer 打分，weights 变量的实际对象为TermWeight，进而调用org.apache.lucene.search.TermQuery.TermWeight#scorer方法，继续跟进：

@Override????public?Scorer?scorer(LeafReaderContext?context)?throws?IOException?{??????///?...省略其他代码??????//?1.?获取前面查询结果的termState??????final?TermsEnum?termsEnum?=?getTermsEnum(context);??????if?(termsEnum?==?null)?{????????return?null;??????}??????//?2.?最终会调用?Lucene50PostingsReader#postings方法??????PostingsEnum?docs?=?termsEnum.postings(null,?needsScores???PostingsEnum.FREQS?:?PostingsEnum.NONE);??????assert?docs?!=?null;??????//?3.?核心逻辑：根据相似度算法进行打分（默认使用BM25算法）??????return?new?TermScorer(this,?docs,?similarity.simScorer(stats,?context));????}

关于上述的代码的第三步，Lucene 默认使用的 Okapi BM25 算法的计算公式如下：

注：前面的idf部分（log 后面的第一个乘数因子）已在上述 weights 阶段计算得出，另外，对于 norm：

norm：该值描述的是文档长度对打分的影响，满足同一种查询的多篇文档，会因为 norm 值的不同而影响打分值（从.nvd文件中读取）

k1, b 两个是调节因子，默认值为 k1 = 1.2、b = 0.75（经验参数）

至此，每个文档的分值也可以根据现有参数计算得出（部分参数从 Lucene 文件读取）

5. Collector - 查询结果收集

经过如上第四阶段的打分后，最终会给上层返回一个org.apache.lucene.search.Weight.DefaultBulkScorer对象并调用scoreAll方法（如下）：

?static?void?scoreAll(LeafCollector?collector,?DocIdSetIterator?iterator,?TwoPhaseIterator?twoPhase,?Bits?acceptDocs)?throws?IOException?{??????if?(twoPhase?==?null)?{????????for?(int?doc?=?iterator.nextDoc();?doc?!=?DocIdSetIterator.NO_MORE_DOCS;?doc?=?iterator.nextDoc())?{??????????if?(acceptDocs?==?null?||?acceptDocs.get(doc))?{????????????//?搜集文档????????????collector.collect(doc);??????????}????????}??????}?else?{????????//省略...??????}????}??}

进一步跟进，会调用CollectorManager.reduce方法，将多个 collector 的数据进行合并（各自取得分 topN 个文档）

自此，已经拿到了最终的查询结果。

三、小结

本文带大家从上层逐步向下了解了 Lucene 的查询过程，对整体的搜索流程有了一定的认知。熟悉基本流程和关键的查询节点，希望能在日常排查慢查询和优化查询语句时有一定的帮助，助你更快地定位性能卡点。

参考文档

Lucene源码 - v7.2.1

Lucene Java Doc

《Lucene in Action》第二版

Chris的博客

全部栏目

Lucene 查询原理解析