并發內存OLAP查詢優化技術研究

張延松 焦 敏 張 宇 王 珊

1(數據工程與知識工程教育部重點實驗室(中國人民大學) 北京 100872)2(中國人民大學信息學院 北京 100872)3(中國調查與數據中心(中國人民大學) 北京 100872)4(中國氣象局國家衛星氣象中心 北京 100081)(zhangys_ruc@hotmail.com)

?

并發內存OLAP查詢優化技術研究

張延松1,2,3焦 敏1,2張 宇4王 珊1,2

1(數據工程與知識工程教育部重點實驗室(中國人民大學) 北京 100872)2(中國人民大學信息學院 北京 100872)3(中國調查與數據中心(中國人民大學) 北京 100872)4(中國氣象局國家衛星氣象中心 北京 100081)(zhangys_ruc@hotmail.com)

基于多核處理器硬件技術和高并發查詢負載需求，近年來的研究不僅關注于一次一查詢模式的查詢優化技術，而且也關注于一次一組模式的查詢優化技術.通過將并發查詢轉換為共享負載，一些低訪問延遲的操作，如磁盤IO、cache訪問，可以被多個并發的查詢所共享.當前的研究通?；诠蚕聿樵儾僮鞣?，如掃描、連接、謂詞處理等，通過生成全局執行計劃優化并發查詢.對于復雜的分析型負載，如何創建優化的執行計劃是一個具有挑戰性的問題.在廣泛使用的星形模型的基礎上提出一種模板OLAP查詢執行計劃來簡化查詢執行計劃，以達到最大化查詢操作符利用率的目標.1)提出了基于代理鍵的連接索引技術，將傳統的基于值探測的連接操作轉化為內存數組索引引用(AIR)，使連接操作的CPU效率更高并且支持聚集計算的后物化;2)并發查詢的謂詞處理簡化為cache line敏感的謂詞向量，在單次cache line訪問中最大化并發查詢謂詞計算性能;3)通過多核并行實現技術在SSB基準上進行測試.實驗結果表明：共享掃描和共享謂詞處理能夠將并發OLAP查詢處理性能提升1倍.

并發OLAP查詢處理；數組索引引用；模板OLAP查詢處理；連接索引；過濾向量

大內存、多核處理器已經成為高性能計算平臺的基本特征，基于內存的分析處理系統，如MonetDB[1]，Vectorwise[2]，SAP HANA[3]，Oracle Exadata X4[4]，Hyper[5]，IWA[6]等逐漸成為高性能分析型數據庫和新一代數據庫一體機技術的代表.隨著互聯網用戶和互聯網業務的飛速發展，高負載的實時分析處理需求是數據庫需要面對的新技術挑戰，不僅要求數據庫引擎具有良好的實時查詢響應性能，還要求數據庫引擎具有強大的查詢吞吐性能，能夠同時滿足成百上千的并發分析處理任務.

分析型內存數據庫技術面向低延遲的實時查詢處理負載，查詢處理技術的核心是提高單個查詢的執行性能，以MonetDB的二元關聯表(binary associated table, BAT)處理和Vectorwise的向量處理技術為代表，通過列存儲訪問、優化內存Hash表設計、以向量為單位處理來優化數據的cache訪問局部性，提高查詢處理性能.在并發查詢處理時，每個查詢處理線程需要并發地訪問數據，維護獨立的線程私有化數據(如Hash表、向量等)，從而造成線程間數據共享度低、內存數據在cache中頻繁換入換出，降低了并發查詢處理效率.

并發查詢優化技術主要包括查詢間結果集共享訪問、查詢間數據共享掃描和查詢間操作符共享等方式.MonetDB采用緩存中間結果技術[7]，并通過對并發查詢執行順序進行優化以使緩存的中間結果能夠被后續的查詢利用.Database Cracking[8]通過查詢時的動態數據劃分技術加速后續查詢的謂詞處理性能.共享結果集并發優化技術的基礎是查詢的相關性，通過相近查詢結果集復用減少冗余的計算代價.Blink系統[9-10]通過Denormalization技術將模式簡化為單一的表，并發查詢轉換為表掃描和謂詞操作，通過共享掃描技術提高并發查詢的數據訪問效率.Crescando[11]在存儲訪問層采用共享掃描技術，并通過連接數據與查詢集合的方式實現并發查詢處理.共享掃描是并發查詢處理廣泛采用的技術，主要優化訪問延遲較大的數據集上的全表掃描操作，通常采用循環掃描方式支持“always-on”模式的查詢處理.QPipe[12]，DataPath[13]，SharedDB[14]，CJoin[15]等研究面向復雜的分析型查詢操作符，通過共享執行代價大的操作符減少并發查詢處理時的冗余計算代價.共享操作符的并發查詢優化技術需要面向并發查詢構造全局性的查詢執行計劃，調整查詢執行順序以實現高代價操作符的共享.

