Lucene搜索流程(下)
在上一篇文章中，重點講到了如何通過TermsDict定位Term所對應的Postings的位置，以及讀取Posting的過程，我們姑且將這部分理解為一次搜索過程中的后端處理。上篇文章還將搜索的主要流程，簡單概括為如下七個步驟：
在上一篇文章中，重點講到了如何通過TermsDict定位Term所對應的Postings的位置，以及讀取Posting的過程，我們姑且將這部分理解為一次搜索過程中的后端處理。上篇文章還將搜索的主要流程，簡單概括為如下七個步驟：
解析查詢條件生成一棵邏輯語法樹
提取基于Term的原子查詢
通過字典信息定位Term的Postings位置
讀取Posting用于文檔匹配
構建評分器對文檔評分
按語法樹的定義執行邏輯運算
通過Collector收集目標文檔集合
如此看來，上篇文章的內容只講解了第3步與第4步的處理流程。這篇文章，將繼續探討余下的內容。
Query
對于常見的組合查詢條件，IndexSearch需要先將查詢條件解析成一顆語法樹。語法樹的所有葉子結點均為一個原子搜索，如TermQuery，這意味著需要基于IndexReader讀取某一個Term對應的Postings信息。非葉子節點則需要匯聚子節點的計算結果。
但如果用戶提交的查詢原本就是一個原子查詢，那就略去了上面提到的解析過程。
TermQuery
我們先來看一下最基礎的TermQuery的處理流程。
TermQuery按下圖流程得到Postings信息，并構建成一個PostingsEnum對象(Postings信息被封裝在PostingEnum對象中)，它是一個迭代器。PostingsEnum中的元素按DocID升序存放，它提供了advance操作來將迭代器指針移動到指定位置并返回相應的元素。advance操作將在本文后面的內容中詳細介紹。
關于Posting讀取的過程，在上篇文章中已詳細講過，這個過程中，還記錄了Term的相關統計信息(如TTF, TDF等)，這些信息將被應用在后續的評分過程中。
有了Posting信息以后，緊接著就是文檔的匹配和評分流程。IndexSearch利用Query創建一個Weight對象用于文檔的二次匹配(諸如PhraseQuery需要去除距離不符的文檔)，這部分內容上文中也講過，然后，再由Weight對象創建出一個Scorer對象用于文檔評分工作。
Query查詢TermsDict之后獲得的Postings會給Weight，所以，Weight對象可直接訪問Postings。對于TermWeight而言，它只負責兩件事: 一方面創建一個與它對應的Scorer評分器，由它負責文檔的評分方面工作。另一方面，通過matches接口向外部提供訪問Term的Postings信息，即指定的Term出現在哪些文檔上，在每個文檔中出現的次數位置和每個位置附帶額外信息。
Scorer由Weight對象創建，但Weight需要結合Terms在候選文檔上的位置信息和Payload信息對評分結果進行explain。
Scorer是Lucene在搜索流程用于計算Query與文檔相似度計算的外圍組件，它實際上并不負責文檔得分的計算，這部分工作委托給了Similarity。Similarity才是真正的評分器，而Scorer只是負責評分外圍的工作。比如它為文檔評分提供必須參數，決定文檔是否需要評分，哪部分文檔進行評分，哪些文檔不用評分。也就說它決定了讀取Postings信息的種類和模式，是否啟用跳表優化等。
注：Query與文檔的相似度代表文檔在這次查詢的得分，得分越高，相似度越高?？蓪⑽臋n得分與相似度理解為相同的含義.
雖然Scorer不負責文檔得分的計算，但文檔的最終評分卻是由Scorer提供的。Lucene實現了兩種常用的評分計算模型，空間向量模型和BM25概率模型。這兩種模型都依賴于TF-IDF，它是一種統計方法，可以粗略的將二者關系理解為：TF-IDF用于計算權重，兩模型通過權重計算相似度。從Lucene 6.0版本開始，已經默認使用了BM25概率模型。
TF-IDF用于計算查詢詞Term文檔或者Query的權重，那么文檔與Query的相似度如何用這兩種權重來表示呢？以空間向量模型為例，Query中的Term系列，可以計算得每個Term的文檔權重，得到文檔權重系列，它也是文檔權重的向量。同樣的方式也可以得到Query權重的向量，那么Query與文檔的最終相似度便可以表示為兩向量的距離。
至于如何決定文檔是否需要評分，Lucene定義了三種模式分別如下：
TOP_SCORE，最常用的方式，即按文檔得分取查詢結果集的TopK
COMPLETE，則需要為所有候選文檔都進行評分
NOT_COMPLETE，與COMPLETE相反，它表示完全不需要評分
關于評分模式，通常由collector決定的，如在大部分的facet查詢的collector便是完全無須評分的。但也有由排序的條件決定，如按字段排序。
在默認情況下，即如果沒有指定Collector和排序條件，IndexSearcher就會采用TOP_SCORE模式，僅給用戶返回TopK文檔。顯然Lucene僅需要對頭部文檔進行評分即可，即跳過部分候選文檔不用為之計算就可以淘汰的。
Lucene為什么可以直接淘汰跳過部分文檔，而不需要為之計算評分，且最終不影響召回的結果集呢？
首先從評分角度看，哪些因素會最終影響了評分呢？下面是對Lucene官方文檔給出的TFIDFSimlarity相似度評分公式：
doc_freq表示搜索關鍵詞term出現在多少個文檔中
doc_count表示整個Segment的總文檔個數
frequency(t,d)表示詞條t在文檔d中出現頻次 norm(t,d)表示詞條t在文檔d歸一化因子 其中這兩個函
norm(t,d)和frequency(t,d)的值與本文中的上下文均用norm和freq表示。
由此可見，其中只有norm(t,d)和frequency(t,d)是隨文檔變化的，其它參數都在segment內確定不變的固定值。也可以理解為，在一個Segment范圍內，freq和norm值直接決定了一個文檔的得分排序。
其次是與Postings的存儲結構相關，Postings是有序且分塊存儲的。為了讓Postings實現非順序查找，Lucene為此構建了多層SkipList，且在構建的時候，為每個節點記下當前以及之前所有Block的freq和norm信息。此時，Lucene便可以啟用SkipList的優化，直接跳過低的文檔。
Postings采用了分塊存儲的方式，為了能夠快速訪問某一個塊，Lucene采用了SkipList的設計，前面的系列文章中已經講過，這里我們再來簡單回顧一下它的設計，并且結合搜索流程來探討一下它是如何幫助提升搜索性能的。
SkipList
SkipList本質上是在有序的鏈表上實現實現二分查找，它能有效的提升鏈表的查找效率，其時間復雜度為O(logn)（其中n為鏈表長度）。簡單說SkipList優化了Postings的隨機查找的性能問題。
SkipList的節點存儲了三部分數據，分別是當前節點指向Block的信息，是關于Block本身的信息；指向下層的索引；最后是存儲freq和norm的信息，它被封裝在Impact對象里面。
Impact結構僅存儲了
從.doc文件讀取出來的SkipList如下圖所示，為了方便制圖，把步長縮小為2。在第0層，每兩個Block創建一個索引節點，第1層在第0層的基本上構建，依此類推。
常規多層跳表結構，每個索引節點兩個指針，一個指向同層下一個節點，叫next指針；另一個指向下一層的down指針。在下圖中，第1層的節點4指向第0層的節點4的指針即是down指針，而從節點4直接指向節點8的叫next指針。
SkipList提升性能的思路，其實是通過在鏈表上加了多級索引獲得的，以空間換時間。層級越高，索引的步長越短，構建索引的空間代價也會越高。這也解釋了Lucene為何采用8個Block的步長，雖然查詢性能會差一些，但需要的空間也減少了n/8，這是一種存儲空間與性能的折中方案。
我們再來看一下SkipList的查找過程：以查找第7個Block為例，與最上層第二層的第1個節點比較，7 < 8；通過down指針下沉到第一層，7 > 4，通過next指針找到下一個索引節點繼續比較，7 < 8。所以回溯到節點4，然后下沉到第0層，7 > 6且7 < 8。所以回到6節點并下沉，前進一個節點之后發現7 = 7，成功找到并返回。
Lucene的SkipList僅多花費n/8的存儲空間，便將Block的隨機查詢的性能提到O(logn)的時間復雜度。PostingsEnum的advance(target)是SkipList主要應用場景，它除了應用于TOP_SCORE，還能用在多個結果集間做析取和合取運算上。
BooleanQuery
在真實的運用情景下，多個條件的復合查詢場景最為常見，Lucene使用BooleanQuery來描述一個符合查詢，如下圖所示：
其所有葉子節點都是原子查詢，它需要讀取Postings信息，但非葉子節點都通過對葉子節點的Postings進行謂詞運算獲得。簡單的BooleanQuery，是由多個原子查詢以AND，OR，NOT等操作符連接起來，再復雜一點，BooleanQuery還可以包含嵌套的BooleanQuery。
在執行查詢的時候，某些Term所關聯的Postings可能過大，此時，如果對整個Postings中所有的文檔都進行評分計算的話，代價太大。針對純AND以及純OR運算的BooleanQuery(也可能是一個嵌套的子BooleanQuery)，Lucene專門設計了如下兩種算法。
Conjunction算法
布爾運算的與運算，要求所有的查詢關鍵詞（查詢條件）共同命中候選文檔，即候選文檔同時出現了所有查詢條件的關鍵詞。也就是Postings中都出現的文檔號才是最終結果集。
實際上就是在多個集合間取交集，易知最終結果集必然是任意集合的子集。因此，基于最小的集合開始遍歷，可以避免不必須嘗試。而Lucene通過二階驗證，可以進一步減小無效嘗試。基本思想是，合并后的結果集中每個文檔必須是每個Postings都存在。
Lucene的實現比較巧妙，首先在Posting Lists中取出最短Postings命名為Lead1，接著取出次短Postings命名為Lead2，除此之外稱為Others。然后遍歷Lead1的每個文檔的過程中，每個文檔都在Lead2中做校驗。假如在Lead2中不存在，則直接退出，否則到others中校驗判斷是否存在。簡單說通過Lead1可以非常有效的減小嘗試次數，通過Lead2則能進一步減小嘗試的次數?？傮w思路就是避免到Others列表校驗文檔是否存在，流程如下。
在Others的校驗的式子如下，一旦max(...)返回NO_MORE_DOCS退出循環，合并完成。
boolean?matches?=?(DocID?==?max(pe1.advance(DocID),?pe2.advance(DocID),?pe3.advance(DocID),?...);
通過如上流程中，都是通過PostingsEnum#advance(target)方法尋找離target最近且不小于target的DocID。而advance(target)在有SkipList的情況下，可能會啟用SkipList優化。
Disjunction算法
布爾運算的或運算，要求將每個查詢條件的結果集進行并集運算。每個查詢的結果集Postings，在Lucene中都被表示為PostingsEnum。前面介紹PostingsEnum的操作advance(target)，這個方法是取Postings的文檔號不小于target的最小文檔號。所以用編程語言描述為：
DocID?=?min(pe1.advance(DocID),?pe2.advance(DocID),?pe3.advance(DocID),?...);
此過程用圖示如下，這里簡化的Lucene的運算流程。實際上就是將DocID++之后進行上面式子的運算，直至每個元素都至少會被觸達一次，也是DocID恰為NO_MORE_DOCS時表示計算完成。
每一輪都會得到一條存在當前DocID的Postings數組，然后計算查詢條件命中率，即擁有當前DocID的Postings占所有原子查詢條件的比例。當它小于某個閥值時，該DocID被以為不匹配直接丟棄。而對于滿足條件的DocID的Postings鏈表則會用于計算文檔最終評分的計算，它有兩種常用的計算策略，有SumScore和MaxScore，即是對每個子詢的文檔得分匯總并獲取所有原子查詢中的最高得分。需要簡單提一點，Disjunction在計算文檔得分時，針對TOP_SCORE模式，采用的是Weak-AND算法(一種剪枝算法)，請參考論文”Efficient Query Evaluation Using a Two-Level Retrieval Process”。
文檔結果集收集器：Collector
收集目標文檔集可以算是Search流程的最后一個步驟了，它是對候選文檔集進行過濾。這里有多種策略，比如通過該查詢的候選文檔的評分取TopK，或者按文檔的某些字段值取TopK等。此外還有一些高級用法，如Group、Facet和Stats以統計為主的聚合運算。
這里主要以文檔評分取TopK為例，介紹Collector搜索過程的主路徑中充當的角色以及職責，順帶介紹取TopK的常見方案。
Search流程中，Collector會為每一個Segment分配一個所屬的LeafCollector，用來負責這一個Segment的文檔收集任務，由它觸發Scorer對文檔進行評分，再收集文檔的得分和文檔編號。在LeafCollector在收集過程會不斷更新它的最小得分，有利于scorer更快的過濾不滿足條件的文檔。
在收集過程中，由于最終只按文檔得分來取TopK文檔，Lucene并不需要保留過程中所有的文檔，因此問題轉為化如何取TopK方案，Lucene采用經典的做法，依賴于優先隊列，它的插入的取出的復雜度均為O(logK)，而需要的內存僅為O(K)。關于PriorityQueue，我們可以詳細展開一點內容：
PriorityQueue的創建時，需要先指定期望獲得結果集的長度，然后PriorityQueue創建一個指定長度的數組。PriorityQueue在數組上構建一棵完全二叉樹，其中第0個元素留空，第1個元素作為樹的根節點。
如上圖可能看起來還不夠直觀，為此把它位置重新調整一下變成如下所示。注意，圖中的數字表示數組下標，而非是數據的值。
比較特殊的是PriorityQueue并不保證任意一個父節點的左右兩個子節點之間有序，它只保證父節點小于任意子節點。它的根節點稱為隊首，也是整棵樹中最小的節點。PriorityQueue主要包含如下幾個操作：1. 定義節點排序器。2.取隊首節點。3. 出隊。4. 入隊。
PriorityQueue的出入隊的時間復雜度為O(logK)，其中K為隊列的長度，而取隊首的時間復雜度為O(1)。
入隊可以區別為兩種方式，第一種是列隊仍不滿時，將數據放入隊列中，然后將它與父節點比較，如果小于父節點，則對換位置之后，繼續比較直至不小于父節點，入隊操作完成。 第二種是列隊已經滿時，如果入隊的數據小于父節點，入隊操作完成。否則，將隊首置換為入隊的節點，然后它不斷與它的子節點比較，直到它不大于子節點。相比之下，出隊則比較簡單，即將隊尾置換隊首，然后執行一下第二種入隊操作。
不管是出隊還是入隊，都是被更新的節點是上浮或下沉兩種操作。在下沉的過程，它還需要與兩個節點都做一次操作，選擇繼續下沉的路徑。
小結
這篇文章主要繼續上篇文章，先基于原子查詢TermQuery，介紹了文檔的匹配與評分流程，而后介紹了復合查詢BooleanQuery的合取與析取算法，文中還結合搜索流程講到了兩個重要的數據結構：SkipList與PriorityQueue。將搜索流程與索引構建流程結合，可進一步加深關于Lucene倒排索引的原理，所謂知其然也知其所以然。
Lucene倒排索引原理探秘(1)
Lucene倒排索引原理探秘(2)
Lucene索引流程與倒排索引實現
Lucene高性能索引之道
Lucene列式存儲格式DocValues詳解
Lucene 8.0關于DocValues的改進
Lucene搜索流程(上)
本文轉載自微信公眾號【Nosql漫談】。
存儲 Lucene/Solr
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
