位圖連接索引服務機制研究

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

1.中國人民大學 信息學院，北京 100872

2.中國人民大學 中國調查與數據中心，北京 100872

1 引言

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

內存數據庫已成為重要的實時分析處理平臺，相對于當前主流的多核處理器和協處理器，內存仍然是一種訪問延遲較高的存儲設備，同時，內存訪問帶寬也是內存數據庫的性能瓶頸之一，需要內存數據庫中高效的索引機制來提高數據訪問效率和充分利用內存帶寬。

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

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

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

本文所提出的位圖連接索引服務機制是在傳統的位圖連接索引的基礎上設計獨立于數據庫的索引服務層，根據多維數據集的特性以關鍵字為粒度為數據庫建立統一的位圖連接索引，通過查詢日志上的統計或數據挖掘方法按內存空間約束建立基于關鍵字的TOPK位圖連接索引，在不同的索引更新窗口內根據關鍵字加權頻度更新TOPK連接位圖，以保證位圖連接索引在給定內存存儲空間中的使用效率最大化。在索引運算性能方面，通過多核處理器并行位圖索引計算，GPU并行位圖索引計算以及內存云位圖索引計算等不同的計算平臺靈活地為位圖連接索引提供更高性能的支持。本文的主要貢獻體現在三個方面：

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

位圖連接索引的管理不再是由數據庫管理員根據經驗進行管理，而是通過查詢負載監視和分析模塊通過特定的策略提供自適應的索引管理機制。

（2）基于關鍵字的TOPK位圖連接索引機制

內存數據庫要求索引具有更高的內存空間敏感性，提出了基于關鍵字的TOPK位圖連接索引來實現指定內存索引空間配額下的細粒度索引管理。

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

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

2 相關工作

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

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

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

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

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

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

3 基于關鍵字的TOP K位圖連接索引

3.1 系統架構

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

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

查詢優化器設計的難點在于集成了新的索引結構后的代價模型，而在本文中位圖操作的代價已知，過濾位圖上的選擇率為精確值，數據庫系統在原有的代價優化模型基礎上只要簡單增加基于位圖的掃描優化即可集成本文的索引技術。

傳統的基于屬性而創建的位圖連接索引在面臨存儲空間約束時難以有效解決頻繁訪問屬性中非頻繁訪問屬性成員索引利用率低的問題和高勢集或非頻繁訪問屬性中頻繁訪問成員的索引難以創建問題；在面臨計算代價估算時難以評估新的存儲或處理技術對局部性能優化所產生的收益，如引入SSD存儲或GPU等新型硬件存儲和加速位圖索引計算性能。

本文所采用的關鍵字位圖連接索引是一個數據庫對象上的細粒度關鍵字索引，在索引空間配額的約束下能夠根據獨立的統計或數據挖掘算法選擇TOPK關鍵字作為索引成員，最大化索引效率。同時，由于索引管理和處理的獨立性，索引與不同存儲和處理器相結合時的性能可以通過獨立的代價模型與數據庫自身的代價模型相結合，優化基于索引的查詢處理。

3.2 關鍵字位圖連接索引模塊功能

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

圖1 基于關鍵字的位圖連接索引查詢優化技術

本文所述關鍵字指查詢中where子句對應的謂詞表達式，包括等值謂詞表達式和范圍謂詞表達式，抽象為統一關鍵字（uniform keyword），具體形式為：表名（前綴）_屬性名_操作符_關鍵字序列，如：

通過統一關鍵字命名規則，查詢關鍵字為數據庫級的全局索引成員，不需要為不同的維表屬性獨立創建位圖連接索引，簡化索引結構。

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

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

3.3 關鍵字位圖連接索引管理模塊功能

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

當用戶提出查詢請求時，以SQL命令為輸入，經關鍵字位圖連接索引處理，輸出連接過濾位圖。如圖2所示，SQL命令中where子句中的謂詞按統一關鍵字命名規則被抽取為關鍵字，按關鍵字名稱在key/value關鍵字位圖連接索引中檢索，當檢索到非空位圖時，將其抽取出按SQL命令中的謂詞表達式轉換為位圖操作。

圖2 SQL命令關鍵字位圖檢索

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

圖3 關鍵字位圖操作樹

3.4 關鍵字位圖連接索引的自管理