在內存數據倉庫應用場景中，OLAP查詢是一個在多維數據空間中定位多維數據子集并對其進行聚集計算的過程.在關系OLAP(relational OLAP, ROLAP)處理模式中，多維查詢處理表現為事實表通過維表外鍵與各維表生成的Hash表進行連接并對連接結果進行分組聚集的計算過程，是一個SPJGA(選擇、投影、連接、分組、聚集)關系操作，查詢性能的關鍵是星形連接(star join)的效率，Hash連接操作的性能取決于Hash表相對于cache的大小以及連接選擇率.當構建并發查詢共享Hash表時，由于查詢中需要攜帶不同查詢的維表分組屬性，共享Hash表中的記錄可能為維表記錄寬度，Hash表存儲空間增大；星形Hash連接在選擇率較低時產生較大的無效Hash探測代價，在并發查詢處理時消耗了過多的CPU cycle.

本文以數據倉庫中通用的代理鍵索引為基礎，通過代理鍵連接索引機制實現基于數組索引引用(array index referencing， AIR)的連接技術，將傳統的Hash連接操作簡化為內存數組索引直接引用，消除了Hash表.進一步地，通過維表位圖壓縮維表記錄，實現連接過濾，支持后物化的維表分組屬性訪問.在AIR OLAP多維查詢處理技術的支持下，并發OLAP查詢處理被劃分為3個階段：1)并發查詢分組并創建維表位圖向量，記錄并發查詢在每一個維表記錄上的謂詞過濾結果；2)并發星形過濾，通過事實表記錄外鍵定位各維表位圖向量，通過按位與操作計算出當前事實表記錄在各個維表上每個并發查詢的過濾結果；3)基于代理鍵連接索引的分組聚集計算，事實表記錄按映射的數組內存索引地址直接訪問維表分組屬性并進行聚集計算.

與已有的并發查詢技術相比，AIR OLAP并發查詢處理直接在原始星形模式上執行，不需要物化表；星形OLAP查詢處理通過代理鍵連接索引構造了一個模板化的OLAP查詢執行計劃，不同的OLAP查詢對應結構相同、數據不同的維過濾位圖，相同的查詢執行計劃能夠最大化并發查詢的共享訪問和計算性能；后物化的聚集計算則在低選擇率的OLAP查詢中提高了數據訪問效率.

1 相關工作

1.1 內存OLAP查詢優化技術

列存儲已經成為內存分析型數據庫普遍采用的存儲模型，面向事務處理優化的內存數據庫通常支持列存儲、行存儲以及混合存儲模型以優化不同的查詢負載.MonetDB采用一次一列(column-at-a-time)的處理技術，在低選擇率時具有良好的性能，但選擇率較高時需要物化較大的中間結果，增加了存儲及計算代價.Vectorwise采用一次一向量(vector-at-a-time)的查詢處理技術，以L1 cache敏感的較小向量為處理單位，實現L1 cache內的物化數據存儲訪問，消除了內存物化數據存儲和訪問代價.傳統的行存儲模型執行的是一次一記錄(tuple-at-a-time)執行方式，存在數據訪問效率低、查詢解析代價高的問題.但在并發查詢處理負載中，不同的查詢訪問不同的列，導致內存帶寬訪問競爭加劇；同時，并發查詢產生較多的中間結果數據，增加了cache及內存訪問代價.

