ElasticSearch 7更新后，探究top-k的查詢優(yōu)化
參考資料：ES7更新notes
Magic WAND: Faster Retrieval of Top Hits in Elasticsearch

背景

探究優(yōu)化，總要知道以前是怎么樣的
以前如果要得到 top10，則在各個分片上計算 top10，在進行合并比較得到全局的top10，這也是深分頁的原罪，分布式情況下，對于全局排序的困境

演變1

95年提出優(yōu)化初步方案
方案內容：

• ES或者說Lucene的評分是根據(jù)詞頻等內容來評定的，查一個復雜語句，本質上是一個個查，用公式進行計算的，每個term，理論上都有他的最高分
• 現(xiàn)在舉例查詢 elasticsearch kibana，假設 elasticsearch的最高分為3.0，kibana為5.0，查詢top10，當你已經(jīng)有10個值超過3.0時，意味著10th的分數(shù)肯定已經(jīng)大于3.0了
• 這就意味著如果一份文檔不包含kibana，得分就絕對不會超過3.0.此時就減少了很多文檔的評分工作，要知道，評分是一個比較耗性能的操作
• 推廣到任意數(shù)量term的查詢：你有2個term的集合，第一個集合是用來查詢的詞項，第二個集合的詞項只用于計算得分
  初始：Candidate Set={候選準備動態(tài)加入后續(xù)查詢的term} Score Set={每個詞項的最高分}

還是回到剛剛的例子，一開始，查詢所有文檔，每個文檔都要計算得分，隨著文檔數(shù)查詢的增多，你需要的top10的最低分增大，當增大到3.0時，我們知道，必須要包含kibana單詞，因此就可以將kibana從第一個候選set中移到接下去的查詢條件中，使得查詢更為精確，是的后續(xù)的查詢變得更快。你可以想象一個例子
a:1,b:2,c:5,d:10
你一開始全算得分，得到最低分為2后，你知道要查b,c,d
最低分到5，你要查c，d
最低分到10，你要查d

演變2

之前的方案那么好，那么難點在哪呢？以至于過了幾年才實現(xiàn)

• 問題：分數(shù)取決于索引統(tǒng)計信息，例如文檔頻率（包含給定術語的文檔總數(shù)），因此向索引添加更多文檔也會更改現(xiàn)有分段中過帳的最高分數(shù)，這是一個動態(tài)的過程，這意味著這種優(yōu)化只適用于實際中的靜態(tài)索引
• 轉變：
  Lucene從TF-IDF切換到BM25作為其默認評分模型。此舉對于MAXSCORE非常重要，因為BM25得分自然是有限的，這使我們能夠在不記錄索引中的最大分數(shù)的情況下實現(xiàn)此優(yōu)化。當然，這個上限不如我們計算每個術語在所有文檔上的最高分數(shù)一樣好，但它足夠好，以便可以在這個問題上恢復工作

按照官網(wǎng)的說法：

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.

• 具體實現(xiàn)，也沒有采用MaxScore，而是WAND(Weak And),一個相比之前更好的算法
  WAND保留單個集合，但為每個子句分配權重（在這種情況下為最大分數(shù)），并利用權重總和必須大于某個數(shù)字的事實，以便不評估所有術語上的所有匹配。這與Lucene和Elasticsearch已經(jīng)用于“minimum_should_match”大于1的布爾查詢的算法相同。算法在minimum_should_match所有權重等于1 的情況下稍微簡單一些。

通過跳過一個無需計算分數(shù)的文檔，使得查詢的效率得到提高，但這有一個前提，每個term的得分不可以為負數(shù)

演變3

WAND算法哪些缺陷？
一個異常值，可能會使得所有的算法優(yōu)化速度下降

Block-max WAND是WAND的變體，它利用了每個塊可能具有不同最大分數(shù)的事實。
它將數(shù)據(jù)分為一個個的block，然后利用block的最大值而不是全局最大值，來避免異常值的影響。
也因為有block max，可以使得優(yōu)化時，某些情況下，能直接跳過整個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個改變

• 分數(shù)可能不再是負數(shù)。
• 總命中數(shù)不再總是準確的

現(xiàn)在仍可以命中所有，但這會消耗性能

{
  "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參數(shù)計算的命中數(shù)。如果實際命中數(shù)小于此數(shù)，則響應將返回準確的命中計數(shù)，否則響應將設置值為track_total_hits“gte”作為“關系”的命中數(shù)，這意味著實際命中count實際上大于或等于這個數(shù)字。值越低track_total_hits，查詢越快

• 搜索請求中包含聚合，則此優(yōu)化將不適用：Elasticsearch仍需要訪問所有匹配項以計算聚合