張延松,張宇,周恒,王珊

(1.中國(guó)人民大學(xué)DEKE實(shí)驗(yàn)室,北京100872; 2.中國(guó)人民大學(xué)信息學(xué)院,北京100872; 3.中國(guó)人民大學(xué)中國(guó)調(diào)查與數(shù)據(jù)中心,北京100872; 4.國(guó)家衛(wèi)星氣象中心,北京100081)

不對(duì)稱內(nèi)存計(jì)算平臺(tái)OLAP查詢處理技術(shù)研究

張延松1-3,張宇4,周恒1,2,王珊1,2

(1.中國(guó)人民大學(xué)DEKE實(shí)驗(yàn)室,北京100872; 2.中國(guó)人民大學(xué)信息學(xué)院,北京100872; 3.中國(guó)人民大學(xué)中國(guó)調(diào)查與數(shù)據(jù)中心,北京100872; 4.國(guó)家衛(wèi)星氣象中心,北京100081)

給出了一種面向當(dāng)前和未來(lái)不對(duì)稱內(nèi)存計(jì)算平臺(tái)的OLAP查詢處理技術(shù).不對(duì)稱內(nèi)存計(jì)算平臺(tái)是指配置有不同計(jì)算類型的處理器、不同存儲(chǔ)訪問(wèn)設(shè)備的計(jì)算機(jī),因此需要對(duì)OLAP查詢處理模型按不同的計(jì)算特點(diǎn)進(jìn)行優(yōu)化存儲(chǔ)配置和實(shí)現(xiàn)算法設(shè)計(jì),從而使OLAP查詢處理的不同階段更好地適應(yīng)相應(yīng)的存儲(chǔ)與計(jì)算設(shè)備的硬件特點(diǎn),提高硬件設(shè)備的利用率,更好地發(fā)揮硬件的性能.提出了3階段OLAP計(jì)算模型,將傳統(tǒng)基于迭代處理模型的OLAP查詢處理過(guò)程分解為計(jì)算密集型和數(shù)據(jù)密集型負(fù)載,分別由功能完備的通用處理器和并行計(jì)算能力強(qiáng)大的協(xié)處理器分而治之地完成,并最小化不同存儲(chǔ)與計(jì)算設(shè)備之間的數(shù)據(jù)傳輸代價(jià).實(shí)驗(yàn)結(jié)果表明基于負(fù)載劃分的3階段OLAP計(jì)算模型能夠較好地適應(yīng)CPU-Phi不對(duì)稱計(jì)算平臺(tái),實(shí)現(xiàn)通過(guò)計(jì)算型硬件加速計(jì)算密集型負(fù)載,從而加速整個(gè)OLAP查詢處理性能的目標(biāo).

內(nèi)存計(jì)算;不對(duì)稱計(jì)算平臺(tái);內(nèi)存聯(lián)機(jī)分析處理

0 引言

硬件技術(shù)的發(fā)展推動(dòng)數(shù)據(jù)庫(kù)技術(shù)的升級(jí).計(jì)算機(jī)硬件技術(shù)發(fā)展的一個(gè)重要反映是晶體管制造工藝水平的持續(xù)提高,晶體管制造工藝主要體現(xiàn)在CPU/GPU和內(nèi)存技術(shù)的進(jìn)步. CPU制造工藝從1971年的10 μm提升到2015年的14 nm,未來(lái)還將推出7 nm工藝.隨著CPU和GPU制造工藝的迅速提高,在單位面積的芯片上能夠集成更多的晶體管.晶體管集成技術(shù)的提升在處理器和內(nèi)存架構(gòu)設(shè)計(jì)上產(chǎn)生了巨大的影響.如圖1(a)-(f)所示,處理器在晶體管的集成技術(shù)的不同技術(shù)路線產(chǎn)生了不同類型的處理器.多核CPU采用了L1-L2-L3多級(jí)緩存結(jié)構(gòu),大量晶體管用于構(gòu)建控制電路與LLC(Last Level Cache),僅有5%左右用于計(jì)算單元ALU,主要通過(guò)高性能緩存加速數(shù)據(jù)訪問(wèn)性能,圖1(a)中間部分面積較大的晶體管單元為L(zhǎng)LC.當(dāng)前多核CPU已達(dá)到22個(gè)處理核心,55 MB LLC.協(xié)處理器(coprocessor,如圖1(b)和1(c))Cache較小,核心數(shù)量眾多但功能相對(duì)簡(jiǎn)單,大約40%的晶體管用于構(gòu)建計(jì)算單元,主要通過(guò)更多的并發(fā)線程來(lái)掩蓋內(nèi)存訪問(wèn)延遲.例如NVIDIA K80雙GK210核心采用28 nm工藝,集成的晶體管數(shù)量超過(guò)71億個(gè),每個(gè)GK210核心有2880個(gè)流處理器.代號(hào)Knights Landing的新一代Xeon Phi處理器采用14 nm工藝制造,擁有72億個(gè)晶體管,集成了72個(gè)x86核心,搭配16 GB MCDRAM緩存.

通用處理核心的復(fù)雜數(shù)據(jù)處理能力與大規(guī)模計(jì)算核心強(qiáng)大的并行計(jì)算能力相結(jié)合產(chǎn)生了融核設(shè)計(jì)思想.圖1(d)顯示了AMD融核架構(gòu)的APU結(jié)構(gòu),將多核處理器與GPU處理器集成到一個(gè)芯片上,使處理器同時(shí)具有兩種不同的計(jì)算特性.圖1(e)為下一代Intel Phi處理器Knight Landing的主處理器架構(gòu),由眾核處理器直接構(gòu)建主處理器,從而提供一個(gè)兼容x86架構(gòu)的高性能計(jì)算平臺(tái).下一代Xeon處理器將使用Xeon+FPGA的異構(gòu)計(jì)算模式[1](見(jiàn)圖1(f)),將FPGA集成到Xeon處理器內(nèi)部,提供定制的計(jì)算能力和更低的計(jì)算功耗.

存儲(chǔ)技術(shù)同樣隨著晶體管集成技術(shù)的發(fā)展而不斷進(jìn)步.圖1(h)為IBM的eXFlash DIMM內(nèi)存[2],提供了基于內(nèi)存插槽的非易失性大容量存儲(chǔ),為內(nèi)存計(jì)算提供了大容量持久存儲(chǔ)介質(zhì).圖1(i)顯示了3D內(nèi)存的基本結(jié)構(gòu),通過(guò)芯片堆疊技術(shù)顯著提升內(nèi)存的容量和帶寬性能,新一代采用3D芯片堆疊技術(shù)的內(nèi)存架構(gòu)相較于DDR3內(nèi)存速度有10倍的提升.圖1(j)顯示了Intel的3D XPointDIMM結(jié)構(gòu)[3],通過(guò)獨(dú)特的3D集成技術(shù)提供非易失、大容量、高性能存儲(chǔ),Q可用作SSD,也可用作新型非易失內(nèi)存.

圖1 不同類型的處理器與存儲(chǔ)技術(shù)Fig.1Different types of processors and memory technologies

