張延松 ，蘇明川 ，張 宇 ，王方舟

1.中國人民大學(xué) 信息學(xué)院，北京 100872

2.中國人民大學(xué) 中國調(diào)查與數(shù)據(jù)中心，北京 100872

1 引言

隨著多核處理器和大內(nèi)存計(jì)算機(jī)平臺(tái)的普及，內(nèi)存正在取代磁盤成為新的高性能計(jì)算存儲(chǔ)設(shè)備。內(nèi)存數(shù)據(jù)庫MonetDB[1]以內(nèi)存列存儲(chǔ)和cache優(yōu)化的列代數(shù)優(yōu)化技術(shù)成為內(nèi)存分析型數(shù)據(jù)庫的代表技術(shù)，其產(chǎn)品VectorWise[2-3]也成為高性能內(nèi)存分析處理技術(shù)的代表產(chǎn)品，并在TPC-H[4]測(cè)試中獲得集中式處理的最高性能。SAP HANA[5]以高性能內(nèi)存分析處理技術(shù)迅速獲得了市場(chǎng)認(rèn)可，占據(jù)了實(shí)時(shí)分析處理的高端市場(chǎng)。傳統(tǒng)的數(shù)據(jù)庫廠商，如Oracle也推出了基于內(nèi)存處理的ExaData X3[6]數(shù)據(jù)庫一體機(jī)，以大容量的PCI-e閃存卡作為大容量高性能存儲(chǔ)，消除磁盤I/O。

內(nèi)存數(shù)據(jù)庫已成為重要的實(shí)時(shí)分析處理平臺(tái)，相對(duì)于當(dāng)前主流的多核處理器和協(xié)處理器，內(nèi)存仍然是一種訪問延遲較高的存儲(chǔ)設(shè)備，同時(shí)，內(nèi)存訪問帶寬也是內(nèi)存數(shù)據(jù)庫的性能瓶頸之一，需要內(nèi)存數(shù)據(jù)庫中高效的索引機(jī)制來提高數(shù)據(jù)訪問效率和充分利用內(nèi)存帶寬。

連接索引[7-8]是數(shù)據(jù)倉庫中一種有效的提高表間連接效率的索引技術(shù)，它將表之間的連接關(guān)系（[rowid：rowid]）記錄下來，可以對(duì)連接表按連接索引中的記錄物理地址直接訪問。Oracle進(jìn)一步實(shí)現(xiàn)了位圖連接索引[9]，為指定連接表上的列成員建立連接索引，用位圖指示當(dāng)前列成員在連接表上的位置，從而用高效的位圖索引掃描來代替大數(shù)據(jù)表上代價(jià)巨大的順序掃描。在行存儲(chǔ)磁盤數(shù)據(jù)庫中，位圖連接索引的存儲(chǔ)空間開銷和位圖處理開銷都很小，而在列存儲(chǔ)內(nèi)存數(shù)據(jù)庫中，多個(gè)維表屬性上的位圖連接索引需要較大的內(nèi)存存儲(chǔ)開銷，而且索引運(yùn)算的代價(jià)不容忽視，內(nèi)存位圖運(yùn)算的CPU代價(jià)較大，位圖連接索引的整體效率受到較大影響。

雖然位圖連接索引在提高表掃描效率和降低多表連接代價(jià)方面具有重要的作用，但磁盤數(shù)據(jù)庫中的位圖連接索引直接應(yīng)用于內(nèi)存數(shù)據(jù)庫會(huì)產(chǎn)生較大的索引存儲(chǔ)開銷和位圖計(jì)算開銷，降低索引的綜合性能。同時(shí)，位圖連接索引是為查詢中頻繁訪問屬性中的每一個(gè)成員建立一個(gè)連接位圖，通常優(yōu)先為低勢(shì)集的頻繁訪問屬性建立位圖連接索引以降低索引存儲(chǔ)開銷。但低勢(shì)集屬性連接位圖的選擇率較低，索引訪問效率降低；而高勢(shì)集屬性成員低選擇率的連接位圖雖然提高了索引訪問效率，但索引的存儲(chǔ)開銷消耗了大量寶貴的內(nèi)存資源。另一方面，數(shù)據(jù)倉庫多維數(shù)據(jù)模型的特點(diǎn)使數(shù)據(jù)庫中存在大量不同屬性上的位圖連接索引，復(fù)雜查詢往往涉及到多個(gè)索引之間的位圖操作，增加了查詢優(yōu)化的復(fù)雜度。值得注意的是，頻繁屬性中存在大量非頻繁訪問成員而非頻繁屬性中也存在著部分頻繁訪問成員，而當(dāng)前以屬性為粒度的位圖連接索引機(jī)制無法在內(nèi)存容量約束的前提下更好地發(fā)揮位圖連接索引的效率。

