[發(fā)明專利]一種提速的基于IPC編碼的查詢處理方法

有效

• 申請?zhí)枺?/td>: 201710035078.0
• 申請日: 2017-01-17
• 公開（公告）號: CN106909621B
• 公開（公告）日: 2020-02-11
• 發(fā)明（設(shè)計(jì)）人: 付璽;王斌;李鵬;王卿;李雄;徐杰;馬宏遠(yuǎn)
• 申請（專利權(quán)）人: 中國科學(xué)院信息工程研究所
• 主分類號: G06F16/24
• 分類號: G06F16/24;G06F16/22
• 代理公司: 11200 北京君尚知識產(chǎn)權(quán)代理有限公司
• 代理人: 邱曉鋒

本發(fā)明涉及一種提速的基于IPC編碼的查詢處理方法。該方法把IPC編碼下的索引文件視為樹形的跳表文件，實(shí)現(xiàn)快讀略過子樹的算法；在處理布爾的求交查詢時，根據(jù)鏈表的單調(diào)性判斷是否略過(skip)某些子樹，略過(skip)操作可節(jié)省大量時間從而提高線上布爾查詢處理速度；在處理排序查詢時，使用常見的TAAT處理方式與continue機(jī)制，根據(jù)ID列表的求交結(jié)果的位置可以快速取出對應(yīng)的頻率的索引文件的對應(yīng)的值，通過略過所有不必要訪問的子樹的手段提高線上排序查詢的處理速度。本發(fā)明根據(jù)IPC編碼的特點(diǎn)優(yōu)化了查詢速度(包括布爾查詢與排序查詢)，優(yōu)化了檢索系統(tǒng)的用戶體驗(yàn)。

技術(shù)領(lǐng)域

本發(fā)明屬于信息技術(shù)領(lǐng)域，具體涉及一種提速的基于IPC編碼的查詢處理方法。

背景技術(shù)

目前的檢索系統(tǒng)里大多采用倒排索引作為處理用戶查詢的數(shù)據(jù)結(jié)構(gòu)。倒排索引文件(IF)通常比較大，一般不能完整地放入內(nèi)存，因此實(shí)際在應(yīng)用時對索引文件都要進(jìn)行按照某種編碼進(jìn)行壓縮。一般來說，壓縮率越高的編碼在線上進(jìn)行查詢處理時會更加慢一些，因此所有的編碼都是在空間跟處理時間上找平衡點(diǎn)。

在編碼ID的索引文件時有兩種基本的策略，一種是編碼原始的遞增的值，另一種是編碼連續(xù)兩個遞增的值之間的差值(delta編碼)。一般來說差值遠(yuǎn)遠(yuǎn)小于原值，因此編碼差值可能會帶來一些壓縮率的提高。但某些原值編碼中也有非常高效的編碼。

當(dāng)前在產(chǎn)業(yè)界用的比較多的是PFD編碼(Marcin Zukowski,Sandor Heman,NielsNes and Peter Boncz.Superscalar RAM-CPU cache compression.In Proceedings ofthe 22nd International Conference on Data Engineering(ICDE),no.59,pages 1-12.IEEE,2006.)，PFD編碼屬于delta編碼，它利用了ID的差值的分布特征，將90％較小的delta值根據(jù)最大字長位對齊順序地存儲，而把10％的較大值作為特例單獨(dú)用變長編碼存儲。PFD編碼的壓縮率跟解壓速度都可以讓人接受，實(shí)現(xiàn)簡單，因此在工業(yè)上得到廣泛應(yīng)用。它的缺點(diǎn)是它建立在差值的分布特性的假設(shè)的前提下，在不滿足這個假設(shè)的時候它的壓縮率不算太高。

IPC編碼是一種在原值上的編碼(Alistair Moat and Lang Stuiver.Binaryinterpolative coding for effective index compression.Information Retrieval,vol.3,no.1,pages 25-47,2000.)，它需要編碼在遞增的原值上。具體做法是對某個列表或者子列表先編碼其中值，并根據(jù)最大與最小乃至區(qū)間長度來判斷中值的取值區(qū)間，根據(jù)此區(qū)間來決定編碼該值占幾個存儲字長。在確定了中值后，原區(qū)間被平分為兩個子區(qū)間，在子區(qū)間上的遞歸地進(jìn)行這樣編碼中值的操作，直至子區(qū)間的長度為0。

IPC的編碼是一個樹形結(jié)構(gòu)，通過這種遞歸地減小區(qū)間的方法，最后能以很小的長度編碼各值，這也是它壓縮率非常高的原因。但是同樣可以看到在編碼時它需要更多的計(jì)算，例如計(jì)算上下限等等，而它的解碼需要復(fù)原這個過程，因此速度是比較慢的，在布爾與排序查詢中IPC編碼的速度大約是PFD編碼速度的1/4與1/3。

此外還存在其他的編碼，但在所有的主流編碼中，IPC編碼的壓縮率是最高的，也是線上處理速度偏慢的一種。

IPC編碼因?yàn)槠涓邏嚎s率會被用在某些有著嚴(yán)格存儲空間限制的應(yīng)用場景內(nèi)，例如超大規(guī)模數(shù)據(jù)量的檢索系統(tǒng)或者嵌入式系統(tǒng)等等。但I(xiàn)PC編碼最大的缺點(diǎn)在于解壓速度較慢，由此導(dǎo)致在線上處理的速度也偏慢。例如常見的OPTPFD編碼的一個rank查詢的處理時間大約為IPC編碼的1/3。雖然IPC編碼擁有不錯的壓縮率，但是線上的查詢處理時間會增大使用用戶的等待時間，因此限制了它的進(jìn)一步應(yīng)用。

發(fā)明內(nèi)容