Lucene架構下布爾查詢的執(zhí)行計劃研究

趙 廣

(武漢體育學院 體育工程與信息技術學院，湖北 武漢 430079)

Lucene[1]是apache軟件基金會jakarta項目組的一個子項目，是一個開放源代碼的全文檢索引擎工具包，提供了完整的查詢引擎和索引引擎.Lucene分別通過索引器和檢索器來實現(xiàn)2大核心功能，即創(chuàng)建索引和檢索索引.創(chuàng)建索引是使用分詞器對源數(shù)據(jù)進行處理，把關鍵詞提取出來，利用倒排索引技術和增量索引方式生成索引庫的過程；檢索是對索引庫的逆操作，用戶的檢索請求，通過分詞器分詞，生成檢索關鍵詞，與索引庫中的詞典進行比對，取出命中詞的倒排表，進行打分、合并與排序，將結果返回給用戶[2].

在全文檢索應用中，布爾查詢憑借精確和高效的特性被廣泛采用，如百度、谷歌、中國知網(wǎng).布爾查詢語句往往同時混合了多種布爾操作，如AND、NOT、OR，其表達式相對繁瑣，對大多數(shù)用戶來說，理解并靈活應用布爾表達式來精確定義檢索請求是很不容易的.因此，深入研究布爾查詢的執(zhí)行邏輯，對于靈活應用布爾查詢邏輯，并實現(xiàn)檢索功能的優(yōu)化具有十分重要的意義.

布爾查詢也是Lucene檢索功能的主要實現(xiàn)方式，學者對其執(zhí)行計劃的研究極少.文獻[3]研究了在Lucene環(huán)境中，復雜布爾查詢文檔搜集和打分策略的優(yōu)化方法，并設計了一種性能回歸預測機制；文獻[4]研究數(shù)據(jù)集成中的布爾查詢的改寫問題,給出了兩種改寫處理的方法，并證明了方法的可靠性；文獻[5]通過實驗深入研究了SQL的執(zhí)行計劃.這些文獻，雖然不是對布爾查詢執(zhí)行計劃的直接研究，但具有極強的借鑒意義.本文利用這些方法或思路，在Lucene架構下，首先深入研究布爾查詢的執(zhí)行計劃，包括表示方式、查詢解析、執(zhí)行時序，運算規(guī)則等，然后對布爾查詢進行剖析，提出布爾查詢表達式構建的優(yōu)化規(guī)律和交換律，并通過實驗模擬進行驗證.

1 布爾查詢

在全文檢索應用中，布爾查詢，是指在查詢詞項上通過布爾操作符(與非或)構建出查詢表達式，從而表達用戶希望文檔所具有的特征[6].在Lucene框架下，無論是一框式搜索，還是高級查詢器，都可以轉化為布爾查詢.布爾查詢也可以多層嵌套，一個布爾查詢可以作為另一個布爾查詢的子句，具有嵌套關系的布爾查詢稱為復雜布爾查詢.

1.1 布爾查詢的表示

絕大部分的應用中，布爾查詢語法都是使用AND、NOT、OR和括號來連接查詢關鍵詞，如：(xORy)AND (uORz),其中x,y,u,z為查詢關鍵詞.在Lucene中，布爾查詢采用了全新的表示方式，假設有以下查詢項：a,b,c,d,e,f，需要檢索滿足條件的文檔表示如下：

Q=(+a-(+c-d)-b+(ef)).

(1)

則Q是一個典型的布爾查詢，其中a,b,c,d,e,f可以是原子查詢，也可以是查詢子句.子查詢的布爾關系有3種，如表1所示，假設a為一個Term.

表1 布爾關系表

1.2 執(zhí)行計劃分析

執(zhí)行計劃即為布爾查詢在檢索過程中的執(zhí)行方案.在Lucene中，即為根據(jù)布爾查詢語句從索引庫中讀出倒排表、合并倒排表，得到結果文檔集并對文檔打分的過程.Lucene的布爾查詢執(zhí)行的過程復雜而又高效.

1.2.1 布爾查詢執(zhí)行的時序圖

索引器是Lucene實現(xiàn)檢索功能的組件，對于輸入的布爾查詢語句，將轉換為Query對象樹，檢索執(zhí)行的時序如圖1所示.