同時(shí)，隨著多核處理器和協(xié)處理器的發(fā)展，索引的性能不僅僅取決于存儲(chǔ)器的性能和存儲(chǔ)訪問模型，還取決于計(jì)算平臺(tái)的并行計(jì)算模型。例如位圖連接索引中經(jīng)常執(zhí)行多個(gè)位圖之間的位圖AND操作，對(duì)于多核CPU而言，位圖訪問和位運(yùn)算需要較高的CPU cycle，而對(duì)于協(xié)處理器（如GPU）而言，位運(yùn)算的效率極高。索引的性能不僅要考慮cache-conscious的存儲(chǔ)訪問算法，而更應(yīng)該考慮processor-conscious的索引運(yùn)算技術(shù)。索引管理需要決定什么時(shí)候，為誰，在什么地方，創(chuàng)建什么樣的索引，索引的計(jì)算采用什么方式，索引計(jì)算的場(chǎng)地在哪里，索引計(jì)算的結(jié)果如何傳遞給下一級(jí)操作符，索引的更新如何觸發(fā)，在處理器緩存-內(nèi)存-磁盤多級(jí)存儲(chǔ)結(jié)構(gòu)中索引如何從同構(gòu)的存儲(chǔ)模型擴(kuò)展為異構(gòu)存儲(chǔ)模型等問題。索引管理本身已是一個(gè)獨(dú)立的系統(tǒng)級(jí)優(yōu)化問題，而且位圖連接索引具有與數(shù)據(jù)庫系統(tǒng)相獨(dú)立的輸入（SQL命令參數(shù)）和輸出（位圖），因此將索引從數(shù)據(jù)庫內(nèi)置的數(shù)據(jù)結(jié)構(gòu)抽取到數(shù)據(jù)庫外層作為松耦合的索引服務(wù)能夠降低數(shù)據(jù)庫優(yōu)化器的負(fù)擔(dān)并更加獨(dú)立地面向新的硬件平臺(tái)（如協(xié)處理器）或存儲(chǔ)技術(shù)（如內(nèi)存云技術(shù)）而優(yōu)化。

本文所提出的位圖連接索引服務(wù)機(jī)制是在傳統(tǒng)的位圖連接索引的基礎(chǔ)上設(shè)計(jì)獨(dú)立于數(shù)據(jù)庫的索引服務(wù)層，根據(jù)多維數(shù)據(jù)集的特性以關(guān)鍵字為粒度為數(shù)據(jù)庫建立統(tǒng)一的位圖連接索引，通過查詢?nèi)罩旧系慕y(tǒng)計(jì)或數(shù)據(jù)挖掘方法按內(nèi)存空間約束建立基于關(guān)鍵字的TOPK位圖連接索引，在不同的索引更新窗口內(nèi)根據(jù)關(guān)鍵字加權(quán)頻度更新TOPK連接位圖，以保證位圖連接索引在給定內(nèi)存存儲(chǔ)空間中的使用效率最大化。在索引運(yùn)算性能方面，通過多核處理器并行位圖索引計(jì)算，GPU并行位圖索引計(jì)算以及內(nèi)存云位圖索引計(jì)算等不同的計(jì)算平臺(tái)靈活地為位圖連接索引提供更高性能的支持。本文的主要貢獻(xiàn)體現(xiàn)在三個(gè)方面：

（1）松耦合的自管理位圖連接索引

位圖連接索引的管理不再是由數(shù)據(jù)庫管理員根據(jù)經(jīng)驗(yàn)進(jìn)行管理，而是通過查詢負(fù)載監(jiān)視和分析模塊通過特定的策略提供自適應(yīng)的索引管理機(jī)制。

（2）基于關(guān)鍵字的TOPK位圖連接索引機(jī)制

內(nèi)存數(shù)據(jù)庫要求索引具有更高的內(nèi)存空間敏感性，提出了基于關(guān)鍵字的TOPK位圖連接索引來實(shí)現(xiàn)指定內(nèi)存索引空間配額下的細(xì)粒度索引管理。

（3）處理器敏感的位圖連接索引技術(shù)

內(nèi)存大數(shù)據(jù)集上的位圖連接索引涉及很多超長（數(shù)億位）位圖之間的位操作，位圖索引運(yùn)算同樣成為內(nèi)存數(shù)據(jù)庫的性能約束。通過引入多核處理器平臺(tái)、眾核協(xié)處理器平臺(tái)以及內(nèi)存云平臺(tái)使位圖運(yùn)算性能通過處理器平臺(tái)的支持而提升。

2 相關(guān)工作

分析型數(shù)據(jù)庫通常采用多維存儲(chǔ)模型，即典型的星形模型或雪花形模型。數(shù)量眾多但數(shù)據(jù)量較小的維表和位于模式中心的大事實(shí)表構(gòu)成一個(gè)多維數(shù)據(jù)模型：事實(shí)表通過外鍵與維表連接，通過維表上屬性定義的層次來描繪多維數(shù)據(jù)空間上的多維數(shù)據(jù)分析處理任務(wù)。多維查詢中的謂詞主要用于維表上層次的選擇，而查詢處理的代價(jià)主要集中于大事實(shí)表與數(shù)量眾多維表之間的連接操作，因此索引的主要作用不是加速較小維表上的檢索性能，而是要加速維表與事實(shí)表之間的連接操作性能。

連接索引[10]是一種面向連接關(guān)系的索引結(jié)構(gòu)，它通過預(yù)連接將連接表中相應(yīng)記錄對(duì)應(yīng)的地址記錄在索引中，當(dāng)再次執(zhí)行表連接操作時(shí)，可以根據(jù)連接索引中的地址對(duì)直接訪問兩個(gè)表中具有連接關(guān)系的數(shù)據(jù)，可以看作是物化視圖的一種索引表示方法。Oracle的位圖連接索引（Bitmap join index）通過位圖方式為維表中與事實(shí)表連接的字段成員建立連接映射位圖，維成員通過與事實(shí)表等長的位圖記錄了其與事實(shí)表連接的位置關(guān)系，查詢可以通過匹配的位圖索引直接獲得事實(shí)表的位置關(guān)系，并通過位圖與rowid的轉(zhuǎn)換獲得事實(shí)表連接匹配記錄的物理地址，實(shí)現(xiàn)在事實(shí)表上的直接訪問，消除連接代價(jià)并減少大事實(shí)表掃描代價(jià)。位圖連接索引可以建立在多個(gè)維表和多個(gè)維屬性上，提供靈活高效的連接優(yōu)化技術(shù)。位圖連接索引提供了性能和靈活性兩方面的支持：多表之間的復(fù)雜連接操作可以通過抽取出謂詞對(duì)應(yīng)的列成員位圖直接獲得在較大的連接表上的連接位置，將I/O代價(jià)巨大的大表掃描轉(zhuǎn)換為高效率的按位置訪問，極大降低了連接操作中的大表掃描代價(jià)；連接索引的輸出是標(biāo)準(zhǔn)的位圖，從而為用戶自定義索引提供了底層支持。內(nèi)存列存儲(chǔ)數(shù)據(jù)庫通常采用內(nèi)存數(shù)組數(shù)據(jù)結(jié)構(gòu)，位圖可以直接映射為列的物理地址，從而使位圖連接索引中的位圖能夠與列建立直接地址映射關(guān)系，提高索引訪問性能。MonetDB的列代數(shù)在執(zhí)行列連接時(shí)生成物化的列間連接索引，記錄兩個(gè)列之間連接記錄的OID地址關(guān)系，多列連接操作轉(zhuǎn)換為連接索引之間的連接關(guān)系。Invisible-join[11]將列間連接索引進(jìn)一步優(yōu)化存儲(chǔ)為位圖，列間連接索引的連接操作轉(zhuǎn)換為多個(gè)位圖之間的位操作，從而用更加適合現(xiàn)代處理器SIMD計(jì)算模式的位圖操作替代星形連接操作。