Hash連接是內存數據庫優化技術的核心問題.文獻[16-17]通過實驗驗證了在多核處理器平臺上基于radix分區的并行Hash連接算法優于基于共享Hash表的并行Hash連接算法和排序連接算法，通過分區提高Hash探測階段的cache數據局部性，提升整體Hash連接操作性能.但在并發查詢處理時，radix分區操作會產生較大的內存消耗，而共享Hash表連接方法則可以通過建立并發查詢共享Hash表的方式支持批量Hash連接操作.因此，并發OLAP查詢優化技術與占用全部資源的單查詢優化技術在設計思想上有較大的區別，前者強調全局共享效率，后者強調局部性能.

內存列存儲支持基于偏移地址計算的直接內存訪問，文獻[18]實現了數據倉庫中將事實表外鍵映射為維表內存偏移地址的DDTA-JOIN(directly dimensional tuple accessing-join)算法，支持在原始數據上的內存直接關聯記錄訪問，簡化了連接操作并消除了傳統的Hash表或排序操作.

1.2 并發OLAP查詢優化技術

在數據倉庫負載中，表掃描操作通常代價較高，基于共享掃描的并發查詢技術能夠更高效地利用順序訪問的內存帶寬，同時服務于多個OLAP查詢處理任務.Blink采用非規范化設計，將OLAP查詢轉換為單一的表掃描操作，實現了常量時間的查詢處理性能，同時支持基于共享掃描的并發查詢處理.Crescando通過索引運行的查詢和共享掃描來支持可預期性能的查詢處理，MonetDBX100也提供了協同掃描機制以優化動態的內存帶寬性能.

代表性的關系操作符并發優化技術包括Datapath，CJoin，SharedDB，QPipe，COD[19]等，基本思想是為并發查詢創建全局操作符.CJoin是面向數據倉庫星形模型的一種并發OLAP查詢優化技術，它為并發查詢創建全局Hash表，事實表循環掃描為每個事實表記錄依次通過每個Hash過濾器傳遞事實表記錄在每個過濾器上對每個并發查詢的過濾結果，實現一次Hash探測操作服務于多個并發查詢任務.QPipe作為執行代價較大的操作創建一直在線運行的操作符，查詢進入系統后通過代價估算連接上活動的共享操作符，從操作符產生的數據流中獲取當前查詢需要的結果.COD通過列存儲、水平分片策略，基于NUMA架構在每個核心的數據分片上執行Clock-Scan，連續掃描每個核心上數據集的水平分片.查詢首先進入執行隊列，按謂詞索引，掃描線程執行數據分片上的順序掃描，完成查詢隊列的查詢任務，然后通過歸并和聚集線程將查詢結果推送到輸出隊列.文獻[20]實現了磁盤存儲事實表共享掃描、內存DDTA-JOIN連接模式的并發OLAP查詢處理，在一個IO時間片內通過多核內存并發DDTA-JOIN算法最大化共享IO訪問服務的并發查詢數量.

在共享操作符的并發OLAP查詢處理技術中，并發查詢處理的性能通常優于一次一查詢執行方式的性能，尤其在存在慢速磁盤IO的OLAP應用場景中.內存OLAP并發查詢處理時，不僅需要通過共享掃描減少表掃描的內存訪問延遲，更重要的是通過并發查詢優化技術減少星形連接過程的cache miss，即通過算法數據結構的優化在一個cache line miss中盡可能完成并發查詢的計算任務.

Fig. 1 Multidimensional models of typical benchmarks.圖1 典型多維數據模型

2 并發OLAP查詢處理

2.1 AIR OLAP多維查詢處理

數據倉庫不同于關系數據庫之處在于采用的是多維數據模型，即每一個事實數據F由多個維度(D1,D2,…,Dn)映射(Map)，記作F←Map(D1,D2,…,Dn).

圖1顯示了OLAP應用中最具有代表性的模式：TPC-H[21]，SSB[22]，TPC-DS[23].在數據倉庫中分別對應雪花模型(snow-flake schema)、星形模型(star schema)和暴風雪(snow storm schema)模型.

TPC-H是一個滿足3NF的數據庫，存在共享多級維表，可以看作是一種雪花模型，也可以看作是3個子星形模式：(ORDERS,CUSTOMER→NATION→REGION)，(LINEITEM,PART,SUPPLIER→NATION→REGION)，(PARTSUPP,PART,SUPPLIER→NATION→REGION).

SSB是對TPC-H非規范化處理后的星形模型，使用單一的星形模式：(LIENORDER,PART,SUPPLIER,CUSTOMER,DATE).