硬件技術(shù)的飛速發(fā)展提供了多樣化的存儲(chǔ)與計(jì)算平臺(tái),也構(gòu)建了一個(gè)不對(duì)稱的內(nèi)存計(jì)算平臺(tái),即內(nèi)存計(jì)算面對(duì)的不僅是對(duì)稱的多核處理器和DRAM,而且包含了多核處理器、協(xié)處理器、融核處理器和DRAM內(nèi)存、非易失內(nèi)存、Flash閃存等性能特征存在顯著不同的異構(gòu)存儲(chǔ)與計(jì)算平臺(tái).硬件技術(shù)的發(fā)展與變化為內(nèi)存數(shù)據(jù)庫(kù)技術(shù)帶來(lái)的直接挑戰(zhàn)是如何將負(fù)載的特點(diǎn)與計(jì)算設(shè)備的特點(diǎn)相匹配,如何將不同訪問(wèn)類型的數(shù)據(jù)在不同訪問(wèn)特點(diǎn)的異構(gòu)存儲(chǔ)設(shè)備上進(jìn)行分布,從而實(shí)現(xiàn)負(fù)載本地計(jì)算的最大化,更好地發(fā)揮新型存儲(chǔ)和計(jì)算設(shè)備的性能.

本文探討了基于當(dāng)前和未來(lái)不對(duì)稱內(nèi)存計(jì)算平臺(tái)硬件特征的內(nèi)存OLAP查詢處理技術(shù),通過(guò)負(fù)載劃分將傳統(tǒng)的迭代處理模型分解為具有較強(qiáng)數(shù)據(jù)局部性的3階段計(jì)算模型,使不同階段的計(jì)算特征與負(fù)載特征、數(shù)據(jù)分布特征以及存儲(chǔ)和計(jì)算硬件特征相匹配,更好地適應(yīng)不對(duì)稱內(nèi)存計(jì)算平臺(tái)的特性,提高內(nèi)存OLAP查詢處理的性能與效率.本文第1節(jié)介紹了研究背景及相關(guān)工作,第2節(jié)給出了基于負(fù)載特征劃分的3階段內(nèi)存計(jì)算模型,第3節(jié)通過(guò)實(shí)驗(yàn)驗(yàn)證3階段內(nèi)存計(jì)算模型的性能特征,最后在第4節(jié)概括本文的工作.

1 研究背景和相關(guān)工作

1.1 研究背景

隨著硬件技術(shù)的發(fā)展,內(nèi)存計(jì)算平臺(tái)呈現(xiàn)多樣化的趨勢(shì).從處理器技術(shù)發(fā)展趨勢(shì)來(lái)看,通用的多核處理器結(jié)構(gòu)復(fù)雜、成本高昂、能耗顯著、核心集成數(shù)量較少,基于對(duì)稱同構(gòu)多核處理器的計(jì)算平臺(tái)在大規(guī)模實(shí)時(shí)分析處理領(lǐng)域?qū)⒅饾u被異構(gòu)非對(duì)稱的計(jì)算型處理器所取代.

圖2顯示了當(dāng)前和未來(lái)內(nèi)存計(jì)算平臺(tái)可能的技術(shù)選擇.位于主板的主處理器(host processor)能夠直接訪問(wèn)內(nèi)存,需要處理器能夠獨(dú)立運(yùn)行系統(tǒng).除傳統(tǒng)的通用多核CPU之外, AMD融核APU處理器在CPU中集成了具有較強(qiáng)并行計(jì)算能力的GPU,實(shí)現(xiàn)CPU與GPU對(duì)相同地址空間數(shù)據(jù)的直接訪問(wèn)與處理.Intel Phi下一代的Knights Landing采用Silvermont核心替代原來(lái)的P54C核心,可以作為主處理器使用,從而提供更加強(qiáng)大的內(nèi)存計(jì)算能力. FPGA在一些數(shù)據(jù)密集型負(fù)載中得到廣泛的應(yīng)用,如Netezza使用FPGA作為數(shù)據(jù)庫(kù)加速卡進(jìn)行前端數(shù)據(jù)流的簡(jiǎn)單、數(shù)據(jù)密集型處理.Intel未來(lái)的Xeon處理器中將集成FPGA,面向應(yīng)用定制處理器,提高處理器面向負(fù)載特征的性能.通過(guò)PCI-E通道連接的獨(dú)立協(xié)處理器,如Intel Xeon Phi、NVIDIA GPGPU、FPGA等具有強(qiáng)大的并行處理能力,通常具有較大的本地高帶寬內(nèi)存,但需要通過(guò)帶寬相對(duì)較低的PCI-E通道訪問(wèn)大容量?jī)?nèi)存,現(xiàn)階段主要的技術(shù)挑戰(zhàn)是協(xié)處理器強(qiáng)大的并行計(jì)算能力和PCI-E傳輸瓶頸之間的矛盾,未來(lái)的設(shè)備互聯(lián)技術(shù),如PCI-E 4.0、NVLink、Omni Path等技術(shù)能夠大幅度提高協(xié)處理器與CPU內(nèi)存或協(xié)處理器之間的數(shù)據(jù)傳輸性能,從而使協(xié)處理器強(qiáng)大的并行計(jì)算能力得到更好的發(fā)揮.

圖2 不對(duì)稱處理器與存儲(chǔ)技術(shù)Fig.2Asymmetric processor and storage technologies

從內(nèi)存層面來(lái)看,主存在現(xiàn)代3D內(nèi)存技術(shù)的支持下將獲得更大的容量、更高的帶寬以及非易失性,是內(nèi)存計(jì)算的重要高性能存儲(chǔ)設(shè)備.協(xié)處理器內(nèi)存通常為8-24 GB,一般作為協(xié)處理器的本地緩存使用,也可以作為計(jì)算密集型負(fù)載的駐留存儲(chǔ)和計(jì)算存儲(chǔ).PCI-E Flash閃存卡是一種大容量存儲(chǔ)設(shè)備,當(dāng)前能夠提供高達(dá)6.4TB的設(shè)備存儲(chǔ)容量,可以作為內(nèi)存計(jì)算的二級(jí)內(nèi)存使用,從而提高內(nèi)存計(jì)算的性價(jià)比.FPGA良好的集成性使其可以集成到大容量PCI-E Flash閃存卡中,從而實(shí)現(xiàn)將一部分?jǐn)?shù)據(jù)處理工作下推到最底層的數(shù)據(jù)存儲(chǔ)層.

硬件技術(shù)的日新月異為內(nèi)存數(shù)據(jù)庫(kù)技術(shù)提出很多技術(shù)挑戰(zhàn).內(nèi)存數(shù)據(jù)庫(kù)的算法設(shè)計(jì)以傳統(tǒng)的基于通用多核處理器多級(jí)cache硬件架構(gòu)為基礎(chǔ),但新興的計(jì)算型處理器通常采用大量處理核心、更高向量處理能力、較小cache的硬件架構(gòu),因此內(nèi)存數(shù)據(jù)庫(kù)在算法設(shè)計(jì)上需要從cache-conscious算法設(shè)計(jì)升級(jí)為architecture-conscious算法設(shè)計(jì),使內(nèi)存數(shù)據(jù)庫(kù)的關(guān)鍵算法設(shè)計(jì)能夠更好地適應(yīng)未來(lái)不同的處理器特點(diǎn).同時(shí),需要在內(nèi)存數(shù)據(jù)庫(kù)查詢處理模型的設(shè)計(jì)上改變以同構(gòu)內(nèi)存訪問(wèn)和計(jì)算為假設(shè)的思想,需要根據(jù)不對(duì)稱的計(jì)算與存儲(chǔ)資源特點(diǎn)對(duì)查詢處理任務(wù)進(jìn)行分解,將負(fù)載的特征、數(shù)據(jù)的特征與存儲(chǔ)和計(jì)算資源的特征相匹配,達(dá)到優(yōu)化資源配置,減少不同負(fù)載處理的耦合度,提高不對(duì)稱內(nèi)存計(jì)算性能和效率.