由于多維分析查詢主要是基于多維數(shù)據(jù)立方體的維層次進(jìn)行的上卷、下鉆、切片和切塊等操作，維表上的層次屬性是多維分析查詢中高頻訪問的字段，因此這些維屬性列上的連接索引能夠極大地優(yōu)化星形連接代價(jià)。但是位圖連接索引是以屬性列為單位創(chuàng)建，默認(rèn)地為屬性中所有成員建立連接位圖，要求創(chuàng)建位圖連接索引的屬性是低勢(shì)集列，即成員數(shù)量相對(duì)較少。

位圖連接索引成為數(shù)據(jù)倉庫星形模型或雪花狀模型上一種簡單而高效的索引技術(shù)，但位圖連接索引的存儲(chǔ)和更新代價(jià)較大，選擇和創(chuàng)建索引成為位圖連接索引的一個(gè)關(guān)鍵技術(shù)問題。文獻(xiàn)[12-13]首先通過數(shù)據(jù)挖掘技術(shù)對(duì)索引候選空間進(jìn)行剪枝，降低候選索引的優(yōu)化空間，然后采用貪心算法選擇出能夠滿足空間約束的執(zhí)行代價(jià)最低的候選索引屬性。文獻(xiàn)[14]采用更加精確的頻繁項(xiàng)集數(shù)據(jù)挖掘技術(shù)從給定負(fù)載中確定候選索引屬性集，通過建立代價(jià)模型評(píng)估索引創(chuàng)建的代價(jià)與性能收益。文獻(xiàn)[15]采用最大頻繁項(xiàng)集數(shù)據(jù)挖掘技術(shù)進(jìn)行索引候選屬性剪枝，并在訪問頻率基礎(chǔ)上擴(kuò)展了更多的參數(shù)以提高索引候選屬性選擇的準(zhǔn)確性。

數(shù)據(jù)倉庫應(yīng)用中事實(shí)表數(shù)據(jù)量非常大，分析型內(nèi)存數(shù)據(jù)庫應(yīng)用中需要盡可能地提高昂貴內(nèi)存的利用率，最小化索引等輔助數(shù)據(jù)的內(nèi)存空間開銷。查詢中涉及的維成員往往較為分散，為多個(gè)維屬性列創(chuàng)建位圖連接索引將產(chǎn)生巨大的索引存儲(chǔ)開銷，而且維屬性列成員中只有部分成員屬于頻繁訪問成員，以維屬性列為對(duì)象的位圖連接索引創(chuàng)建方法在索引空間消耗和效率方面還存在著較大的問題，傳統(tǒng)的以屬性為粒度的索引管理機(jī)制難以滿足內(nèi)存數(shù)據(jù)庫存儲(chǔ)空間精細(xì)化管理的需求。

相對(duì)于磁盤數(shù)據(jù)庫，內(nèi)存數(shù)據(jù)庫索引的CPU運(yùn)算代價(jià)占比較高，因此提高索引運(yùn)算性能是提高索引可用性的保證。相對(duì)于當(dāng)前較少核數(shù)的多核處理器，GPU擁有更高的內(nèi)存位寬與帶寬，其相對(duì)較小的高帶寬顯存（最大6 GB），難以存儲(chǔ)大量的原始數(shù)據(jù)但適合存儲(chǔ)較小的索引數(shù)據(jù)。GDB[16]提出了GPU與CPU混合平臺(tái)上的關(guān)系操作實(shí)現(xiàn)技術(shù)，GPU上的關(guān)系操作性能必須通過并行處理性能和數(shù)據(jù)在內(nèi)存和GPU之間的傳輸代價(jià)綜合計(jì)算。文獻(xiàn)[17]測(cè)試了多種內(nèi)存與GPU之間的傳輸技術(shù)，提出了小表駐留GPU內(nèi)存的外鍵連接技術(shù)，但大表連接屬性的數(shù)據(jù)傳輸延遲仍然是GPU關(guān)系操作的重要性能瓶頸。當(dāng)前GPU上的優(yōu)化技術(shù)主要集中在關(guān)系操作的實(shí)現(xiàn)技術(shù)上，尤其以星形連接操作為優(yōu)化的核心問題，但對(duì)多維模型上最重要的位圖連接索引方面的研究相對(duì)較少。位圖連接索引計(jì)算簡單，輸出數(shù)據(jù)為單一位圖，GPU有限的內(nèi)存和強(qiáng)大的并行處理能力使其成為位圖連接索引管理和運(yùn)算的最佳平臺(tái)。

3 基于關(guān)鍵字的TOP K位圖連接索引