TPC-DS可以看作是2個子星形模式：(Store_Sales,Date_Dim,Promotion,Customer→Customer_Address,Customer→Customer_Demographics,Customer→Household_Demographics→Income_Band,Item,Store,Time_Dim)，(Store_Returns,Reason,Date_Dim,Customer→Customer_Address,Customer→Customer_Demographics,Customer→Household_Demographics→Income_Band,Item,Store,Time_Dim).

3個模式普遍遵循數據倉庫的代理鍵約束，除SSB的維表DATE主鍵為19920101,19920102,…,格式的連續日期外，其余所有維表主鍵均為從0或1開始的連續序列，當采用內存列存儲時，維表主鍵可以直接映射為維表屬性列的數組下標地址，事實表記錄可以通過外鍵數組下標引用方式直接訪問內存維屬性列對應的記錄.

在圖2所示的AIR OLAP多維查詢處理中，多維分析處理分為3個階段：1)通過SQL命令改寫在維表上創建過濾位圖；2)事實表外鍵通過代理鍵連接索引映射到維表過濾位圖完成星形連接過濾；3)滿足連接過濾條件的事實表記錄通過內存索引引用分組屬性并進行聚集計算.在AIR OLAP查詢處理過程中，計算代價最大的多維連接操作簡化為從事實表外鍵向維表位圖的位置映射，聚集計算采用后物化維分組屬性直接內存訪問方式，簡化了查詢處理算法，同時，維表構成了查詢共享訪問數據集，減少查詢執行時私有連接Hash表的開銷，提高了維表列的數據局部性.

Fig. 2 Dimensional bitmap filtering oriented AIR OLAP multidimensional query processing.圖2 基于維表位圖過濾的AIR OLAP多維查詢處理

2.2 并發AIR OLAP多維查詢處理

在AIR OLAP算法中，多維過濾需要訪問各個維表位圖對應位置并進行按位與運算.每次位圖訪問對應1個cache line訪問，但僅使用512 b中的1 b.如圖3所示，我們以5個并發查詢為例，在并發AIR OLAP查詢處理時，維表過濾位圖轉換為維表過濾向量，5 b向量表示5個并發查詢在當前維表記錄上的謂詞處理結果，并發查詢Q0,Q1,Q2,Q3,Q4生成寬度為5 b的維表過濾向量.

事實表對維表位向量的每次訪問都可以獲得512個并發查詢過濾位圖，多個維表位向量的按位與操作可以利用SIMD機制并行計算，從而提高維表位圖訪問和計算的效率.

2.3 并發AIR OLAP多維查詢處理實現技術

2.3.1 并發查詢預處理

基于維過濾位向量的并發OLAP查詢處理需要對并發查詢分組，并通過查詢預處理過程為并發查詢創建維過濾位向量.如圖4所示，OLAP查詢被分解為維表上的謂詞處理和分組聚集表達式，每個維表謂詞表達式生成一個維過濾位圖，存儲在行存儲的維過濾向量中查詢序號對應的列.并發查詢存儲在查詢隊列(query queue)中，分別記錄了查詢在各個維表上的分組屬性，度量屬性通過事實表屬性位向量來記錄哪些度量屬性需要進行聚集計算.

Fig. 3 Concurrent AIR OLAP query processing.圖3 并發AIR OLAP多維查詢處理

Fig. 4 Concurrent query grouping and predicate pre-computing.圖4 并發查詢分組和謂詞預計算

在并發查詢分組過程中創建了維過濾位向量，加速維過濾位圖的位與計算效率，同時創建并發查詢分組聚集表，用于對滿足連接過濾條件事實表記錄以后物化方式進行的直接維表分組屬性訪問操作.

2.3.2 并發連接過濾操作

在圖5的并發OLAP查詢處理過程中，事實表上執行共享的順序掃描操作，每個維表對應一個位向量過濾器(BVecFilter)，事實表記錄外鍵分別映射到各個維表位向量過濾器中抽取對應的位向量并進行如圖3所示的按位與操作.按位與操作結果產生的位向量中的“1”表示該位置i對應的查詢Qi在當前事實表記錄上滿足所有維表上的連接過濾條件，需要進行后續的分組聚集計算.向量的按位與操作結果傳遞給查詢分發器(distributor)，根據位向量中“1”的位置調用各個對應查詢預設的聚集計算函數(aggr operator)，完成并發查詢對當前事實表記錄的聚集計算.