1.2 相關(guān)工作分析

雖然內(nèi)存數(shù)據(jù)庫(kù)已經(jīng)成為當(dāng)前數(shù)據(jù)庫(kù)的主流技術(shù),但對(duì)內(nèi)存數(shù)據(jù)庫(kù)核心算法的研究仍在繼續(xù),尤其以內(nèi)存連接算法研究為代表.從近年來(lái)的研究技術(shù)路線來(lái)看,一個(gè)熱點(diǎn)討論問(wèn)題是在現(xiàn)代處理器硬件架構(gòu)下,cache-oblivious還是cache-conscious能夠獲得更高的性能. cache-oblivious性能占優(yōu)意味著連接算法采用簡(jiǎn)單的設(shè)計(jì)并且對(duì)不同硬件平臺(tái)具有自動(dòng)適應(yīng)能力,cache-conscious性能占優(yōu)則意味著連接算法必須挖掘硬件特性以獲得更高的性能,算法復(fù)雜度相對(duì)較高.文獻(xiàn)［4］通過(guò)實(shí)驗(yàn)對(duì)比了cache-oblivious的無(wú)分區(qū)哈希連接算法與cache-conscious的radix分區(qū)哈希連接算法的性能,指出無(wú)分區(qū)哈希連接算法的主要代價(jià)集中在哈希探測(cè)產(chǎn)生的內(nèi)存訪問(wèn)代價(jià),可以通過(guò)現(xiàn)代處理器支持的并發(fā)多線程和自動(dòng)預(yù)取機(jī)制提高性能；radix分區(qū)哈希連接算法的主要代價(jià)集中在radix分區(qū)過(guò)程,時(shí)間和空間代價(jià)均較高,但哈希探測(cè)性能較高.文獻(xiàn)［5］進(jìn)一步優(yōu)化了［4］的算法設(shè)計(jì),通過(guò)SIMD等硬件技術(shù)進(jìn)一步優(yōu)化算法性能,從而使radix分區(qū)哈希連接算法優(yōu)于無(wú)分區(qū)哈希連接算法,證明了基于硬件特性的優(yōu)化技術(shù)仍然能夠帶來(lái)更高的性能.文獻(xiàn)［6］通過(guò)SIMD技術(shù)對(duì)排序歸并算法和哈希算法進(jìn)行優(yōu)化,radix分區(qū)哈希連接算法的綜合性能最優(yōu),證明了radix分區(qū)哈希連接算法的優(yōu)勢(shì).

內(nèi)存數(shù)據(jù)庫(kù)的算法研究同樣延伸到眾核協(xié)處理器平臺(tái).在文獻(xiàn)［7］中,radix連接的radix分區(qū)操作在CPU端執(zhí)行,分區(qū)后的數(shù)據(jù)傳輸?shù)紾PU端,通過(guò)nested loop或二分查找算法完成分區(qū)數(shù)據(jù)上的連接操作.GPU相對(duì)CPU擁有大量的核心與硬件級(jí)并發(fā)線程,內(nèi)存訪問(wèn)的優(yōu)化不同于CPU通過(guò)cache緩存減少內(nèi)存訪問(wèn)延遲,而是通過(guò)大量并發(fā)內(nèi)存訪問(wèn)線程掩蓋內(nèi)存訪問(wèn)延遲,因此更加適合cache-oblivious的無(wú)分區(qū)哈希連接算法[8,9].文獻(xiàn)［10］進(jìn)一步探索了基于融核APU上的查詢優(yōu)化技術(shù),通過(guò)協(xié)同CPU與GPU核心的任務(wù)調(diào)度和優(yōu)化不同內(nèi)核之間的數(shù)據(jù)共享訪問(wèn)提高查詢處理性能.相對(duì)于GPU需要用CUDA或OpenCL對(duì)算法重寫(xiě),Xeon Phi由于其與x86兼容的指令系統(tǒng)而更容易從CPU平臺(tái)遷移到Xeon Phi協(xié)處理器平臺(tái).文獻(xiàn)［11］將文獻(xiàn)［5］提供的開(kāi)源哈希算法優(yōu)化為Xeon Phi版本并進(jìn)行測(cè)試,實(shí)驗(yàn)結(jié)果表明Xeon Phi的眾多核心和更多的線程能夠有效地降低內(nèi)存訪問(wèn)延遲,cache-oblivious的無(wú)分區(qū)哈希連接算法較CPU平臺(tái)有較大的性能提升,甚至優(yōu)于radix分區(qū)哈希連接算法的性能.最新的研究[12]對(duì)算法再次進(jìn)行全面的SIMD優(yōu)化設(shè)計(jì),挖掘了Xeon Phi 512位向量處理能力,進(jìn)一步優(yōu)化了算法在Xeon Phi端的性能,并使radix分區(qū)哈希連接算法再次優(yōu)于無(wú)分區(qū)哈希連接算法.值得注意的是,Xeon Phi與CPU具有類似的L1-L2 cache結(jié)構(gòu),因此經(jīng)過(guò)充分優(yōu)化后具有與CPU類似的性能特征.但radix分區(qū)哈希連接算法需要雙倍的內(nèi)存空間來(lái)支持對(duì)兩個(gè)連接表的radix分區(qū)操作,降低了Xeon Phi協(xié)處理器有限內(nèi)存的利用率.內(nèi)存哈希連接算法的研究同樣擴(kuò)展到FPGA平臺(tái)[13],FPGA相對(duì)于CPU支持更深的流水線和數(shù)以千計(jì)的并發(fā)內(nèi)存訪問(wèn)線程,不借助cache機(jī)制而達(dá)到較高的內(nèi)存訪問(wèn)性能,在相似內(nèi)存帶寬性能的CPU和FPGA平臺(tái)上基于文獻(xiàn)［5］的兩種內(nèi)存哈希算法較CPU平臺(tái)有成倍的性能提升.除通用的內(nèi)存哈希連接算法之外,文獻(xiàn)［14］研究了OLAP中基于主-外鍵參照完整性約束關(guān)系和代理鍵機(jī)制[15]的外鍵連接優(yōu)化技術(shù),通過(guò)對(duì)OLAP模式的分析提出了代理鍵地址映射機(jī)制,并基于數(shù)組存儲(chǔ)模型設(shè)計(jì)了以維代理向量參照地址訪問(wèn)為基礎(chǔ)的數(shù)組地址參照訪問(wèn)AIR算法,并通過(guò)Benchmark測(cè)試驗(yàn)證了其較好的性能.AIR算法是一種依賴簡(jiǎn)單數(shù)組存儲(chǔ)和數(shù)組地址訪問(wèn)操作的外鍵連接算法,算法效率高并且易于向協(xié)處理器平臺(tái)遷移.