3.1 系統(tǒng)架構(gòu)

圖1所示的基于關(guān)鍵字的TOPK位圖連接索引查詢處理技術(shù)將整個(gè)查詢處理過程分為兩個(gè)階段：索引處理和基于位圖過濾的查詢處理。索引處理是根據(jù)用戶查詢輸入的SQL命令獨(dú)立進(jìn)行索引計(jì)算，如：

框圖中where表達(dá)式中的c_region和AMERICAN合起來是一個(gè)查詢關(guān)鍵字，表示在維表customer的c_region字段中值為AMERICAN的成員與事實(shí)表具有連接關(guān)系。同理，多個(gè)謂詞表達(dá)式分別表示不同維表上不同字段中的成員與事實(shí)表具有的連接關(guān)系。完成此查詢最直接最高效的方法是在查詢負(fù)載中找到使用頻率最高的查詢關(guān)鍵字并為這些關(guān)鍵字建立位圖連接索引，通過對(duì)用戶輸入的查詢命令的解析，以關(guān)鍵字為單位檢索是否存在對(duì)應(yīng)的連接位圖，然后在選定的位圖上執(zhí)行位AND運(yùn)算，生成具有全局連接作用的過濾位圖來過濾事實(shí)表，并根據(jù)位圖連接索引來剪裁SQL命令中不再需要的連接操作，減少參與實(shí)際連接操作的記錄數(shù)量。索引處理階段是一個(gè)獨(dú)立的過程，可以將該索引機(jī)制作為獨(dú)立的功能模塊附加在數(shù)據(jù)庫之外作為獨(dú)立的索引服務(wù)層，如圖1中虛線框部分可以作為獨(dú)立于數(shù)據(jù)庫之外的索引服務(wù)。在基于位圖過濾的查詢處理階段，索引生成的過濾位圖用于在事實(shí)表上進(jìn)行連接記錄篩選，并且根據(jù)使用的索引位圖將用戶原始輸入的查詢Q優(yōu)化為查詢Q'。在Q'中，如果謂詞關(guān)鍵字存在連接位圖并且對(duì)應(yīng)維表屬性沒有出現(xiàn)在分組屬性中，如s_region=’AMERICAN’AND（p_mfgr=’MFGR#1’OR p_mfgr=’MFGR#2’）謂詞關(guān)鍵字存在連接位圖，則索引所生成的過濾位圖隱含了事實(shí)表與維表supplier和part的連接關(guān)系，查詢Q'中可以將lineorder與supplier表和part表的連接操作進(jìn)行剪枝，在縮減事實(shí)表掃描代價(jià)的基礎(chǔ)上將表連接的數(shù)量減少到兩個(gè)。優(yōu)化后的查詢Q'如下所示：

查詢優(yōu)化器設(shè)計(jì)的難點(diǎn)在于集成了新的索引結(jié)構(gòu)后的代價(jià)模型，而在本文中位圖操作的代價(jià)已知，過濾位圖上的選擇率為精確值，數(shù)據(jù)庫系統(tǒng)在原有的代價(jià)優(yōu)化模型基礎(chǔ)上只要簡單增加基于位圖的掃描優(yōu)化即可集成本文的索引技術(shù)。

傳統(tǒng)的基于屬性而創(chuàng)建的位圖連接索引在面臨存儲(chǔ)空間約束時(shí)難以有效解決頻繁訪問屬性中非頻繁訪問屬性成員索引利用率低的問題和高勢(shì)集或非頻繁訪問屬性中頻繁訪問成員的索引難以創(chuàng)建問題；在面臨計(jì)算代價(jià)估算時(shí)難以評(píng)估新的存儲(chǔ)或處理技術(shù)對(duì)局部性能優(yōu)化所產(chǎn)生的收益，如引入SSD存儲(chǔ)或GPU等新型硬件存儲(chǔ)和加速位圖索引計(jì)算性能。

本文所采用的關(guān)鍵字位圖連接索引是一個(gè)數(shù)據(jù)庫對(duì)象上的細(xì)粒度關(guān)鍵字索引，在索引空間配額的約束下能夠根據(jù)獨(dú)立的統(tǒng)計(jì)或數(shù)據(jù)挖掘算法選擇TOPK關(guān)鍵字作為索引成員，最大化索引效率。同時(shí)，由于索引管理和處理的獨(dú)立性，索引與不同存儲(chǔ)和處理器相結(jié)合時(shí)的性能可以通過獨(dú)立的代價(jià)模型與數(shù)據(jù)庫自身的代價(jià)模型相結(jié)合，優(yōu)化基于索引的查詢處理。

3.2 關(guān)鍵字位圖連接索引模塊功能

圖1所示的查詢關(guān)鍵字管理模塊負(fù)責(zé)對(duì)查詢關(guān)鍵字進(jìn)行監(jiān)視，具體功能包括從查詢中抽取出謂詞關(guān)鍵字，記錄關(guān)鍵字訪問日志，并根據(jù)關(guān)鍵字訪問日志或關(guān)鍵字訪問頻率等數(shù)據(jù)通過統(tǒng)計(jì)分析方法確定高頻訪問關(guān)鍵字，為創(chuàng)建基于關(guān)鍵字的位圖連接索引提供候選關(guān)鍵字集。

圖1 基于關(guān)鍵字的位圖連接索引查詢優(yōu)化技術(shù)

本文所述關(guān)鍵字指查詢中where子句對(duì)應(yīng)的謂詞表達(dá)式，包括等值謂詞表達(dá)式和范圍謂詞表達(dá)式，抽象為統(tǒng)一關(guān)鍵字（uniform keyword），具體形式為：表名（前綴）_屬性名_操作符_關(guān)鍵字序列，如：