Fig. 5 dimensional filtering bit vector oriented concurrent OLAP.圖5 基于維過濾位向量的并發OLAP查詢處理

Fig. 6 Bit vector oriented grouping and aggregate computing.圖6 基于位向量的分組聚集計算

2.3.3 并發分組聚集計算操作

查詢分發器的分組聚集計算需要經過查詢映射和分組映射2個階段.如圖6所示，首先通過生成的位向量中“1”的位置映射查詢隊列中的查詢記錄，然后獲得查詢隊列中記錄的分組屬性名稱通過事實表記錄中外鍵的值映射到對應的維表分組屬性列中獲取分組屬性值，并根據事實向量訪問對應的度量屬性值，生成若干個連接輸出記錄，通過聚集計算中的Hash表進行分組聚集計算.

AIR的維表記錄內存映射訪問機制實現了后物化的分組聚集計算，不需要在共享Hash表中存儲較大的并發查詢分組屬性記錄，實現了對共享事實表記錄按并發查詢位過濾向量結果的“按需訪問”.

2.3.4 多線程并發OLAP操作

Fig. 7 Bit vector oriented multi-thread concurrent OLAP.圖7 基于位向量的多線程并發OLAP查詢處理

2.3.5 AIR算法對不同模式的適應性

星形模型是數據倉庫的基礎，也構成了多維數據集中事實表與多個維表之間的映射關系.內存列存儲和數據倉庫代理鍵機制支持了事實表外鍵可以直接映射為維記錄內存偏移地址的特性，即事實表外鍵在維表列上的array index referencing，從而將傳統Pipeline連接分解為簡單的多維連接過濾和后物化模式的分組聚集計算，多維連接過濾操作轉換為位向量計算，適合當前CPU的單指令多數據流(single instruction multiple data， SIMD)計算特性.雪花型模式的維表構成主-外鍵參照引用關系的維層次，可以通過AIR算法將底端層次維表上的謂詞條件映射到頂端層次維表記錄上，規范化為星形過濾向量結構，滿足模板化OLAP查詢處理的基礎條件.

星形模型上的并發查詢基于共享事實表掃描和共享多維過濾計算，復雜的數據倉庫模式，如雪花模型TPC-H、暴風雪模型TPC-DS等可以看作是多個星形模式上的協同計算，各事實表之間同樣存在主-外鍵參照引用關系.在實踐中，涉及多事實表的查詢可以采用基于事實表間主-外鍵的AIR協同掃描技術完成并發OLAP查詢時多事實表間的共享掃描；當查詢包含多個獨立星形結構之間的協同查詢時，可以將一個星形模型并發OLAP計算操作符的輸出流作為另一個星形模式并發OLAP計算操作符的輸入，在星形子模式之間共享并發OLAP計算.

3 實驗結果與分析

3.1 實驗環境配置

實驗硬件平臺為一臺HP服務器，配置有4塊Intel?Xeon?E5-4640@2.40 GHz(8-core,20 MB Cache)處理器、256 GB內存、操作系統為Windows 2012 64位版，查詢數據集為Star Schema Benchmark[22].在SSB測試集中，擴展因子(scale factor,SF)為數據量單位，SF=1對應事實表記錄數量為6 000 000.實驗數據集設置多組，大小分別取SF為1，10，100、并發查詢數量分別為32，64，128，256，最大測試并發數量為1 024.

在并發OLAP查詢性能測試中，我們選擇了6個對比對象：AIR OLAP單線程查詢處理、多線程并發執行的AIR OLAP查詢處理、基于維過濾位向量的AIR OLAP并發查詢處理、基于MySQL內存表的OLAP查詢處理、開源列存儲數據庫MonetDB、基于向量處理的內存數據庫Vectorwise.參考文獻所述并發查詢研究主要為原型系統，難于進行有效的性能對比.Vectorwise，MonetDB等內存數據庫在學術界與產業界可以作為性能標桿，我們以它們作為基礎性能參照對象能夠為后續研究提供可類比的性能.

