并發(fā)內(nèi)存OLAP查詢優(yōu)化技術(shù)研究

張延松 焦 敏 張 宇 王 珊

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

?

并發(fā)內(nèi)存OLAP查詢優(yōu)化技術(shù)研究

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

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

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

并發(fā)OLAP查詢處理；數(shù)組索引引用；模板OLAP查詢處理；連接索引；過濾向量

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

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

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

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

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

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

1 相關(guān)工作

1.1 內(nèi)存OLAP查詢優(yōu)化技術(shù)

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

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

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

1.2 并發(fā)OLAP查詢優(yōu)化技術(shù)

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

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

在共享操作符的并發(fā)OLAP查詢處理技術(shù)中，并發(fā)查詢處理的性能通常優(yōu)于一次一查詢執(zhí)行方式的性能，尤其在存在慢速磁盤IO的OLAP應(yīng)用場景中.內(nèi)存OLAP并發(fā)查詢處理時，不僅需要通過共享掃描減少表掃描的內(nèi)存訪問延遲，更重要的是通過并發(fā)查詢優(yōu)化技術(shù)減少星形連接過程的cache miss，即通過算法數(shù)據(jù)結(jié)構(gòu)的優(yōu)化在一個cache line miss中盡可能完成并發(fā)查詢的計算任務(wù).

Fig. 1 Multidimensional models of typical benchmarks.圖1 典型多維數(shù)據(jù)模型

2 并發(fā)OLAP查詢處理

2.1 AIR OLAP多維查詢處理

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

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

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

SSB是對TPC-H非規(guī)范化處理后的星形模型，使用單一的星形模式：(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個模式普遍遵循數(shù)據(jù)倉庫的代理鍵約束，除SSB的維表DATE主鍵為19920101,19920102,…,格式的連續(xù)日期外，其余所有維表主鍵均為從0或1開始的連續(xù)序列，當采用內(nèi)存列存儲時，維表主鍵可以直接映射為維表屬性列的數(shù)組下標地址，事實表記錄可以通過外鍵數(shù)組下標引用方式直接訪問內(nèi)存維屬性列對應(yīng)的記錄.

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

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

2.2 并發(fā)AIR OLAP多維查詢處理

在AIR OLAP算法中，多維過濾需要訪問各個維表位圖對應(yīng)位置并進行按位與運算.每次位圖訪問對應(yīng)1個cache line訪問，但僅使用512 b中的1 b.如圖3所示，我們以5個并發(fā)查詢?yōu)槔诓l(fā)AIR OLAP查詢處理時，維表過濾位圖轉(zhuǎn)換為維表過濾向量，5 b向量表示5個并發(fā)查詢在當前維表記錄上的謂詞處理結(jié)果，并發(fā)查詢Q0,Q1,Q2,Q3,Q4生成寬度為5 b的維表過濾向量.

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

2.3 并發(fā)AIR OLAP多維查詢處理實現(xiàn)技術(shù)

2.3.1 并發(fā)查詢預(yù)處理

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

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

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

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

2.3.2 并發(fā)連接過濾操作

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

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

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

2.3.3 并發(fā)分組聚集計算操作

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

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

2.3.4 多線程并發(fā)OLAP操作

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

2.3.5 AIR算法對不同模式的適應(yīng)性

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

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

3 實驗結(jié)果與分析

3.1 實驗環(huán)境配置

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

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

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

3.2 實驗測試結(jié)果和分析

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

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

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

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

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

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

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

Fig. 9 Average concurrent query execution time.圖9 并發(fā)查詢平均執(zhí)行時間

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

4 結(jié)束語

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

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

[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)(張延松, 焦敏, 王占偉, 等. 海量數(shù)據(jù)分析的One-size-fits-all OLAP技術(shù)[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

國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2015AA015307)；中國人民大學科學研究基金(中央高校基本科研業(yè)務(wù)費專項資金資助)項目(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