通過統(tǒng)一關(guān)鍵字命名規(guī)則，查詢關(guān)鍵字為數(shù)據(jù)庫級(jí)的全局索引成員，不需要為不同的維表屬性獨(dú)立創(chuàng)建位圖連接索引，簡化索引結(jié)構(gòu)。

在從查詢中抽取出關(guān)鍵字之后，可以將關(guān)鍵字相關(guān)信息記錄到關(guān)鍵字訪問日志中，訪問日志可以采用數(shù)據(jù)庫表存儲(chǔ)或磁盤日志文件存儲(chǔ)。關(guān)鍵字訪問日志記錄了關(guān)鍵字相關(guān)的各種信息，包括關(guān)鍵字名稱、時(shí)間戳、訪問計(jì)數(shù)等信息，可以周期性地通過統(tǒng)計(jì)方法或數(shù)據(jù)挖掘算法計(jì)算出系統(tǒng)TOPK個(gè)高頻訪問關(guān)鍵字候選集。如采用固定時(shí)間窗口統(tǒng)計(jì)方法可以匯總出各時(shí)間段內(nèi)關(guān)鍵字訪問次數(shù)，然后通過公式：

計(jì)算出各關(guān)鍵字加權(quán)訪問頻率。其中ai表示每個(gè)時(shí)間窗口內(nèi)關(guān)鍵字的訪問次數(shù)，a0+2-1a1+2-2a2+…+2-nan表示按窗口時(shí)間順序訪問頻率影響遞減策略的加權(quán)計(jì)算方法，(2-s)則通過關(guān)鍵字選擇率s增加影響因子，如選擇率為10%的關(guān)鍵字加權(quán)值為1.9，選擇率為50%的關(guān)鍵字加權(quán)值為1.5，優(yōu)先選擇低選擇率的高頻關(guān)鍵字來加速索引性能。同樣可以對(duì)關(guān)鍵字訪問日志采用數(shù)據(jù)挖掘方法分析關(guān)鍵字之間的關(guān)聯(lián)訪問關(guān)系和通過貪心算法計(jì)算全局最優(yōu)TOPK關(guān)鍵字，提高關(guān)鍵字位圖連接索引的全局使用效率。本文中主要提出了基于關(guān)鍵字的TOPK位圖連接索引服務(wù)機(jī)制，TOPK關(guān)鍵字選擇算法并不作為本文的主要內(nèi)容。通過查詢關(guān)鍵字日志機(jī)制記錄了查詢中的關(guān)鍵字信息，可以在實(shí)際應(yīng)用中增加不同的TOPK關(guān)鍵字挖掘算法來提高索引效率。

3.3 關(guān)鍵字位圖連接索引管理模塊功能

該模塊負(fù)責(zé)位圖索引的創(chuàng)建、存儲(chǔ)、更新和訪問。本文所述關(guān)鍵字位圖連接索引不是為指定的屬性列創(chuàng)建位圖連接索引，本文所指索引關(guān)鍵字分布在不同表的不同屬性中，因此可以集中地批量為離散的關(guān)鍵字創(chuàng)建位圖連接索引，也可以將關(guān)鍵字位圖連接索引的創(chuàng)建附加在相近的查詢處理過程中增量式創(chuàng)建。關(guān)鍵字位圖連接索引可以看作是＜keyword，bitmap＞數(shù)據(jù)對(duì)，可以存儲(chǔ)于內(nèi)存存儲(chǔ)結(jié)構(gòu)中，如內(nèi)存哈希表中，也可以存儲(chǔ)于獨(dú)立的key/value存儲(chǔ)引擎，如memcached、Redis等，形成外置的索引存儲(chǔ)。基于key/value存儲(chǔ)的索引甚至可以與數(shù)據(jù)庫服務(wù)器不在相同的節(jié)點(diǎn)上或擴(kuò)展到集群上以提高索引存儲(chǔ)能力。與數(shù)據(jù)庫內(nèi)置的索引結(jié)構(gòu)相比，索引存儲(chǔ)代價(jià)約束可以進(jìn)一步放松。索引的動(dòng)態(tài)更新以TOPK關(guān)鍵字加權(quán)訪問頻率的更新計(jì)算為基礎(chǔ)，確保TOPK個(gè)索引收益最大的關(guān)鍵字位圖在內(nèi)存存儲(chǔ)。對(duì)于TOPK關(guān)鍵字候選集中被替換出的位圖，可以根據(jù)應(yīng)用的需求，存儲(chǔ)于磁盤存儲(chǔ)設(shè)備上形成二級(jí)索引存儲(chǔ)結(jié)構(gòu)，提高已生成連接位圖的利用率。與傳統(tǒng)的索引技術(shù)不同，本文考慮到協(xié)處理器內(nèi)存-內(nèi)存-外存三級(jí)存儲(chǔ)層次，TOPK關(guān)鍵字位圖連接索引可以進(jìn)一步擴(kuò)展為TOPK/M/N模型，其中K＜M＜N，K、M、N分別表示協(xié)處理器內(nèi)存分配的連接位圖配額、內(nèi)存連接位圖配額，外存連接位圖配額。TOPN個(gè)連接位圖被系統(tǒng)根據(jù)查詢關(guān)鍵字訪問頻度模型創(chuàng)建，在N個(gè)高頻關(guān)鍵字中，TOPK個(gè)關(guān)鍵字連接位圖存儲(chǔ)于協(xié)處理器內(nèi)存，第K+1到第M個(gè)關(guān)鍵字連接位圖存儲(chǔ)于內(nèi)存，最后N-K-M個(gè)關(guān)鍵字連接位圖存儲(chǔ)于外存，即TOPK關(guān)鍵字連接位圖索引采用的是三級(jí)存儲(chǔ)模型。在關(guān)鍵字連接位圖更新時(shí)，位圖在不同的存儲(chǔ)層次中升級(jí)或降級(jí)，直至最終被淘汰。