實驗中主要的測試指標是并發查詢執行總時間、并發查詢平均查詢執行時間、查詢吞吐性能(每小時執行查詢的數量).實驗使用服務器為對稱多處理結構(symmetric multi-processing, SMP)多核CPU架構，使用pthread庫函數實現并發查詢的多線程并行處理，測試數據庫的并發查詢通過多線程JDBC訪問實現，在測試時間中去掉JDBC初始化時間，只計算并發查詢執行時間.

3.2 實驗測試結果和分析

表1、表2給出了在SF=100數據集下，并發查詢數量為32，64，128，256時的并發OLAP查詢執行總時間和平均查詢執行時間對比.

AIR OLAP采用行式掃描，通過外鍵值-地址映射維表謂詞處理機制，查詢時間比較穩定，查詢處理的主要代價是表掃描代價，串行執行時查詢平均執行時間性能與MySQL內存表查詢處理性能相當.當通過多線程并發執行AIR OLAP查詢處理時，查詢任務被并發地執行，但由于并發查詢線程超過物理核心數量時產生線程切換代價以及并發查詢處理時在LLC所產生的cache爭用，并發AIR OLAP查詢的加速比低于物理核心數量32，在256并發線程時達到最大加速比22.基于MySQL內存表的并發OLAP查詢平均執行時間達到22 s，而列存儲內存數據庫MonetDB并發查詢最小平均查詢執行時間為4.63 s，體現了列存儲相對于行存儲的性能優勢.基于向量處理的Vectorwise是當前性能最好的產品級內存數據庫，當前為TPC-H測試中SF=100和SF=300數據集上的性能最佳的數據庫系統[24]，在并發OLAP查詢時的最小平均查詢執行時間為0.89 s，與并發AIR OLAP的平均查詢執行時間相當.基于維過濾位向量技術的并發AIR OLAP的最小平均查詢執行時間最短，僅為0.48 s，通過事實表共享掃描和并發維過濾技術進一步提高了并發查詢的CPU處理效率.

Table 1 Comparison of Total OLAP Query Execution Time (SF=100)

Table 2 Comparison of Average OLAP Query Execution Time (SF=100)

圖8顯示了不同并發度時的查詢吞吐性能(每小時查詢執行數量)，其中MonetDB和MySQL內存表的查詢吞吐性能趨于穩定，而并發AIR OLAP、基于維過濾位向量的AIR OLAP和Vectorwise的查詢吞吐性能隨并發度的增加而增加，當并發查詢數量增加時能夠相應地提高數據訪問及計算的效率，能夠較好地利用現代多核處理器的并行計算資源.

圖9顯示了基于維過濾位向量的AIR OLAP在數據集大小為SF=1，SF=10，SF=100時，不同并發線程數量時執行的平均查詢時間.在實驗中，線程內并發查詢數量與線程數量相同，線程數量增長時，并發查詢數量也隨之增長，維過濾位圖寬度增長.圖9所示的查詢平均執行時間中，當線程(并發查詢)數量為512時具有最少的平均查詢執行時間，主要原因是512個并發查詢對應的維過濾位向量長度為512 b(64 B)，對應一個cache line訪問，能夠最大化cache line數據的利用率，內存訪問數據利用率最高.

Fig. 8 Query throughput of concurrent query workload(SF=100).圖8 并發查詢吞吐性能(SF=100)

Fig. 9 Average concurrent query execution time.圖9 并發查詢平均執行時間

綜上所述，AIR OLAP與當前主流的內存分析型數據庫在OLAP算法實現上最大的不同是充分利用了數據倉庫代理鍵的地址映射(array index referencing)特點，實現了基于事實表外鍵映射的連接索引，支持基于維表過濾位圖的連接過濾和后物化的分組聚集計算，將OLAP查詢處理過程中的查詢私有數據集轉換為并發查詢共享訪問的較小的維過濾位向量和原始維表列，在并發查詢處理時提高了數據訪問的局部性，因此在并發AIR OLAP查詢處理時有較好的數據局部性和吞吐性能.

4 結束語

AIR OLAP查詢處理中與并發查詢優化相關的操作是并發數據訪問和并發連接過濾計算：并發數據訪問體現在并發查詢共享事實表掃描操作，并發連接過濾計算體現在維表過濾位圖映射由一位擴展到多位，充分利用cache line訪問和計算更多的并發查詢維過濾位，提高并發OLAP查詢的整體性能.

