張延松 焦 敏 張 宇 王 珊

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

?

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

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

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

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

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

大內(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ù)庫(kù)和新一代數(shù)據(jù)庫(kù)一體機(jī)技術(shù)的代表.隨著互聯(lián)網(wǎng)用戶(hù)和互聯(lián)網(wǎng)業(yè)務(wù)的飛速發(fā)展，高負(fù)載的實(shí)時(shí)分析處理需求是數(shù)據(jù)庫(kù)需要面對(duì)的新技術(shù)挑戰(zhàn)，不僅要求數(shù)據(jù)庫(kù)引擎具有良好的實(shí)時(shí)查詢(xún)響應(yīng)性能，還要求數(shù)據(jù)庫(kù)引擎具有強(qiáng)大的查詢(xún)吞吐性能，能夠同時(shí)滿(mǎn)足成百上千的并發(fā)分析處理任務(wù).

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

2.1 AIR OLAP多維查詢(xún)處理

數(shù)據(jù)倉(cāng)庫(kù)不同于關(guān)系數(shù)據(jù)庫(kù)之處在于采用的是多維數(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ù)倉(cāng)庫(kù)中分別對(duì)應(yīng)雪花模型(snow-flake schema)、星形模型(star schema)和暴風(fēng)雪(snow storm schema)模型.

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

SSB是對(duì)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ù)倉(cāng)庫(kù)的代理鍵約束，除SSB的維表DATE主鍵為19920101,19920102,…,格式的連續(xù)日期外，其余所有維表主鍵均為從0或1開(kāi)始的連續(xù)序列，當(dāng)采用內(nèi)存列存儲(chǔ)時(shí)，維表主鍵可以直接映射為維表屬性列的數(shù)組下標(biāo)地址，事實(shí)表記錄可以通過(guò)外鍵數(shù)組下標(biāo)引用方式直接訪問(wèn)內(nèi)存維屬性列對(duì)應(yīng)的記錄.

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

Fig. 2 Dimensional bitmap filtering oriented AIR OLAP multidimensional query processing.圖2 基于維表位圖過(guò)濾的AIR OLAP多維查詢(xún)處理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

星形模型上的并發(fā)查詢(xún)基于共享事實(shí)表掃描和共享多維過(guò)濾計(jì)算，復(fù)雜的數(shù)據(jù)倉(cāng)庫(kù)模式，如雪花模型TPC-H、暴風(fēng)雪模型TPC-DS等可以看作是多個(gè)星形模式上的協(xié)同計(jì)算，各事實(shí)表之間同樣存在主-外鍵參照引用關(guān)系.在實(shí)踐中，涉及多事實(shí)表的查詢(xún)可以采用基于事實(shí)表間主-外鍵的AIR協(xié)同掃描技術(shù)完成并發(fā)OLAP查詢(xún)時(shí)多事實(shí)表間的共享掃描；當(dāng)查詢(xún)包含多個(gè)獨(dú)立星形結(jié)構(gòu)之間的協(xié)同查詢(xún)時(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位版，查詢(xún)數(shù)據(jù)集為Star Schema Benchmark[22].在SSB測(cè)試集中，擴(kuò)展因子(scale factor,SF)為數(shù)據(jù)量單位，SF=1對(duì)應(yīng)事實(shí)表記錄數(shù)量為6 000 000.實(shí)驗(yàn)數(shù)據(jù)集設(shè)置多組，大小分別取SF為1，10，100、并發(fā)查詢(xún)數(shù)量分別為32，64，128，256，最大測(cè)試并發(fā)數(shù)量為1 024.

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2015AA015307)；中國(guó)人民大學(xué)科學(xué)研究基金(中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(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