當(dāng)用戶提出查詢請(qǐng)求時(shí)，以SQL命令為輸入，經(jīng)關(guān)鍵字位圖連接索引處理，輸出連接過濾位圖。如圖2所示，SQL命令中where子句中的謂詞按統(tǒng)一關(guān)鍵字命名規(guī)則被抽取為關(guān)鍵字，按關(guān)鍵字名稱在key/value關(guān)鍵字位圖連接索引中檢索，當(dāng)檢索到非空位圖時(shí)，將其抽取出按SQL命令中的謂詞表達(dá)式轉(zhuǎn)換為位圖操作。

圖2 SQL命令關(guān)鍵字位圖檢索

關(guān)鍵字位圖操作對(duì)應(yīng)查詢連接樹的剪枝或連接操作的約簡。當(dāng)查詢中某個(gè)維表上所有謂詞關(guān)鍵字都存在連接位圖且不包含分組屬性時(shí)，如查詢示例中part表和supplier表上的謂詞關(guān)鍵字，連接位圖的位操作代表了事實(shí)表與該維表的連接關(guān)系，查詢計(jì)劃中的連接操作可以消除。通過查詢關(guān)鍵字位圖的檢索生成對(duì)查詢連接操作剪枝后的新查詢Q'，進(jìn)而生成原查詢的新的執(zhí)行計(jì)劃。當(dāng)查詢中同一維表存在多個(gè)謂詞關(guān)鍵字但在索引中只檢索到部分連接位圖時(shí)，對(duì)于AND連接的多個(gè)位圖通過與操作生成事實(shí)表過濾位圖，減少連接操作中事實(shí)表候選連接記錄的數(shù)量；當(dāng)OR表達(dá)式中關(guān)鍵字對(duì)應(yīng)的位圖不完整時(shí)，檢索到的關(guān)鍵字連接位圖不被使用。將查詢中的謂詞操作轉(zhuǎn)換為關(guān)鍵字位圖操作樹，獨(dú)立于數(shù)據(jù)庫通過關(guān)鍵字檢索和樹形位圖操作生成查詢過濾位圖，然后將查詢過濾位圖作為數(shù)據(jù)庫大表的附加過濾器。數(shù)據(jù)庫只需要提供一個(gè)位圖接口，接收外置索引傳遞的過濾位圖并優(yōu)化表掃描操作。

圖3 關(guān)鍵字位圖操作樹

3.4 關(guān)鍵字位圖連接索引的自管理

關(guān)鍵字位圖連接索引的自管理性表現(xiàn)在如下幾個(gè)方面：

（1）索引效率自管理

關(guān)鍵字位圖索引解決了以屬性為粒度創(chuàng)建位圖連接索引時(shí)，20%位圖連接索引屬性中20%高頻關(guān)鍵字和80%非位圖連接索引屬性中20%高頻關(guān)鍵字的統(tǒng)一索引問題。通過細(xì)粒度關(guān)鍵字更好地提高索引效率，通過統(tǒng)一的索引存儲(chǔ)優(yōu)化多個(gè)索引的存儲(chǔ)和管理開銷。

（2）索引空間自適應(yīng)

在分析型內(nèi)存數(shù)據(jù)庫應(yīng)用中，大表上的索引需要巨大的空間開銷，對(duì)于內(nèi)存數(shù)據(jù)庫而言，內(nèi)存每單位存儲(chǔ)價(jià)格仍然遠(yuǎn)遠(yuǎn)高于其他存儲(chǔ)設(shè)備，因此索引需要自動(dòng)適應(yīng)內(nèi)存空間約束。關(guān)鍵字位圖連接索引中的位圖長度固定，索引大小取決于關(guān)鍵字的數(shù)量，因此可以根據(jù)索引的空間約束確定TOPK個(gè)關(guān)鍵字連接位圖，并且通過實(shí)時(shí)或周期性的關(guān)鍵字加權(quán)訪問頻率計(jì)算更新候選關(guān)鍵字集，動(dòng)態(tài)更新關(guān)鍵字位圖。

（3）索引平臺(tái)自管理

一種新的索引進(jìn)入數(shù)據(jù)庫系統(tǒng)是一件非常復(fù)雜的系統(tǒng)工程，一種索引服務(wù)于多種數(shù)據(jù)庫系統(tǒng)將產(chǎn)生較高的重復(fù)開發(fā)成本。因此，索引獨(dú)立于數(shù)據(jù)庫成為一種服務(wù)是索引平臺(tái)適應(yīng)性的表現(xiàn)?；趦?nèi)存key/value的存儲(chǔ)使關(guān)鍵字位圖連接索引不僅能夠服務(wù)于指定數(shù)據(jù)庫，還可以作為集群的共享索引存儲(chǔ)，通過內(nèi)存云擴(kuò)展索引存儲(chǔ)能力。在進(jìn)一步的研究中，可以將關(guān)鍵字位圖操作下壓到內(nèi)存云中計(jì)算。如圖4左側(cè)虛線框所示，na?ve的關(guān)鍵字位圖連接索引只利用內(nèi)存云存儲(chǔ)連接位圖，而查詢關(guān)鍵字檢索到的位圖需要抽取到索引客戶端進(jìn)行位圖操作；可以將關(guān)鍵位圖連接索引的位圖操作集成進(jìn)內(nèi)存云，使其成為一個(gè)索引服務(wù)，減少位圖網(wǎng)絡(luò)訪問代價(jià)。

圖4 云計(jì)算關(guān)鍵字位圖連接索引

4 實(shí)驗(yàn)與性能分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