哈希連接是內(nèi)存數(shù)據(jù)庫(kù)最重要的算法,也是內(nèi)存OLAP性能決定性的操作符.連接操作性能優(yōu)化技術(shù)研究的一個(gè)顯著趨勢(shì)是借助先進(jìn)硬件的性能獲得提升,需要使算法設(shè)計(jì)與硬件特點(diǎn)相匹配.在未來(lái)的處理器技術(shù)中,Intel Xeon Phi KNL可以將整個(gè)板上內(nèi)存用作16 GB的L3 cache,提高了cache-oblivious算法優(yōu)化的應(yīng)用范圍,而NVIDIA GPGPU、FPGA等處理器則更加注重大規(guī)模并發(fā)線程的內(nèi)存訪問(wèn)性能,因此,在內(nèi)存連接算法的研究上不能完全依賴cache-oblivious或者cache-conscious設(shè)計(jì),而要使算法具有對(duì)不同類型硬件平臺(tái)的適應(yīng)性,提高內(nèi)存利用率,優(yōu)化內(nèi)存隨機(jī)訪問(wèn)性能.

2 不對(duì)稱內(nèi)存計(jì)算平臺(tái)OLAP查詢優(yōu)化技術(shù)

處理器和存儲(chǔ)技術(shù)的分化產(chǎn)生了不對(duì)稱的內(nèi)存計(jì)算平臺(tái),查詢處理的整個(gè)過(guò)程被物理地分配給不同硬件性能特點(diǎn)的存儲(chǔ)設(shè)備和處理器,因此,如何減少數(shù)據(jù)在不同處理器和存儲(chǔ)設(shè)備之間的傳輸代價(jià)、使查詢負(fù)載適合不同的處理器計(jì)算特性對(duì)于提高不對(duì)稱內(nèi)存計(jì)算平臺(tái)的性能和效率具有重要的意義.

2.1 內(nèi)存OLAP不對(duì)稱存儲(chǔ)模型

OLAP模型是一種多維數(shù)據(jù)模型,由數(shù)量眾多但數(shù)據(jù)量極小的維表和巨大的事實(shí)表構(gòu)成,維表由主鍵和代表維層次等屬性的描述性字段構(gòu)成,事實(shí)表由維表外鍵和代表數(shù)量關(guān)系的度量屬性組成.

圖3 SSB不同類型數(shù)據(jù)量和查詢時(shí)間占比Fig.3Proportions of Different Datasets and Processing Time of Star Schema Benchmark

以SSB數(shù)據(jù)集為例(SF=100,事實(shí)表包含600 000 000記錄),如圖3所示,四個(gè)維表數(shù)據(jù)量占比為0.86%,事實(shí)表外鍵數(shù)據(jù)量占比為19.34%,事實(shí)表度量列數(shù)據(jù)量占比為79.80%；在［14］中基于AIR算法的維表處理、外鍵連接和聚集計(jì)算三個(gè)階段執(zhí)行時(shí)間占比分別為7.11%、86.43%和6.46%.20%的外鍵列上的計(jì)算代價(jià)超過(guò)OLAP查詢總代價(jià)的80%,而這部分外鍵連接操作適合通過(guò)新興的計(jì)算型處理器進(jìn)行加速,較小的外鍵通常能夠?qū)崿F(xiàn)協(xié)處理器內(nèi)存駐留存儲(chǔ),從而最小化內(nèi)存與協(xié)處理器之間的PCI-E數(shù)據(jù)傳輸代價(jià).以SSB數(shù)據(jù)集為例,在SF=100的數(shù)據(jù)集中四個(gè)外鍵列大小為9.6 GB,小于主流Xeon Phi與GPGPU的16 GB和24 GB內(nèi)存,也就是說(shuō)一個(gè)協(xié)處理器可以支持SF=100的OLAP外鍵存儲(chǔ)和其上的連接加速任務(wù).

在內(nèi)存OLAP應(yīng)用中,維表數(shù)據(jù)量和其上的選擇、投影、分組等操作執(zhí)行時(shí)間較短,維表可采用內(nèi)存存儲(chǔ)或閃存存儲(chǔ).事實(shí)表外鍵相對(duì)于度量列較小,但其上的外鍵連接操作占OLAP查詢時(shí)間的比重最高,屬于計(jì)算密集型負(fù)載,需要將其駐留存儲(chǔ)于最接近計(jì)算單元的存儲(chǔ)設(shè)備中,如協(xié)處理器內(nèi)存或主存.事實(shí)表度量列數(shù)據(jù)量最大,但其上的聚集計(jì)算執(zhí)行時(shí)間較短,屬于數(shù)據(jù)密集型負(fù)責(zé),可以將其存于閃存等低成本、大容量存儲(chǔ)設(shè)備中以提高內(nèi)存OLAP查詢處理的性價(jià)比.

2.2 內(nèi)存OLAP三階段計(jì)算模型

我們以數(shù)據(jù)為中心,將OLAP查詢處理分解為三個(gè)獨(dú)立的計(jì)算階段.第一階段是維表處理階段,將OLAP查詢中維表上的選擇、投影、分組操作應(yīng)用在維表上,生成分組投影向量,并對(duì)分組投影向量采用輕量字典表壓縮,將投影出的分組成員存儲(chǔ)在數(shù)組字典表中,數(shù)組下標(biāo)作為壓編碼更新到分組投影向量中.第二階段是事實(shí)表外鍵列計(jì)算階段,事實(shí)表外鍵與維表投影向量執(zhí)行外鍵連接操作,與分組投影向量連接的結(jié)果存儲(chǔ)在度量向量中,記錄每個(gè)事實(shí)表記錄是否滿足連接條件及相應(yīng)的多維形式的分組編碼.第三階段通過(guò)度量向量在事實(shí)表度量列上執(zhí)行分組聚集計(jì)算,度量向量起到位圖索引的作用,按位置訪問(wèn)OLAP查詢相關(guān)的度量屬性列,并根據(jù)度量向量中存儲(chǔ)的多維分組編碼進(jìn)行聚集計(jì)算.三個(gè)計(jì)算階段之間輸入與輸出的是較小的維表分組投影向量和事實(shí)表度量向量,在數(shù)據(jù)按存儲(chǔ)和計(jì)算設(shè)備劃分時(shí)能夠最小化不同計(jì)算任務(wù)之間的數(shù)據(jù)傳輸代價(jià).

在維表處理階段,我們使用基于代理鍵的外鍵連接技術(shù).在數(shù)據(jù)倉(cāng)庫(kù)中具有主-外鍵參照完整性約束關(guān)系的被參照表中使用代理鍵[15]作為主鍵,然后更新外鍵為代理外鍵.OLAP查詢?cè)诰S表上的操作生成代理向量,即以代理鍵為偏移地址的向量,外鍵連接操作轉(zhuǎn)化為向代理向量的地址映射訪問(wèn),即文獻(xiàn)［14］所述的AIR算法.我們進(jìn)一步放松了文獻(xiàn)［14］中基于數(shù)組存儲(chǔ)的強(qiáng)約束條件,通過(guò)邏輯代理鍵保持被參照表主鍵邏輯地址映射特性,解決了數(shù)據(jù)庫(kù)異位更新機(jī)制(out-of-place update)導(dǎo)致的代理鍵與物理偏移地址不對(duì)應(yīng)問(wèn)題.圖4顯示了邏輯代理鍵映射機(jī)制的實(shí)例,其中surrogate key列為邏輯代理鍵列,數(shù)據(jù)庫(kù)只需要維護(hù)代理鍵唯一、連續(xù)分配,并不需要保持物理存儲(chǔ)順序.查詢結(jié)果輸出為代理向量,即以邏輯代理鍵為下標(biāo)的向量,投影操作的結(jié)果映射到邏輯代理鍵值對(duì)應(yīng)的向量單元中,由代理向量與外鍵列完成基于代理鍵地址映射的外鍵連接操作.