關鍵字位圖連接索引的自管理性表現在如下幾個方面：

（1）索引效率自管理

關鍵字位圖索引解決了以屬性為粒度創建位圖連接索引時，20%位圖連接索引屬性中20%高頻關鍵字和80%非位圖連接索引屬性中20%高頻關鍵字的統一索引問題。通過細粒度關鍵字更好地提高索引效率，通過統一的索引存儲優化多個索引的存儲和管理開銷。

（2）索引空間自適應

在分析型內存數據庫應用中，大表上的索引需要巨大的空間開銷，對于內存數據庫而言，內存每單位存儲價格仍然遠遠高于其他存儲設備，因此索引需要自動適應內存空間約束。關鍵字位圖連接索引中的位圖長度固定，索引大小取決于關鍵字的數量，因此可以根據索引的空間約束確定TOPK個關鍵字連接位圖，并且通過實時或周期性的關鍵字加權訪問頻率計算更新候選關鍵字集，動態更新關鍵字位圖。

（3）索引平臺自管理

一種新的索引進入數據庫系統是一件非常復雜的系統工程，一種索引服務于多種數據庫系統將產生較高的重復開發成本。因此，索引獨立于數據庫成為一種服務是索引平臺適應性的表現。基于內存key/value的存儲使關鍵字位圖連接索引不僅能夠服務于指定數據庫，還可以作為集群的共享索引存儲，通過內存云擴展索引存儲能力。在進一步的研究中，可以將關鍵字位圖操作下壓到內存云中計算。如圖4左側虛線框所示，na?ve的關鍵字位圖連接索引只利用內存云存儲連接位圖，而查詢關鍵字檢索到的位圖需要抽取到索引客戶端進行位圖操作；可以將關鍵位圖連接索引的位圖操作集成進內存云，使其成為一個索引服務，減少位圖網絡訪問代價。

圖4 云計算關鍵字位圖連接索引

4 實驗與性能分析

4.1 實驗設計

關鍵字位圖連接索引可以有多種實現方案，在實驗中重點關注位圖連接索引對查詢性能的優化作用，包括位圖操作的代價和位圖索引對性能的提升。在實驗中模擬了查詢命中不同數量索引位圖的場景，分別測試了位圖操作代價、基于過濾位圖的連接代價和查詢總時間。

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

4.2 實驗環境

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

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

圖5顯示了VectorWise、DDTA-JOIN算法和基于位圖連接索引的DDTA-JOIN（簡稱BJI DDTA-JOIN）算法在13個測試查詢上的執行時間。從總體性能來看，DDTA-JOIN平均查詢執行時間為VectorWise的49.8%，在關鍵字位圖連接索引的支持下，查詢性能進一步提升，平均查詢執行時間為VectorWise的24.8%，即位圖連接索引能夠將查詢處理性能提高一倍。對于低選擇率的查詢，位圖連接索引的加速作用尤其突出。

圖5 內存數據庫SSB性能對比測試

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

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

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

表1 TOP K索引關鍵字位圖連接索引查詢優化測試 ms

表2 位圖計算代價與性能提升收益 %

表3 基于GPU的位圖計算代價與性能提升收益

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

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

5 結束語

索引是提升數據庫性能的重要手段，但在內存數據庫中，索引本身的運算代價同樣成為數據庫整體性能的瓶頸。索引性能的提升不僅取決于存儲平臺，還取決于計算平臺，索引不再是一個平面結構而是一個層次結構，即索引的存儲與處理分布在協處理器內存-內存-外存三級存儲，因此需要一個更加靈活獨立的索引管理機制。

本文將位圖連接索引從數據庫中剝離出來構建獨立的位圖連接索引服務，通過對查詢日志的挖掘和各級存儲空間的約束構造基于關鍵字的TOPK位圖連接索引機制，獨立完成索引的維護、更新和索引運算，通過連接過濾位圖和查詢改寫建立索引服務與數據庫之間的松耦合服務層次，為數據庫提供獨立的索引服務，降低數據庫系統在擴展索引結構時的系統升級代價；同時，這種獨立的索引服務機制有利于索引充分利用各種新型先進硬件平臺以提高索引和數據庫的整體性能。

[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]張延松，焦敏，王占偉，等.海量數據分析的One-size-fits-all OLAP技術[J].計算機學報，2011（10）：1936-1947.