Lucene 8--magic WAND

ElasticSearch 7更新后，探究top-k的查询优化
参考资料：ES7更新notes
Magic WAND: Faster Retrieval of Top Hits in Elasticsearch

背景

探究优化，总要知道以前是怎么样的
以前如果要得到 top10，则在各个分片上计算 top10，在进行合并比较得到全局的top10，这也是深分页的原罪，分布式情况下，对于全局排序的困境

演变1

95年提出优化初步方案
方案内容：

• ES或者说Lucene的评分是根据词频等内容来评定的，查一个复杂语句，本质上是一个个查，用公式进行计算的，每个term，理论上都有他的最高分
• 现在举例查询 elasticsearch kibana，假设 elasticsearch的最高分为3.0，kibana为5.0，查询top10，当你已经有10个值超过3.0时，意味着10th的分数肯定已经大于3.0了
• 这就意味着如果一份文档不包含kibana，得分就绝对不会超过3.0.此时就减少了很多文档的评分工作，要知道，评分是一个比较耗性能的操作
• 推广到任意数量term的查询：你有2个term的集合，第一个集合是用来查询的词项，第二个集合的词项只用于计算得分
  初始：Candidate Set={候选准备动态加入后续查询的term} Score Set={每个词项的最高分}

还是回到刚刚的例子，一开始，查询所有文档，每个文档都要计算得分，随着文档数查询的增多，你需要的top10的最低分增大，当增大到3.0时，我们知道，必须要包含kibana单词，因此就可以将kibana从第一个候选set中移到接下去的查询条件中，使得查询更为精确，是的后续的查询变得更快。你可以想象一个例子
a:1,b:2,c:5,d:10
你一开始全算得分，得到最低分为2后，你知道要查b,c,d
最低分到5，你要查c，d
最低分到10，你要查d

演变2

之前的方案那么好，那么难点在哪呢？以至于过了几年才实现

• 问题：分数取决于索引统计信息，例如文档频率（包含给定术语的文档总数），因此向索引添加更多文档也会更改现有分段中过帐的最高分数，这是一个动态的过程，这意味着这种优化只适用于实际中的静态索引
• 转变：
  Lucene从TF-IDF切换到BM25作为其默认评分模型。此举对于MAXSCORE非常重要，因为BM25得分自然是有限的，这使我们能够在不记录索引中的最大分数的情况下实现此优化。当然，这个上限不如我们计算每个术语在所有文档上的最高分数一样好，但它足够好，以便可以在这个问题上恢复工作

按照官网的说法：

we were able to optimize collection of the top matches on dynamic indexes. 
With this change, disjunctions went between 40% and 13x faster when running Lucene's benchmark suite.

• 具体实现，也没有采用MaxScore，而是WAND(Weak And),一个相比之前更好的算法
  WAND保留单个集合，但为每个子句分配权重（在这种情况下为最大分数），并利用权重总和必须大于某个数字的事实，以便不评估所有术语上的所有匹配。这与Lucene和Elasticsearch已经用于“minimum_should_match”大于1的布尔查询的算法相同。算法在minimum_should_match所有权重等于1 的情况下稍微简单一些。

通过跳过一个无需计算分数的文档，使得查询的效率得到提高，但这有一个前提，每个term的得分不可以为负数

演变3

WAND算法哪些缺陷？
一个异常值，可能会使得所有的算法优化速度下降

Block-max WAND是WAND的变体，它利用了每个块可能具有不同最大分数的事实。
它将数据分为一个个的block，然后利用block的最大值而不是全局最大值，来避免异常值的影响。
也因为有block max，可以使得优化时，某些情况下，能直接跳过整个block

*   Scorer gets the same methods as ImpactsEnum: advanceShallow and getMaxScore, with the same contract
     - Disjunctions and conjunctions skip over entire blocks when the sum of max scores is not competitive.
     - Disjunctions now use the block max score instead of the global max score, which helps skip over more documents.
     - This is not documented in the paper, but when a minimum score is set, the score is computed on the fly in order to move to the next doc faster. I did this based on the observation that computing a score was often less costly than advancing another clause. This is especially useful due to the fact that on the contrary to term queries, the maximum score of a block is often not collected.
*   Another difference with the paper is the fact that we have information about blocks at multiple levels. This is one of the ideas described in a follow-up paper (see section 4 of [http://engineering.nyu.edu/~suel/papers/bmm.pdf](http://engineering.nyu.edu/~suel/papers/bmm.pdf)) which is based on the observation that you sometimes want to advance by more than ${block-size}.

Results on wikibigall need to be taken carefully as some tasks are either faster or slower depending on which query is run. Typically queries whose terms match lots of documents but the intersection matches few documents are a bit slower because it takes time to get a good lower bound for the score. Baseline is master, and patch is the combination of the patch on [~~LUCENE-4198~~](https://issues.apache.org/jira/browse/LUCENE-4198 "Allow codecs to index term impacts") and this patch.

对于ES和lucene的意义

2个改变

• 分数可能不再是负数。
• 总命中数不再总是准确的

现在仍可以命中所有，但这会消耗性能

{
  "value": 1000,
  "relation": "gte" // can only be "eq" if equal of "gte" if `value` is a lower bound of the hit count
}

可以告诉Elasticsearch通过track_total_hits参数计算的命中数。如果实际命中数小于此数，则响应将返回准确的命中计数，否则响应将设置值为track_total_hits“gte”作为“关系”的命中数，这意味着实际命中count实际上大于或等于这个数字。值越低track_total_hits，查询越快

• 搜索请求中包含聚合，则此优化将不适用：Elasticsearch仍需要访问所有匹配项以计算聚合