圖4 邏輯代理鍵映射Fig.4Logical surrogate key mapping

OLAP查詢?cè)诰S表上按WHERE子句投影出GROUP BY子句對(duì)應(yīng)的分組屬性作為代理向量,代理向量中的空值代表對(duì)應(yīng)邏輯代理鍵記錄不滿足WHERE謂詞條件,非空值作為當(dāng)前維上輸出的分組屬性分量.代理向量通過(guò)字典表數(shù)據(jù)壓縮將OLAP查詢投影出的分組向量進(jìn)一步壓縮,通過(guò)數(shù)組字典表存儲(chǔ)代理向量中的分組值,以分組字典數(shù)組下標(biāo)作為代理向量壓縮編碼.在SSB和TPC-H大部分OLAP查詢中分組為低勢(shì)集,維表上的代理向量通?？梢詨嚎s為int 8類型(表示28-1個(gè)分組).由于維表較小且涉及復(fù)雜的數(shù)據(jù)類型、函數(shù)及表達(dá)式處理,維表處理階段由CPU負(fù)載,并輸出經(jīng)過(guò)字典表壓縮后的分組投影向量.

在事實(shí)表外鍵列計(jì)算階段,基于代理鍵地址引用訪問(wèn)的AIR算法將哈希連接算法簡(jiǎn)化為外鍵向代理向量的地址映射訪問(wèn),從而消除了復(fù)雜的哈希表設(shè)計(jì),提高了AIR算法的代碼執(zhí)行效率,并且易于向GPU、Xeon Phi、FPGA等復(fù)雜數(shù)據(jù)管理能力弱、并行計(jì)算能力強(qiáng)大的協(xié)處理器進(jìn)行部署.圖5描述了在不對(duì)稱內(nèi)存計(jì)算平臺(tái)上的外鍵連接實(shí)現(xiàn)策略.當(dāng)協(xié)處理器為主處理器或者與CPU訪問(wèn)相同的內(nèi)存地址空間時(shí),由并行計(jì)算能力更加強(qiáng)大的協(xié)處理器(如APU中的GPU單元、Xeon Phi KNL主處理器、FPGA、Xeon+FPGA中的FPGA單元等)執(zhí)行事實(shí)表外鍵連接操作,并生成度量向量.度量向量由各維代理向量分組壓縮編碼構(gòu)造的多維數(shù)組地址編碼構(gòu)成,通過(guò)多維地址編碼進(jìn)一步壓縮多分組屬性存儲(chǔ)空間.

圖5 基于代理鍵參照訪問(wèn)的外鍵連接實(shí)現(xiàn)Fig.5Surrogate key referencing oriented foreign key join implementation

當(dāng)協(xié)處理器為PCI-E加速卡時(shí),如NVIDIA GPGPU、Xeon Phi、FPGA加速卡等,我們將PCI-E加速卡的本地內(nèi)存作為外鍵列存儲(chǔ)器,加速OLAP的外鍵連接操作.對(duì)于給定的OLAP數(shù)據(jù)集,PCI-E加速卡加速全部外鍵連接操作所需要的內(nèi)存大小為,其中wi表示n個(gè)外鍵寬度及度量向量寬度,R表示外鍵列行數(shù).當(dāng)數(shù)據(jù)集較大時(shí),可以根據(jù)需求配置多個(gè)加速卡實(shí)現(xiàn)計(jì)算密集型外鍵連接操作的內(nèi)存計(jì)算.較小的維代理向量在OLAP查詢執(zhí)行時(shí)由CPU通過(guò)PCI-E通道傳輸?shù)郊铀倏▋?nèi)存執(zhí)行外鍵連接操作,生成度量向量通過(guò)PCI-E通道傳輸回CPU內(nèi)存,完成后續(xù)的聚集計(jì)算,或者由協(xié)處理器基于度量向量通過(guò)PCI-E卡間的通道訪問(wèn)PCI-E Flash閃存卡完成聚集計(jì)算任務(wù).

在聚集計(jì)算階段,度量向量中存儲(chǔ)的多維數(shù)組壓縮編碼可以作為分組鍵值執(zhí)行哈希分組聚集計(jì)算；當(dāng)多維分組壓縮編碼較小時(shí),即多個(gè)分組壓縮編碼所構(gòu)建的多維數(shù)組較小(通常低于LLC slice,即2.5 MB,支持655 360個(gè)int類型分組聚集結(jié)果)時(shí),可以使用多維數(shù)組進(jìn)行聚集計(jì)算,度量向量中存儲(chǔ)的多維數(shù)組壓縮編碼直接映射為多維數(shù)組下標(biāo).

當(dāng)在PCI-E大容量Flash閃存卡上集成了FPGA時(shí),可以進(jìn)一步將聚集計(jì)算階段下推到Flash閃存卡的FPGA單元中.度量向量傳輸?shù)紽lash閃存卡,由嵌入式FPGA根據(jù)度量向量按位置訪問(wèn)度量列并執(zhí)行基于多維數(shù)組的分組聚集計(jì)算,減少度量列在PCI-E通道的傳輸代價(jià).在聚集計(jì)算算法設(shè)計(jì)中只使用向量和多維數(shù)組,算法易于在FPGA中實(shí)現(xiàn).

2.3 不對(duì)稱內(nèi)存計(jì)算平臺(tái)OLAP查詢處理基本策略

通過(guò)前面的算法設(shè)計(jì),我們實(shí)現(xiàn)了OLAP模式中具有典型的復(fù)雜數(shù)據(jù)管理特征的維表、具有計(jì)算密集型處理特征的事實(shí)表外鍵列、具有數(shù)據(jù)密集型訪問(wèn)特征的事實(shí)表度量列在不同存儲(chǔ)層次上的分布以及與數(shù)據(jù)相關(guān)的計(jì)算負(fù)載在不同處理單元上的分布,將負(fù)載的特征與處理單元的特征相結(jié)合,計(jì)算密集型的外鍵連接操作由并行計(jì)算能力強(qiáng)大的協(xié)處理器完成,從而實(shí)現(xiàn)通過(guò)硬件加速卡加速OLAP關(guān)鍵操作性能的目標(biāo).