關(guān)鍵字位圖連接索引可以有多種實(shí)現(xiàn)方案，在實(shí)驗(yàn)中重點(diǎn)關(guān)注位圖連接索引對(duì)查詢性能的優(yōu)化作用，包括位圖操作的代價(jià)和位圖索引對(duì)性能的提升。在實(shí)驗(yàn)中模擬了查詢命中不同數(shù)量索引位圖的場(chǎng)景，分別測(cè)試了位圖操作代價(jià)、基于過濾位圖的連接代價(jià)和查詢總時(shí)間。

基于關(guān)鍵字位圖連接索引的查詢優(yōu)化性能由內(nèi)存查詢處理算法效率和連接過濾位圖的選擇率決定。DDTA-JOIN[18]是一種基于列存儲(chǔ)的星形模型查詢算法，與開源內(nèi)存數(shù)據(jù)庫MonetDB及VectorWise具有類似的性能。在其基礎(chǔ)上實(shí)現(xiàn)了TOPK關(guān)鍵字位圖連接索引，用于分析測(cè)試連接索引對(duì)多維查詢處理性能的優(yōu)化效率。索引采用內(nèi)存哈希表方式存儲(chǔ)，測(cè)試關(guān)鍵字位圖連接索引對(duì)內(nèi)存數(shù)據(jù)庫的性能加速作用。

4.2 實(shí)驗(yàn)環(huán)境

在一臺(tái)HP ProLiant BL460c G7服務(wù)器上完成性能測(cè)試，服務(wù)器硬件配置為：兩個(gè)至強(qiáng)6核處理器E5645@2.40 GHz，24物理線程，48 GB內(nèi)存，300 GB硬盤。操作系統(tǒng)為ubuntu-11.10-server-amd64，gcc版本4.3.4。

使用100 GB（SF=100）SSB數(shù)據(jù)集，事實(shí)表記錄600 037 902條。完整地執(zhí)行SSB的13個(gè)測(cè)試查詢，并與代表性的內(nèi)存數(shù)據(jù)庫VectorWise（http：//www.tpc.org/tpch/default.asp）進(jìn)行性能對(duì)比測(cè)試，VectorWise目前還不支持位圖連接索引。

圖5顯示了VectorWise、DDTA-JOIN算法和基于位圖連接索引的DDTA-JOIN（簡稱BJI DDTA-JOIN）算法在13個(gè)測(cè)試查詢上的執(zhí)行時(shí)間。從總體性能來看，DDTA-JOIN平均查詢執(zhí)行時(shí)間為VectorWise的49.8%，在關(guān)鍵字位圖連接索引的支持下，查詢性能進(jìn)一步提升，平均查詢執(zhí)行時(shí)間為VectorWise的24.8%，即位圖連接索引能夠?qū)⒉樵兲幚硇阅芴岣咭槐丁?duì)于低選擇率的查詢，位圖連接索引的加速作用尤其突出。

圖5 內(nèi)存數(shù)據(jù)庫SSB性能對(duì)比測(cè)試

考慮到關(guān)鍵字位圖索引存在查詢關(guān)鍵字“命中率”以及優(yōu)化使用TOPK關(guān)鍵字位圖的問題，將關(guān)鍵字位圖按選擇率進(jìn)行排序，分別選擇1、2、3、4個(gè)關(guān)鍵字位圖進(jìn)行索引連接優(yōu)化。表1為使用不同數(shù)量關(guān)鍵字位圖查詢處理時(shí)索引階段位圖合并時(shí)間和基于位圖過濾的查詢處理時(shí)間，查詢總時(shí)間為前二者之和。位圖合并代價(jià)相對(duì)穩(wěn)定：2個(gè)位圖合并時(shí)間約150 ms，3個(gè)位圖約200 ms，4個(gè)位圖（Q4.2）約250 ms?；谖粓D過濾的查詢執(zhí)行時(shí)間隨位圖數(shù)量增多（選擇率降低）而減少，從總體性能來看，只使用一個(gè)位圖時(shí)查詢平均時(shí)間略有增長，使用多個(gè)位圖時(shí)查詢時(shí)間不斷降低。

表2列出了查詢中位圖索引計(jì)算占查詢處理總時(shí)間的比例和在位圖連接索引支持下平均查詢性能提升的比例。在CPU中，大數(shù)據(jù)下的位圖計(jì)算對(duì)CPU資源的消耗較高，位圖之間的邏輯運(yùn)算占查詢總時(shí)間的平均比例隨著位圖數(shù)量的增長而快速增長，在低選擇率查詢中，如Q2.3、Q3.3、Q3.4中，位圖運(yùn)算代價(jià)超過90%。

使用一塊中等配置的GPU顯卡作為位圖連接索引處理器。顯卡型號(hào)為GeForce 610M，支持CUDA 2.1，配置有1 GB DDR-3內(nèi)存，48個(gè)CUDA計(jì)算核心，顯卡主頻為1.48 GHz，每個(gè)線程塊支持1 024個(gè)線程，GPU與內(nèi)存之間的PCI-e通道傳輸速度約為2.5 GB/s。表3給出了GPU進(jìn)行位圖運(yùn)算和連接過濾位圖傳回內(nèi)存的總代價(jià)。GPU上的位圖運(yùn)算性能遠(yuǎn)遠(yuǎn)超過多核處理器，位圖運(yùn)算達(dá)到微秒級(jí)，加上壓縮的連接過濾圖傳輸代價(jià)，平均GPU位圖連接索引處理代價(jià)也不超過10 ms，遠(yuǎn)遠(yuǎn)低于多核處理器上幾百到上千毫秒的位圖索引運(yùn)算時(shí)間。引入GPU能夠極大地提升位圖連接索引的性能，索引性能需要通過硬件進(jìn)行提升。

表1 TOP K索引關(guān)鍵字位圖連接索引查詢優(yōu)化測(cè)試 ms

表2 位圖計(jì)算代價(jià)與性能提升收益 %