通過分析Lucene文檔及跟蹤源代碼可得：Weight對象樹，用于計算詞的權重；構造Scorer對象樹，用于計算檢索詞的打分；在構造Scorer對象樹的過程中，其葉子節(jié)點會將詞典和倒排表從索引中讀出來；倒排表合并及打分由SumScorer對象樹來實現(xiàn)，此步將倒排表合并后得到結果文檔集，并計算最終得分，將收集的結果集及分值返回給用戶.倒排表的合并及打分，需要讀取文檔對象，因此需要IO操作，這個過程是查詢主要耗時點.Lucene中采用迭代器來實現(xiàn)結果集的收集，而不是一次性全部讀入.對結果集的大小取舍，直接決定著查詢效率.

1.2.2 布爾查詢的解析

從時序圖可以看出，對于一個布爾查詢的解析并生成Query對象樹是執(zhí)行計劃的第一步.對于式(1)表示的查詢，可以解析為如圖2所示的查詢樹.每一個子樹被稱為一個子查詢.

Query對象樹的每一個葉子節(jié)點為一個查詢Term，也稱為原子查詢，該Term直接在索引詞典中進行匹配運算，從而獲取含有該Term的文檔倒排列表.各個子查詢的結果合并即為倒排表合并，對于Query對象樹，Lucene采取先合并子樹，然后子樹與子樹再進行合并，直到根，這個過程如圖3所示.

1.2.3 布爾子查詢的運算規(guī)則

Query對象樹子查詢的合并是典型的邏輯運算，但是它又有別于與或非的運算規(guī)則.對于查詢樹同級子查詢的合并運算規(guī)則如表2所示.

子查詢的合并運算，本質上就是倒排表的歸并運算，歸納起來，主要有3種，即交集運算、并集運算、和差集運算.對于3種集合運算，Lucene均采用多路歸并運算[7].多路歸并運算就是多條子查詢的倒排表同時參與歸并運算，以交集運算為例：

假定Q=(+x+y+z)，x,y,z為子查詢，Lucene采用基于跳表的多路快速合并算法，圖4為合并流程示意圖，初始狀態(tài)的倒排鏈表如圖4第1部分所示.首先將x、y、z鏈表按長度排序，從最短鏈表y第一個元素開始，然后在鏈表z中查找，如圖4中第2部分；當在z中找到相同的元素，再開始在x中查找，找到了相同的元素，則該元素命中，如圖4第3部分；如此進行，直到鏈表y結束.

表2 布爾運算規(guī)則表

Lucene中，對于3種子句的混合布爾運算按先MUST子句結合，再MUST_NOT，最后SHOULD的優(yōu)先級進行多路歸并運算.因此，對于一個查詢Q，含有多個子查詢，表示如下：

Q=(+a-bc+d+e),其中a，b，c，d，e為子查詢；

根據(jù)表2運算規(guī)則和優(yōu)先級規(guī)則，Q的合并運算過程如下：

Q=(((+a+d+e)-b)c)；

Q=((+Q1 -b)c)，其中Q1=(+a+d+e);

Q=(+Q2c)，其中Q2=(+Q1 -b)；

2 布爾查詢執(zhí)行計劃的剖析

布爾查詢執(zhí)行計劃直接決定著Lucene檢索的性能，對該執(zhí)行計劃的深入研究有利于尋找檢索性能優(yōu)化的途徑.本文從2個方面進行剖析，并提出可能的優(yōu)化策略.

2.1 布爾查詢表達式的優(yōu)化

假定一個布爾查詢Q1=(+a+b+(+c+d-e)-f),其中a,b,c,d,e,f為子查詢，其對應的查詢樹如圖5所示.這是一顆深度為2的查詢樹，根據(jù)Lucene布爾執(zhí)行計劃，先合并子樹，再合并上一級子樹，直到根節(jié)點，同一級的子查詢按優(yōu)先級進行多路合并.從執(zhí)行邏輯上，圖5查詢樹需要執(zhí)行4次多路歸并運算，并產(chǎn)生3個中間結果；而如果將Q1化簡為圖6所示的Q2查詢樹，則只需要執(zhí)行2次多路歸并運算，只產(chǎn)生1個中間結果.從理論上來看，查詢的效率和空間復雜度將會大大改善.

問題：Q1和Q2表示的布爾查詢是否等價？答案是肯定的，證明如下：

令A、B、C、D、E、F分別對應子查詢a、b、c、d、e、f子查詢的結果集，則：

Q1=A∩B∩(C∩D-E)-F

=A∩B∩(C∩D∩)-F

=A∩B∩C∩D∩-F