本文提出的3階段計(jì)算模型的意義是將OLAP查詢中數(shù)據(jù)量占比20%但計(jì)算量占比80%的計(jì)算密集型外鍵連接負(fù)載獨(dú)立出來(lái),并通過(guò)代理鍵索引機(jī)制簡(jiǎn)化外鍵連接算法,使其更易于部署在協(xié)處理器上進(jìn)行加速.三個(gè)計(jì)算階段之間通過(guò)簡(jiǎn)單的向量數(shù)據(jù)結(jié)構(gòu)進(jìn)行驅(qū)動(dòng), Q減少了數(shù)據(jù)傳輸量,也簡(jiǎn)化了后續(xù)計(jì)算的復(fù)雜度.基于度量向量的聚集計(jì)算將位圖索引訪問(wèn)和多維數(shù)組聚集計(jì)算結(jié)合起來(lái),簡(jiǎn)化算法設(shè)計(jì),使之更加易于部署在嵌入式FPGA等芯片中而集成到Flash卡中,實(shí)現(xiàn)存儲(chǔ)設(shè)備上的計(jì)算.

簡(jiǎn)化每個(gè)階段的數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì),將查詢處理過(guò)程解耦合為向量驅(qū)動(dòng)的獨(dú)立計(jì)算過(guò)程等優(yōu)化技術(shù)可以根據(jù)不對(duì)稱內(nèi)存計(jì)算平臺(tái)的資源靈活分配不同的負(fù)載任務(wù),提高存儲(chǔ)和計(jì)算資源的利用率,更好地利用硬件加速器提升關(guān)鍵計(jì)算性能,優(yōu)化OLAP查詢性能.

3 實(shí)驗(yàn)分析

不對(duì)稱內(nèi)存計(jì)算平臺(tái)查詢優(yōu)化技術(shù)的核心是通過(guò)眾核協(xié)處理器的高并行處理性能加速OLAP查詢中最為關(guān)鍵的外鍵連接操作的性能,從而起到通過(guò)硬件協(xié)同處理加速OLAP整體性能的效果.我們?cè)谖墨I(xiàn)［16］已驗(yàn)證基于GPU的3階段OLAP計(jì)算模型的性能,其性能的決定因素為事實(shí)表外鍵連接性能.

為驗(yàn)證眾核協(xié)處理器對(duì)外鍵連接操作的加速效率,我們?cè)谝慌_(tái)DELL PowerEdge R730服務(wù)器上進(jìn)行外鍵連接算法測(cè)試,服務(wù)器配置有2塊Intel Xeon E5-2650 v3@2.30 GHz 10核CPU,共20個(gè)核心,40個(gè)線程,512 GB DDR3內(nèi)存.操作系統(tǒng)為CentOS,Linux版本為2.6.32-431.el6.x86 64,gcc版本為4.4.7.服務(wù)器配置了一塊Intel Xeon Phi 5110P@1.053 GHz協(xié)處理器,其中集成了60個(gè)核心,每核心支持4線程,共計(jì)240線程,Phi 5110P協(xié)處理配置有8 GB內(nèi)存,協(xié)處理器內(nèi)置操作系統(tǒng)的Linux版本為2.6.38.8+mpss3.3,gcc版本為4.7.0.服務(wù)器還配置了一塊NVIDIA K80 GPU加速卡,K80擁有4992 cuda核心和24 GB GDDR5顯存,顯存帶寬達(dá)到480 GB/s.

我們?cè)谖墨I(xiàn)［5］提供的開(kāi)源NPO、PRO算法的基礎(chǔ)上增加了AIR算法.在數(shù)據(jù)生成器中屏蔽了對(duì)R表的shuffler過(guò)程,使R表使用代理鍵作為主鍵,S表需要進(jìn)行shuffler過(guò)程,使之符合主-外鍵約束的一般場(chǎng)景.AIR算法實(shí)現(xiàn)中模擬了R表上的謂詞操作,在NPO算法的BUILD過(guò)程對(duì)R表進(jìn)行過(guò)濾,生成R表代理向量,然后S表根據(jù)主鍵映射到R表代理向量,完成連接操作.AIR算法生成的R表代理向量可以使用不同的數(shù)據(jù)類型,如int 8、int 16或int 32,根據(jù)對(duì)SSB、TPC-H等查詢中維表分組投影的分析,我們主要使用int 8作為過(guò)濾器數(shù)據(jù)類型,模擬維過(guò)濾位圖及分組向量存儲(chǔ).在實(shí)驗(yàn)中R表和S表采用int 32數(shù)據(jù)類型key和payload,key的值域(232-1)能夠滿足數(shù)據(jù)倉(cāng)庫(kù)維表主鍵的取值范圍,考慮到內(nèi)存數(shù)據(jù)庫(kù)普遍采用數(shù)據(jù)壓縮技術(shù),我們?cè)趯?shí)驗(yàn)中并未使用int 64數(shù)據(jù)類型.我們?cè)跍y(cè)試中對(duì)比2塊Xeon CPU與1塊Xeon Phi協(xié)處理器的性能,CPU端算法測(cè)試設(shè)置為40線程,Xeon Phi端算法測(cè)試設(shè)置為240線程.

3.1 測(cè)試數(shù)據(jù)集

我們首先對(duì)比了文獻(xiàn)［5］使用的Workload A和B,其數(shù)據(jù)集對(duì)應(yīng)的連接表R和S的設(shè)置如表1所示.我們將Workload A和B中的key與payload數(shù)據(jù)寬度統(tǒng)一設(shè)置為4字節(jié),能夠滿足OLAP應(yīng)用中主鍵的值域和基于壓縮技術(shù)的數(shù)據(jù)存儲(chǔ)需求.

表1 參考負(fù)載測(cè)試集Tab.1Referenced workloads dataset

為更好地分析不同的外鍵連接算法在內(nèi)存OLAP中的性能,我們模擬典型OLAP Benchmark中的外鍵連接操作,選用的數(shù)據(jù)集為SSB、TPC-H和TPC-DS中相應(yīng)的外鍵連接操作,包括維表與事實(shí)表之間的外鍵連接操作以及具有主-外鍵參照完整性約束關(guān)系的事實(shí)表之間的外鍵連接操作,數(shù)據(jù)集大小設(shè)置為SF=100,對(duì)應(yīng)TPC-H網(wǎng)站官方測(cè)試的最小數(shù)據(jù)集.各數(shù)據(jù)集中連接表的記錄行數(shù)如表2所示.

表2 基準(zhǔn)測(cè)試數(shù)據(jù)集Tab.2Datasets for benchmark testing

3.2 外鍵連接性能測(cè)試結(jié)果分析

由于Intel Xeon E5-2650 v3與Intel Xeon Phi 5110P的主頻不同,因此我們以納秒每記錄(ns/tuple)作為性能指標(biāo).

圖6顯示了AIR、NPO和PRO外鍵連接算法在CPU和Xeon Phi端的執(zhí)行性能,其中無(wú)分區(qū)哈希連接算法NPO的主要代價(jià)是共享哈希表內(nèi)存訪問(wèn),Xeon Phi的并發(fā)多線程內(nèi)存訪問(wèn)機(jī)制能夠提高內(nèi)存訪問(wèn)性能,因此NPO的性能在Xeon Phi端較高；PRO算法依賴于cache大小進(jìn)行優(yōu)化,CPU具有更高的每核心cache大小,而Xeon Phi上有更高的并發(fā)處理線程,總體來(lái)看,其性能在CPU端和Xeon Phi端差距不大；AIR算法中的代理向量較小,CPU較大的cache能夠較好地加速其性能,當(dāng)R表較小時(shí),CPU較大的cache使AIR算法在CPU端的性能優(yōu)于Xeon Phi端,當(dāng)R表較大時(shí),CPU的cache緩存優(yōu)化和Xeon Phi的多線程優(yōu)化具有類似的性能.需要注意的是,我們?cè)趯?shí)驗(yàn)中使用2塊Xeon 10核處理器與1塊Xeon Phi 60核協(xié)處理器進(jìn)行性能對(duì)比,單Xeon Phi協(xié)處理器的性能與2塊Xeon 10核處理器持平.

