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

張延松 焦 敏 張 宇 王 珊

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

內(nèi)存列存儲(chǔ)支持基于偏移地址計(jì)算的直接內(nèi)存訪問，文獻(xiàn)[18]實(shí)現(xiàn)了數(shù)據(jù)倉庫中將事實(shí)表外鍵映射為維表內(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ù)載中，表掃描操作通常代價(jià)較高，基于共享掃描的并發(fā)查詢技術(shù)能夠更高效地利用順序訪問的內(nèi)存帶寬，同時(shí)服務(wù)于多個(gè)OLAP查詢處理任務(wù).Blink采用非規(guī)范化設(shè)計(jì)，將OLAP查詢轉(zhuǎn)換為單一的表掃描操作，實(shí)現(xiàn)了常量時(shí)間的查詢處理性能，同時(shí)支持基于共享掃描的并發(fā)查詢處理.Crescando通過索引運(yùn)行的查詢和共享掃描來支持可預(yù)期性能的查詢處理，MonetDBX100也提供了協(xié)同掃描機(jī)制以優(yōu)化動(dòng)態(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表，事實(shí)表循環(huán)掃描為每個(gè)事實(shí)表記錄依次通過每個(gè)Hash過濾器傳遞事實(shí)表記錄在每個(gè)過濾器上對每個(gè)并發(fā)查詢的過濾結(jié)果，實(shí)現(xiàn)一次Hash探測操作服務(wù)于多個(gè)并發(fā)查詢?nèi)蝿?wù).QPipe作為執(zhí)行代價(jià)較大的操作創(chuàng)建一直在線運(yùn)行的操作符，查詢進(jìn)入系統(tǒng)后通過代價(jià)估算連接上活動(dòng)的共享操作符，從操作符產(chǎn)生的數(shù)據(jù)流中獲取當(dāng)前查詢需要的結(jié)果.COD通過列存儲(chǔ)、水平分片策略，基于NUMA架構(gòu)在每個(gè)核心的數(shù)據(jù)分片上執(zhí)行Clock-Scan，連續(xù)掃描每個(gè)核心上數(shù)據(jù)集的水平分片.查詢首先進(jìn)入執(zhí)行隊(duì)列，按謂詞索引，掃描線程執(zhí)行數(shù)據(jù)分片上的順序掃描，完成查詢隊(duì)列的查詢?nèi)蝿?wù)，然后通過歸并和聚集線程將查詢結(jié)果推送到輸出隊(duì)列.文獻(xiàn)[20]實(shí)現(xiàn)了磁盤存儲(chǔ)事實(shí)表共享掃描、內(nèi)存DDTA-JOIN連接模式的并發(fā)OLAP查詢處理，在一個(gè)IO時(shí)間片內(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ā)查詢處理時(shí)，不僅需要通過共享掃描減少表掃描的內(nèi)存訪問延遲，更重要的是通過并發(fā)查詢優(yōu)化技術(shù)減少星形連接過程的cache miss，即通過算法數(shù)據(jù)結(jié)構(gòu)的優(yōu)化在一個(gè)cache line miss中盡可能完成并發(fā)查詢的計(jì)算任務(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ù)模型，即每一個(gè)事實(shí)數(shù)據(jù)F由多個(gè)維度(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)和暴風(fēng)雪(snow storm schema)模型.

TPC-H是一個(gè)滿足3NF的數(shù)據(jù)庫，存在共享多級(jí)維表，可以看作是一種雪花模型，也可以看作是3個(gè)子星形模式：(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個(gè)子星形模式：(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個(gè)模式普遍遵循數(shù)據(jù)倉庫的代理鍵約束，除SSB的維表DATE主鍵為19920101,19920102,…,格式的連續(xù)日期外，其余所有維表主鍵均為從0或1開始的連續(xù)序列，當(dāng)采用內(nèi)存列存儲(chǔ)時(shí)，維表主鍵可以直接映射為維表屬性列的數(shù)組下標(biāo)地址，事實(shí)表記錄可以通過外鍵數(shù)組下標(biāo)引用方式直接訪問內(nèi)存維屬性列對應(yīng)的記錄.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境配置

實(shí)驗(yàn)硬件平臺(tái)為一臺(tái)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測試集中，擴(kuò)展因子(scale factor,SF)為數(shù)據(jù)量單位，SF=1對應(yīng)事實(shí)表記錄數(shù)量為6 000 000.實(shí)驗(yàn)數(shù)據(jù)集設(shè)置多組，大小分別取SF為1，10，100、并發(fā)查詢數(shù)量分別為32，64，128，256，最大測試并發(fā)數(shù)量為1 024.

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

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

3.2 實(shí)驗(yàn)測試結(jié)果和分析

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

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

圖9顯示了基于維過濾位向量的AIR OLAP在數(shù)據(jù)集大小為SF=1，SF=10，SF=100時(shí)，不同并發(fā)線程數(shù)量時(shí)執(zhí)行的平均查詢時(shí)間.在實(shí)驗(yàn)中，線程內(nèi)并發(fā)查詢數(shù)量與線程數(shù)量相同，線程數(shù)量增長時(shí)，并發(fā)查詢數(shù)量也隨之增長，維過濾位圖寬度增長.圖9所示的查詢平均執(zhí)行時(shí)間中，當(dāng)線程(并發(fā)查詢)數(shù)量為512時(shí)具有最少的平均查詢執(zhí)行時(shí)間，主要原因是512個(gè)并發(fā)查詢對應(yīng)的維過濾位向量長度為512 b(64 B)，對應(yīng)一個(gè)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í)行時(shí)間

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

4 結(jié)束語

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

本文研究范圍定位于可以作為基礎(chǔ)操作符的星形模式下的共享OLAP查詢處理技術(shù)，可以作為通用OLAP查詢處理的基礎(chǔ)并發(fā)操作符.與Datapath，sharedDB，SWO[25]等技術(shù)相比，AIR OLAP算法首先基于數(shù)據(jù)倉庫模式分解為星形模式集合，在星形模式上應(yīng)用維過濾位向量技術(shù)優(yōu)化共享掃描與連接過濾操作，達(dá)到局部最佳共享OLAP處理性能，在多個(gè)星形操作符之間再進(jìn)行數(shù)據(jù)流共享優(yōu)化，簡化復(fù)雜模式下的并發(fā)查詢共享優(yōu)化技術(shù).在未來的工作中，我們將針對TPC-H和TPC-DS模式特點(diǎn)，研究多個(gè)共享操作符之間的協(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]. 計(jì)算機(jī)學(xué)報(bào), 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ā)展計(jì)劃基金項(xiàng)目(2015AA015307)；中國人民大學(xué)科學(xué)研究基金(中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助)項(xiàng)目(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