本文研究范圍定位于可以作為基礎操作符的星形模式下的共享OLAP查詢處理技術，可以作為通用OLAP查詢處理的基礎并發操作符.與Datapath，sharedDB，SWO[25]等技術相比，AIR OLAP算法首先基于數據倉庫模式分解為星形模式集合，在星形模式上應用維過濾位向量技術優化共享掃描與連接過濾操作，達到局部最佳共享OLAP處理性能，在多個星形操作符之間再進行數據流共享優化，簡化復雜模式下的并發查詢共享優化技術.在未來的工作中，我們將針對TPC-H和TPC-DS模式特點，研究多個共享操作符之間的協同并發查詢優化技術.

[1]Boncz P A, Kersten M L, Manegold S. Breaking the memory wall in MonetDB[J]. Communications of the ACM, 2008, 51(12): 77-85

[2]Zukowski M, Boncz P A. Vectorwise: Beyond column stores[J]. IEEE Data Engineering Bulletin, 2012, 35(1): 21-27

[3]Sikka V, F?rber F, Lehner W, et al. Efficient transaction processing in SAP HANA database: The end of a column store myth[C] //Proc of ACM SIGMOD 2012. New York: ACM, 2012: 731-742

[4]Oracle. Oracle exadata database machine[EB/OL]. [2015-03-11]. http://www.oracle.com/technetwork/database/exadata/overview/index.html

[5]Kemper A, Neumann T. HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots[C] //Proc of ICDE 2011. Piscataway, NJ: IEEE, 2011: 195-206

[6]IBM. Informix warehouse accelerator-performance is everything[EB/OL]. (2013-03-21)[2015-01-14]. http://www.iiug.org/library/ids_12/IWA%20White%20Paper-2013-03-21.pdf

[7]Zukowski M, Hèman S, Nes N, et al. Cooperative scans: Dynamic bandwidth sharing in a DBMS[C] //Proc of VLDB 2007. New York: ACM, 2007: 723-734

[8]Pirk H, Petraki E, Idreos S, et al. Database cracking: Fancy scan, not poor man's sort![C] //Proc of the 10th Int Workshop on Data Management on New Hardware. New York: ACM, 2014: 1-8

[9]Qiao L, Raman V, Reiss F, et al. Main-memory scan sharing for multi-core CPUs[C] //Proc of VLDB 2008. New York: ACM, 2008: 610-621

[10]Raman V, Swart G, Qiao L, et al. Constant-time query processing[C] //Proc of ICDE 2008. Piscataway, NJ: IEEE, 2008: 60-69

[11]Unterbrunner P, Giannikis G, Alonso G, et al. Predictable performance for unpredictable workloads[C] //Proc of VLDB 2009. New York: ACM, 2009: 706-717

[12]Harizopoulos S, Shkapenyuk V, Ailamaki A. QPipe: A simultaneously pipelined relational query engine[C] //Proc of ACM SIGMOD 2005. New York: ACM, 2005: 383-394

[13]Kossmann D, Konrad S. Iterative dynamic programming: A new class of query optimization algorithms[J]. ACM Trans on Database Systems, 2000, 25(3): 43-82

[14]Giannikis G, Alonso G, Kossmann D. SharedDB: Killing one thousand queries with one stone[J]. Proceedings of the VLDB Endowment, 2012, 5(6): 526-537

[15]Candea G, Polyzotis N, Vingralek R. A scalable, predictable join operator for highly concurrent data warehouses[C] //Proc of VLDB 2009. New York: ACM, 2009: 277-288

[16]Balkesen C, Teubner J, Alonso G, et al. Main-memory Hash joins on multi-core CPUs: Tuning to the underlying hardware[C] //Proc of ICDE 2013. Piscataway, NJ: IEEE, 2013: 362-373

[17]Balkesen C, Alonso G, Teubner J, et al. Multi-core, main-memory joins: Sort vs. hash revisited[J]. Proceedings of the VLDB Endowment, 2013, 7(1): 85-96

[18]Zhang Yansong, Jiao Min, Wang Zhanwei, et al. One-size-fits-all OLAP technique for big data analysis[J]. Chinese Journal of Computers, 2011, 34(10): 1936-1947 (in Chinese)(張延松, 焦敏, 王占偉, 等. 海量數據分析的One-size-fits-all OLAP技術[J]. 計算機學報, 2011, 34(10): 1936-1947)