=A∩B∩C∩D-E-F

Q2=A∩B∩C∩D-E-F;

因此，Q1=Q2，證畢.

筆者對中國知網(wǎng)、百度、谷歌等全文檢索系統(tǒng)的檢索接口研究發(fā)現(xiàn)，用戶檢索需求解析為Query查詢樹時，深度均為2，因此深入研究用戶查詢需求布爾表達式，將表達式或部分表達式化簡，減少查詢多路歸并的次數(shù)和中間結果的個數(shù)，具有提高查詢效率的意義.本文根據(jù)集合運算規(guī)則，深入研究了各種深度為2的布爾表達式，表3列出了具有規(guī)律且能夠化而簡之的類型，限于篇幅證明省略.

表3 布爾表達式化簡規(guī)律表

2.2 交換律

從布爾子查詢運算規(guī)則和歸并運算規(guī)則來看，用戶查詢請求中生成的布爾運算順序，不是最終的運算順序，Lucene會根據(jù)子查詢的類型和運算的需要進行二次組合和排序.因此，從用戶的角度，構造查詢請求布爾表達式時，同一層子樹，子查詢滿足交換律，例如：

Q1=(+a+b)=(+b+a);

Q2=(+abc)=(c+ab)=(bc+a);

與SQL語句執(zhí)行計劃不同，不需要刻意考慮將查詢結果少的子查詢放在最左邊.

3 實驗仿真

為了進一步分析布爾查詢的合并運算規(guī)則和執(zhí)行效率，驗證布爾查詢表達式優(yōu)化策略和交換律，本文構建實驗環(huán)境，模擬各種優(yōu)化方案，比較查詢結果和執(zhí)行效率.Lucene版本為4.10.3，分詞器為IKAnalyzer02012_u6，采用14萬條商品訂單記錄構建索引庫，每條記錄含有編號、商品名、類型、地址、收貨人、價格字段，分別映射到Document對象中number、name、type、address、user、price域.所有實驗數(shù)據(jù)均在計算機負載穩(wěn)定條件下，3次執(zhí)行取平均值.實驗中選取五個查詢關鍵詞：

a=name:”男”，b=type:”會場”，

c=name:”棉”，d=type:”內(nèi)衣”，

e=name:”正版”.

所有的查詢實驗，均基于以上5個關鍵詞的組合而得.

3.1 布爾查詢表達式優(yōu)化仿真

針對表3所列的兩大類型5條優(yōu)化規(guī)律，分別構建布爾表達式進行檢索，查詢結果個數(shù)、時間耗費、排序情況記錄如表4所示.

表4 化簡規(guī)律實驗數(shù)據(jù)表

從表4的實驗數(shù)據(jù)看出，表3所列的布爾表達式優(yōu)化規(guī)律是正確的，優(yōu)化所帶來的執(zhí)行效率均有提高.由于實驗數(shù)據(jù)量較小，訂單記錄轉換的文檔也非常小，查詢表達式相對簡單，機器負載比較低，執(zhí)行效率的改善不明顯.隨著數(shù)據(jù)量的增加、查詢負載的加大，優(yōu)化的查詢執(zhí)行效率必然會有很大的提高.

3.2 布爾運算規(guī)則的交換律仿真

根據(jù)表2所列的布爾運算基本規(guī)則，對于每一條規(guī)則，進行交換子查詢位置檢索實驗，查詢結果總數(shù)、運行時間數(shù)據(jù)如表5所示.

表5 交換律實驗數(shù)據(jù)表

從表5的實驗數(shù)據(jù)很容易看出，Lucene布爾查詢表達式同一級的查詢子句滿足交換律，打分與排序結果不受子句的順序影響，查詢耗時基本相同.由此說明從應用層面，控制查詢子句的順序，不會帶來查詢效率的提升.

4 總結

本文深入研究了Lucene框架下布爾查詢的執(zhí)行計劃，涉及布爾查詢的表示方式、子句類型、執(zhí)行過程、運算規(guī)則和子查詢多路合并算法.根據(jù)布爾查詢的邏輯過程，一方面剖析了復雜布爾表達式的化簡規(guī)律，并選定一個類型進行了證明；另一方面，提出了布爾運算規(guī)則滿足交換律的特性.通過理論分析和模擬實驗驗證，復雜布爾表達式的化簡規(guī)律和布爾運算的交換律是正確的，并且，對復雜布爾運算的化簡，有效地提高了檢索效率.