圖6 外鍵連接算法性能對(duì)比Fig.6Performance comparison for foreign key join algorithms

圖7顯示了SSB和TPC-H基準(zhǔn)中各外鍵連接操作在CPU和Xeon Phi上的性能對(duì)比.首先,AIR使用代理向量的內(nèi)存開(kāi)銷低于NPO算法中的哈希表,因此能夠支持全部測(cè)試,而NPO在TPC-H中較大的連接表時(shí)超出Xeon Phi的內(nèi)存而不能執(zhí)行,PRO算法的raidx分區(qū)操作需要2倍的內(nèi)存空間,在SSB和TPC-H測(cè)試中超出內(nèi)存容量而不能執(zhí)行測(cè)試.從算法內(nèi)存效率來(lái)看,AIR優(yōu)于NPO,NPO優(yōu)于PRO.其次,從算法性能來(lái)看,SSB數(shù)據(jù)集中維表較小,更適合CPU較大cache上的優(yōu)化,因此AIR算法與NPO算法在CPU上的性能優(yōu)于Xeon Phi上的性能.TPC-H除supplier表較小外其他表均較大,在大表連接時(shí)Xeon Phi的性能優(yōu)于CPU.

圖7 SSB、TPC-H基準(zhǔn)外鍵連接算法性能對(duì)比Fig.7Performance comparison for foreign key join algorithmsin SSB and TPC-H

TPC-DS相對(duì)于SSB和TPC-H有更多的維表,但維表記錄數(shù)量較少且記錄增長(zhǎng)緩慢.AIR算法的代理向量通常低于L2 cache,因此Xeon Phi與CPU都有較好的cache訪問(wèn)性能,Xeon Phi更多的線程使AIR算法的性能優(yōu)于CPU.NPO算法在較少和中等記錄量時(shí)CPU的性能優(yōu)于Xeon Phi,在較大記錄量時(shí)Xeon Phi的性能優(yōu)于CPU.PRO算法在CPU端的性能略優(yōu)于Xeon Phi端的性能,CPU較大的cache和較高的主頻更加有利于PRO算法性能的提高.

總體來(lái)說(shuō),AIR算法在較小維表時(shí)在Xeon Phi有較好的加速性能,PRO算法在Xeon Phi上也有接近一倍的性能提升(圖7和圖8中1塊Xeon Phi與2塊Xeon多核CPU性能接近).在當(dāng)前PCI-E形式的Xeon Phi協(xié)處理器中,AIR算法更適合較小維表對(duì)應(yīng)的外鍵連接操作,不僅維表代理向量傳輸代價(jià)低,而且能夠獲得較高的性能收益,當(dāng)維表較大時(shí),AIR算法更適合在CPU平臺(tái)上執(zhí)行.NPO算法則適合于較大維表的外鍵連接操作,但維表子集在PCI-E通道傳輸代價(jià)也相應(yīng)較高.PRO算法雖然加速性比較穩(wěn)定,但其2倍的內(nèi)存空間消耗降低了Xeon Phi協(xié)處理器內(nèi)存的利用率.未來(lái)Xeon Phi KNL主處理器可以直接訪問(wèn)內(nèi)存數(shù)據(jù),更加適合較大表的外鍵連接操作加速.

圖8 TPC-DS外鍵連接算法性能對(duì)比Fig.8Performance comparison for foreign key join algorithms in TPC-DS

圖9 NVIDIA GPGPU K80外鍵連接算法性能對(duì)比Fig.9Performance comparison for foreign key join algorithms on NVIDIA GPGPU K80

我們用CUDA語(yǔ)言實(shí)現(xiàn)AIR算法,并在最新的NVIDIA GPGPU K80上執(zhí)行以上各Benchmark的外鍵連接性能測(cè)試.K80使用了4992個(gè)流處理器,具有極強(qiáng)的并行處理能力.圖9列出了本文所使用的SSB、TPC-H、TPC-DS、Workloads等Benchmark中的外鍵連接操作使用AIR算法(CPU)、AIR算法(Phi)、NPO(Phi)、PRO(Phi)以及AIR算法(GPU)時(shí)的查詢執(zhí)行總時(shí)間,其中AIR算法(GPU)執(zhí)行時(shí)間極短,我們使用了另一個(gè)較小的坐標(biāo)軸標(biāo)示其外鍵連接執(zhí)行時(shí)間.圖9中可以看到,AIR算法在2塊10核Xeon E5-2650 v3CPU上與1塊Xeon Phi 5110P協(xié)處理器上具有較好的外鍵連接執(zhí)行性能,均低于哈希連接算法NPO和PRO在Xeon Phi協(xié)處理器上的執(zhí)行時(shí)間.AIR算法在K80 GPU上的執(zhí)行時(shí)間幾乎為常量,穩(wěn)定在30-45微秒之間,其眾多的cuda核心、高并發(fā)內(nèi)存訪問(wèn)線程和高帶寬內(nèi)存在AIR算法的代理外鍵內(nèi)存訪問(wèn)時(shí)有極高的性能.

以上實(shí)驗(yàn)在中高端10核處理器Xeon E5-2650 v3、中端Xeon Phi 5110P協(xié)處理器、高端的NVIDIA GPGPU K80上的實(shí)驗(yàn)結(jié)果證明了AIR算法對(duì)于cache優(yōu)化(Xeon E5-2650 v3、Xeon Phi 5110P)及并發(fā)內(nèi)存訪問(wèn)優(yōu)化(K80)都有較好的性能與適應(yīng)性,適合在未來(lái)不對(duì)稱處理器平臺(tái)上面向計(jì)算密集型處理器的負(fù)載優(yōu)化,并通過(guò)先進(jìn)硬件性能的優(yōu)化加速OLAP查詢整體性能.

4 結(jié)論