表3 基于GPU的位圖計(jì)算代價(jià)與性能提升收益

圖6 基于單位圖過濾的查詢性能分析

圖6分析了使用一個(gè)索引位圖時(shí)的查詢性能。Q1.x查詢?cè)谑聦?shí)表上有多個(gè)謂詞條件，增加過濾位圖后使事實(shí)表記錄訪問和計(jì)算代價(jià)大大降低，因此過濾位圖對(duì)性能的加速作用明顯。其他查詢中事實(shí)表上沒有過濾條件，增加過濾位圖相當(dāng)于附加了額外的判斷代價(jià)。對(duì)于列順序訪問而言，cache line寬度為64 Byte，外鍵寬度為4 Byte，當(dāng)選擇率低于1/16時(shí)，才會(huì)對(duì)cache line訪問效率有較大的影響，因此當(dāng)位圖選擇率較高時(shí)性能反而有損失。圖中觀察到，選擇率低于0.8%的位圖才產(chǎn)生性能收益，可以將0.8%作為關(guān)鍵字選擇的一個(gè)約束條件。

5 結(jié)束語

索引是提升數(shù)據(jù)庫性能的重要手段，但在內(nèi)存數(shù)據(jù)庫中，索引本身的運(yùn)算代價(jià)同樣成為數(shù)據(jù)庫整體性能的瓶頸。索引性能的提升不僅取決于存儲(chǔ)平臺(tái)，還取決于計(jì)算平臺(tái)，索引不再是一個(gè)平面結(jié)構(gòu)而是一個(gè)層次結(jié)構(gòu)，即索引的存儲(chǔ)與處理分布在協(xié)處理器內(nèi)存-內(nèi)存-外存三級(jí)存儲(chǔ)，因此需要一個(gè)更加靈活獨(dú)立的索引管理機(jī)制。

本文將位圖連接索引從數(shù)據(jù)庫中剝離出來構(gòu)建獨(dú)立的位圖連接索引服務(wù)，通過對(duì)查詢?nèi)罩镜耐诰蚝透骷?jí)存儲(chǔ)空間的約束構(gòu)造基于關(guān)鍵字的TOPK位圖連接索引機(jī)制，獨(dú)立完成索引的維護(hù)、更新和索引運(yùn)算，通過連接過濾位圖和查詢改寫建立索引服務(wù)與數(shù)據(jù)庫之間的松耦合服務(wù)層次，為數(shù)據(jù)庫提供獨(dú)立的索引服務(wù)，降低數(shù)據(jù)庫系統(tǒng)在擴(kuò)展索引結(jié)構(gòu)時(shí)的系統(tǒng)升級(jí)代價(jià)；同時(shí)，這種獨(dú)立的索引服務(wù)機(jī)制有利于索引充分利用各種新型先進(jìn)硬件平臺(tái)以提高索引和數(shù)據(jù)庫的整體性能。

[1]BonczP A，KerstenM L，ManegoldS.Breakingthe memory wall in MonetDB[J].Commun ACM，2008，51（12）：77-85.

[2]Zukowski M，van de Wiel M，Boncz P A.Vectorwise：a vectorized analytical DBMS[C]//ICDE，2012：1349-1350.

[3]ZukowskiM，BonczP A.Vectorwise：beyondcolumn stores[J].IEEE Data Eng Bull，2012，35（1）：21-27.

[4]TPC[EB/OL].[2013-03-11].http：//www.tpc.org/tpch/results/tpch_perf_results.asp?resulttype=noncluster&version=2%&currencyID=0.

[5]F?rber F，Cha S K，Primsch J，et al.SAP HANA database：data management for modern business applications[J].SIGMOD Record，2011，40（4）：45-51.

[6]ExaData X3[EB/OL].[2013-03-11].http：//www.oracle.com/us/products/database/exadata-db-machine-x3-2-1851253.pdf.

[7]Li Zhe，Ross K A.Fast joins using join indices[J].VLDB J，1999，8（1）：1-24.

[8]O'Neil P E，Graefe G.Multi-table joins through bitmapped join indices[J].SIGMOD Record，1995，24（3）：8-11.

[9]Oracle9/data warehousing guide[EB/OL].[2013-03-11].http：//docs.oracle.com/cd/B10500_01/server.920/a96520/indexes.htm.

[10]Valduriez P.Join indices[J].ACM Transon Database Syst，1987，12（2）：218-246.

[11]Abadi D J，MaddenS，Hachem N.Column-stores vs.row-stores：how different are they really?[C]//SIGMOD Conference，2008：967-980.

[12]Bellatreche L，Missaoui R，Necir H，et al.Selection and pruning algorithms for bitmap index selection problem using data mining[C]//DaWaK，2007：221-230.

[13]Bellatreche L，Missaoui R，Necir H，et al.A data mining approach for selecting bitmap join indices[J].JCSE，2007，1（2）：177-194.

[14]Aouiche K，Darmont J，Boussaid O，et al.Automatic selection ofbitmap join indexesin data warehouses[C]//DaWaK’05，2005：64-73.

[15]Necir H.A data mining approach for efficient selection bitmap join index[J].IJDMMM，2010，2（3）：238-251.

[16]He Bingsheng，Lu Mian，Yang Ke，et al.Relational query coprocessing on graphics processors[J].ACM Trans on Database Syst，2009，34（4）.

[17]Pirk H，Manegold S，Kersten M.Accelerating foreign-key joins using asymmetric memory channels[C]//Proceedings of International Conference on Very Large Data Bases 2011（VLDB），2011：585-597.

[18]張延松，焦敏，王占偉，等.海量數(shù)據(jù)分析的One-size-fits-all OLAP技術(shù)[J].計(jì)算機(jī)學(xué)報(bào)，2011（10）：1936-1947.