[19]Giceva J, Salomie T I, Schüpbach A, et al. COD: Database/operating system co-design[C/OL] //Proc of CIDR 2013.2013 [2014-11-10]. http://people.inf.ethz.ch/troscoe/pubs/cidr13-cod.pdf

[20]Zhang Y S, Jiao M, Wang Z W, et al. Multi-core vs I/O wall: The approaches to conquer and cooperate[C] //Proc of WAIM 2011. Berlin: Springer, 2011: 467-479

[21]TPC-H Homepage[EB/OL]. [2015-03-01]. http://www.tpc.org/tpch/default.asp

[22]O’Neil P, O’Neil B, Chen X D. Star schema benchmark[EB/OL]. (2009-06-05)[2014-12-23]. http://www.cs.umb.edu/～poneil/StarSchemaB.PDF

[23]TPC. TPC-DS homepage[EB/OL]. [2015-03-01]. http://www.tpc.org/tpcds/default.asp

[24]TPC. TPC-H top ten performance[EB/OL]. [2015-01-23]. http://www.tpc.org/tpch/results/tpch_perf_results.asp?resulttype=noncluster

[25]Giannikis G, Makreshanski D, Alonso G, et al. Shared workload optimization[J]. Proceedings of the VLDB Endowment, 2014, 7(6): 429-440

Zhang Yansong, born in 1973. Associate professor in Renmin University of China. His main research interests include main memory database, OLAP and cloud computing.

Jiao Min, born in 1975. Senior engineer in Renmin University of China. Her main research interests include main memory database, OLAP and cloud computing.

Zhang Yu, born in 1977. PhD, associate professor in National Satellite Meteorological China Meteorological Administration. Her main research interests include data warehouse, GPU database and OLAP(zyszy@ruc.edu.cn).

Wang Shan, born in 1944. Professor and PhD supervisor in Renmin University of China. Senior member of China Computer Federation. Her main research interests include high performance database, main memory database and data warehouse.

Concurrent In-Memory OLAP Query Optimization Techniques

Zhang Yansong1,2,3, Jiao Min1,2, Zhang Yu4, and Wang Shan1,2

1(Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), Ministry of Education, Beijing 100872)2(SchoolofInformation,RenminUniversityofChina,Beijing100872)3(NationalSurveyResearchCenter(RenminUniversityofChina),Beijing100872)4(NationalSatelliteMeteorologicalCenter,ChinaMeteorologicalAdministration,Beijing100081)

Recent researches not only focused on query-at-a-time query optimizations but also focused on group-at-a-time query optimizations due to the multicore hardware architecture support and highly concurrent workload requirements. By grouping concurrent queries into shared workload, some high latency operations, e.g., disk IO, cache line access, can be shared for multiple queries. The existing approaches commonly lie in sharing query operators such as scan, join or predicate processing, and try to generate an optimized global executing plan for all the queries. For complex analytical workloads, how to generate an optimized shared execution plan is a challenging issue. In this paper, we present a template OLAP execution plan for widely adopted star schema to simplify execution plan for maximizing operator utilization. Firstly, we present a surrogate key oriented join index to transform traditional key probing based join operation to array index referencing (AIR) lookup to make join CPU efficient and support a lazy aggregation. Secondly, the predicate processing of concurrent queries is simplified as cache line conscious predicate vector to maximize concurrent predicate processing within single cache line access. Finally, we evaluate the concurrent template OLAP (on-line analytical processing) processing with multicore parallel implementation under the star schema benchmark(SSB), and the results prove that the shared scan and predicate processing can double the concurrent OLAP query performance.

concurrent OLAP query processing; array index referencing (AIR); template OLAP query processing; join index; filtering vector

2015-06-30；

2015-10-13

國家“八六三”高技術研究發展計劃基金項目(2015AA015307)；中國人民大學科學研究基金(中央高?；究蒲袠I務費專項資金資助)項目(16XNLQ02) This work was supported by the National High Technology Research and Development Program of China (863 Program) (2015AA015307) and the Research Funds of Renmin University of China (the Fundamental Research Funds for the Central Universities) (16XNLQ02).

焦敏(shingle@ruc.edu.cn)

TP311.5