本文給出了一種面向未來(lái)不對(duì)稱內(nèi)存計(jì)算平臺(tái)的OLAP查詢優(yōu)化技術(shù),其主要設(shè)計(jì)思想體現(xiàn)在3個(gè)方面:①通過(guò)schema-conscious設(shè)計(jì)和代理鍵索引機(jī)制的優(yōu)化工作提出了基于代理向量參照訪問(wèn)的外鍵連接技術(shù),消除復(fù)雜的內(nèi)存哈希表結(jié)構(gòu),簡(jiǎn)化連接操作數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì),提高外鍵連接操作的代碼執(zhí)行效率,使算法更好地適應(yīng)cache及并發(fā)多線程內(nèi)存訪問(wèn)機(jī)制,提高算法對(duì)cache-conscious和cache-oblivious設(shè)計(jì)的適應(yīng)性;②通過(guò)對(duì)OLAP查詢處理過(guò)程的重組,將SPJGA操作分解為SPG+J+A三個(gè)計(jì)算階段,分別綁定較小的維表、固定大小的事實(shí)表外鍵列及較大的事實(shí)表度量列,實(shí)現(xiàn)數(shù)據(jù)密集型任務(wù)與計(jì)算密集型任務(wù)在數(shù)據(jù)集上的劃分,有效地分離了不同類型的負(fù)載,通過(guò)基于向量數(shù)據(jù)結(jié)構(gòu)的優(yōu)化最小化三個(gè)計(jì)算階段之間的數(shù)據(jù)傳輸代價(jià);③基于不同類型的不對(duì)稱計(jì)算及存儲(chǔ)架構(gòu)提出了基于3階段計(jì)算模型的分布式存儲(chǔ)與計(jì)算策略,將數(shù)據(jù)密集型負(fù)載與計(jì)算密集型負(fù)載在通用處理器與計(jì)算型處理器之間優(yōu)化配置,通過(guò)新興的眾核協(xié)處理器加速?zèng)Q定OLAP性能的外鍵連接操作,達(dá)到提高性能和降低系統(tǒng)改寫(xiě)代價(jià)的目標(biāo).

實(shí)驗(yàn)結(jié)果表明,基于代理鍵索引機(jī)制和代理向量參照訪問(wèn)的外鍵連接操作的性能較傳統(tǒng)的內(nèi)存哈希連接算法具有更高的性能和更加簡(jiǎn)單的實(shí)現(xiàn)技術(shù),能夠更加靈活地適應(yīng)以cache為中心和以并發(fā)內(nèi)存訪問(wèn)為中心的不同類型硬件體系結(jié)構(gòu),在通用CPU和眾核協(xié)處理器平臺(tái)均有較優(yōu)的性能,其簡(jiǎn)化的算法設(shè)計(jì)進(jìn)一步降低了遷移到未來(lái)眾核協(xié)處理器平臺(tái)的代價(jià).

［1］SEBASTIAN ANTHONYIntel unveils new Xeon chip with integrated FPGA,touts 20x performance boost [EB/OL].(2014-01-19)[2015-12-25].http://www.extremetech.com/extreme/184828-intel-unveils-new-xeon-chipwith-integrated-fpga-touts-20x-performance-boost.

［2］JIM H.IBM launches flashDIMMs[EB/OL].(2014-01-20)[2015-12-25].http://thessdguy.com/ibm-launchesflash-dimms/.

［3］ANTON S.Intel:First 3D XPoint SSDs will feature up to 6GB/s of bandwidth[EB/OL].(2015-08-28)[2016-03-16].http://www.kitguru.net/components/memory/anton-shilov/intel-first-3d-xpoint-ssds-will-feature-up-to-6gbs-of-bandwidth/.

［4］BLANAS S,LI Y,PATEL J M.Design and evaluation of main memory hash join algorithms for multi-core CPUs [C]//SIGMOD.2011:37-48.

［5］BALKESEN C,TEUBNER J,ALONSO Get al Main-memory hash joins on multi-core cpus:Tuning to the underlying hardware[C]//ICDE.2013:362-373.

［6］ALBUTIU M-C,KEMPER A,NEUMANN T Massively parallel sort-merge joins in main memory multi-core data-base systems[J].VLDB Endowment,2012,5(10):1064-1075.

［7］HE B,YANG K,FANG Ret al.Relational joins on graphics processors[C]//SIGMOD.2008:511-524.

［8］YUAN Y,LEE R,ZHANG XThe yin and yang of processing data warehousing queries on GPU devices[J]. PVLDB,2013,6(10):817-828.

［9］PIRK H,MANEGOLD S,KERSTEN M L.Accelerating foreign-key joins using asymmetric memory channels [C]//ADMS@VLDB.2011:27-35.

［10］HE J,LU M,HE B.Revisiting co-processing for hash joins on the coupled CPU-GPU architecture[J].VLDB Endowment,2013,6(10):889-900.

［11］JHA S,HE B,LU M,et al.Improving main memory hash joins on Intel Xeon Phi processors:an experimental approach[J].Proceedings of TheVldb Endowment,2015,8(6):642-653.

［12］POLYCHRONIOU O,RAGHAVAN A,ROSS K A.Rethinking SIMD vectorization for in-memory databases [C]//SIGMOD Conference.2015:1493-1508.

［13］HALSTEAD R J,ABSALYAMOV I,NAJJAR W A,et al.FPGA-based Multithreading for In-Memory Hash Joins[C]//Conference on Innovative Data Systems Research.2015.

［14］ZHANG Y,ZHOU X,ZHANG Y,et al.Virtual Denormalization via Array Index Reference for Main Memory OLAP[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(4):1061-1074.

［15］ALEKSIC S,CELIKOVIC M,LINK S,et al.Face off:Surrogate vs.natural keys[C]//Advances in Databases and Information Systems-14th East European Conference.2010:543-546.

［16］張宇,張延松,陳紅,等.GPU semi-MOLAP:一種適應(yīng)GPU的混合OLAP查詢處理模型[J].軟件學(xué)報(bào),2016,27(5): 1246-1265.

(責(zé)任編輯:李萬(wàn)會(huì))

Research on OLAP query processing technology for asymmetric in-memory computing platform

ZHANG Yan-song1-3,ZHANG Yu4,ZHOU Xuan1,3,WANG Shan1,2
(1.DEKE Lab,Renmin University of China,Beijing100872,China; 2.School of Information,Renmin University of China,Beijing100872,China; 3.National Survey Research Center at Renmin University of China,
Beijing100872,China; 4.National Satellite Meteorological Center,Beijing100081,China)

This paper proposes an OLAP query processing technology for nowadays and future asymmetric in-memory computing platform.Asymmetric in-memory computing platform means that computer equips with different computing feature processors and different memory access devices so that the OLAP processing model needs to be optimized fordifferent computing features and implementation designs to enable the different processing stages to adapt to the characteristics of corresponding storage and computing hardware for higher hardware utilization and performance.This paper proposes the 3-stage OLAP computing model,which divides the traditional iterative processing model into computing intensive and data intensive workloads to be assigned to general purpose processor with full fledged functions and coprocessor with powerful parallel processing capacity.The data transmission overhead between different storage and computing devices is also minimized. The experimental results show that the 3-stage OLAP computing model based on workload partitioning can be adaptive to CPU-Phi asymmetric computing platform,the acceleration on OLAP query processing can be achieved by accelerating computing intensive workload by computing intensive hardware.

in-memory computing;asymmetric computing platform;in-memory OLAP

TP311

A

10.3969/j.issn.1000-5641.2016.05.011

1000-5641(2016)05-0089-14

2016-05

國(guó)家863計(jì)劃項(xiàng)目(2015AA015307)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(16XNLQ02)；華為創(chuàng)新研究計(jì)劃(HIRP 20140507,HIRP 20140510)

張延松,男,博士,副教授,研究方向?yàn)閮?nèi)存數(shù)據(jù)庫(kù).E-mail:zhangys ruc@hotmail.com.

張宇,女,博士,研究方向?yàn)镺LAP,GPU數(shù)據(jù)庫(kù).E-mail:zyszy511@hotmail.com.