裴 威,李戰(zhàn)懷,潘 巍

1(西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710129)

2(錦州醫(yī)科大學(xué),遼寧 錦州 121001)

近年來(lái),GPU 已經(jīng)從專業(yè)的圖形處理器發(fā)展成為通用的計(jì)算處理器(general-purpose computing on graphics processing units,簡(jiǎn)稱GPGPU)[1],其超高速計(jì)算能力和超大數(shù)據(jù)處理帶寬受到數(shù)據(jù)庫(kù)廠商及研究人員的青睞.一方面,傳統(tǒng)以CPU 為計(jì)算中心的數(shù)據(jù)庫(kù)技術(shù)面臨“能耗墻”“內(nèi)存墻”的限制,單核CPU 的性能提升已經(jīng)接近物理極限,不得不借助并行計(jì)算、分布式技術(shù)來(lái)提升系統(tǒng)整體性能;另一方面,通用GPU 每10 年提升1 000 倍的性能增長(zhǎng)(Jensen’Law),使GPU 在滿足當(dāng)今大數(shù)據(jù)需求方面具有得天獨(dú)厚的優(yōu)勢(shì).

由于受能耗墻(“heat wall”)限制[2],簡(jiǎn)單地增加CPU 的主頻來(lái)獲得性能提升走到了盡頭.早在2004 年,45 納米制程下,CPU 的主頻就可達(dá)到3GHz;但時(shí)至今日,主流CPU 制程已達(dá)到14 納米～7 納米,主頻卻仍然在3GHz～4GHz 左右(除了2017 年IBM z14 CPU 主頻曾達(dá)到5GHz)[3].與此同時(shí),以超流水線、亂序執(zhí)行、微指令(uops)技術(shù)在提升CPU 每時(shí)鐘周期內(nèi)執(zhí)行指令數(shù)上也收效甚微.比如將CISC 指令變?yōu)镽ISC 類似的微指令(uops)來(lái)提高并發(fā)度的方法,從1995 年～2013 年,近20 年間僅僅把最高并發(fā)微指令數(shù)從3 提高到4[3].盡管使用多核CPU 一定程度上緩解了CPU 性能提升的瓶頸,每年繼續(xù)保持15%～20%的增長(zhǎng).然而,CPU 已經(jīng)無(wú)法跟上多源異構(gòu)數(shù)據(jù)的爆炸性增長(zhǎng).

GPU 與CPU 具有不同的體系結(jié)構(gòu)和處理模式,將更多的片上空間用于計(jì)算單元,控制單元和緩存單元相對(duì)很少,使得單塊GPU 上擁有數(shù)千個(gè)并發(fā)計(jì)算核心.因此,在同樣的主頻下,GPU 能夠取得更高的并發(fā)計(jì)算能力,也使GPU 具有滿足大數(shù)據(jù)處理需求的巨大潛能.與CPU 不同,GPU 每?jī)赡耆〉眯阅苌系耐黄?保持了近似摩爾定律的性能增長(zhǎng):以英偉達(dá)公司當(dāng)年最頂級(jí)顯卡的單精度浮點(diǎn)數(shù)計(jì)算峰值為例,2013 年,Titan Black 為5 TFLOPS(每秒運(yùn)行5 兆次單精度浮點(diǎn)數(shù)計(jì)算指令);2015 年,Titan X 達(dá)到7 TFLOPS;2017 年,Titan V 為15 TFLOPS;2020年,RTX 3090 達(dá)到36 TFLOPS.與基于CPU 的分析技術(shù)相比,基于GPU 的數(shù)據(jù)庫(kù)可實(shí)現(xiàn)數(shù)量級(jí)的加速,并具有更高的性價(jià)比.同時(shí),由于單個(gè)GPU 包含大量計(jì)算能力,因此擴(kuò)展GPU 數(shù)據(jù)庫(kù)僅需要向服務(wù)器添加更多GPU,而不是添加更多服務(wù)器.在時(shí)空數(shù)據(jù)OLAP 分析任務(wù)和結(jié)果的可視化展示方面,幾十個(gè)GPU 的GPU 數(shù)據(jù)庫(kù)可以取得近千臺(tái)普通CPU 服務(wù)的數(shù)據(jù)庫(kù)處理能力,而其響應(yīng)時(shí)間甚至更短.比如:Tesla V100 GPU 提供120 TFLOPS 的計(jì)算力,8 塊互聯(lián)即可以頂上160 臺(tái)雙CPU 的服務(wù)器!GPU 極大地加速了可以并行化的操作,即使數(shù)據(jù)集增長(zhǎng)到數(shù)百萬(wàn)或數(shù)十億條記錄,GPU 數(shù)據(jù)庫(kù)也可以在毫秒內(nèi)返回復(fù)雜的查詢.

除了極高的性能之外,GPU 數(shù)據(jù)庫(kù)還在功能上日趨完善:基于商務(wù)智能BI 的可視化交互式圖表查詢界面,讓數(shù)據(jù)查詢和探索更人性化;同時(shí)支持標(biāo)準(zhǔn)SQL 查詢語(yǔ)言,相較于其他大數(shù)據(jù)OLAP 分析平臺(tái),分析周期大大縮短,往往只要幾分鐘就可以完成以往數(shù)天乃至一周的工作;時(shí)空數(shù)據(jù)分析功能,讓基于位置的數(shù)據(jù)分析更高效、及時(shí);GoAI(GPU open analytics initiative,GPU 開放分析計(jì)劃)產(chǎn)業(yè)聯(lián)盟和GPU 數(shù)據(jù)幀(GPU data frame,GDF)構(gòu)建了數(shù)據(jù)庫(kù)庫(kù)和人工智能應(yīng)用程序之間數(shù)據(jù)交換標(biāo)準(zhǔn),使數(shù)據(jù)科學(xué)家可以停留在GPU 上的同時(shí)探索數(shù)據(jù),訓(xùn)練機(jī)器學(xué)習(xí)算法并構(gòu)建人工智能應(yīng)用程序.現(xiàn)在,我們可以使用GPU 數(shù)據(jù)庫(kù)分析每周數(shù)十億次的電視觀看記錄,以做出廣告決策;根據(jù)移動(dòng)定位推進(jìn)時(shí)空思考、計(jì)算和工程設(shè)計(jì),從自然災(zāi)害到能源可持續(xù)性,解決全球挑戰(zhàn),都需要了解現(xiàn)象在時(shí)間和空間上的聯(lián)系.Covid-19 疫情以來(lái),接觸者追蹤為GPU 數(shù)據(jù)庫(kù)帶來(lái)新的挑戰(zhàn)和機(jī)遇,通過(guò)將人口統(tǒng)計(jì)數(shù)據(jù)與運(yùn)動(dòng)數(shù)據(jù)集成在一起,并在地理和時(shí)間多個(gè)維度聚合數(shù)據(jù),人們可以及時(shí)獲得了疫情第一手資料,做出防疫決策.

縱觀整個(gè)GPU 數(shù)據(jù)庫(kù)領(lǐng)域,不管是開源系統(tǒng)還是商業(yè)系統(tǒng),其核心研究?jī)?nèi)容主要集中在查詢編譯器(query compilation)、查詢處理器(query processing)、查詢優(yōu)化器(query optimizer)和存儲(chǔ)管理器(memory management)等4 大部件:查詢編譯器要將用戶的SQL 語(yǔ)言描述的查詢需求轉(zhuǎn)化為CPU-GPU 異構(gòu)計(jì)算環(huán)境下的查詢計(jì)劃;查詢處理器需要應(yīng)用GPU 并行計(jì)算技術(shù)實(shí)現(xiàn)關(guān)系型數(shù)據(jù)處理的各種算子,挖掘GPU 峰值計(jì)算能力;查詢優(yōu)化器利用機(jī)器學(xué)習(xí)乃至人工智能技術(shù),結(jié)合CPU-GPU 異構(gòu)計(jì)算環(huán)境和查詢計(jì)劃特點(diǎn)以及數(shù)據(jù)分布特征,生成最優(yōu)(次優(yōu))的異構(gòu)查詢計(jì)劃;存儲(chǔ)管理器需要在異構(gòu)數(shù)據(jù)存儲(chǔ)管理、數(shù)據(jù)存儲(chǔ)格式、數(shù)據(jù)壓縮、數(shù)據(jù)訪問(wèn)等問(wèn)題上做出決策.本文余下部分將依次對(duì)GPU 數(shù)據(jù)庫(kù)的4 大部件的關(guān)鍵技術(shù)進(jìn)行綜述.

1 GPU 數(shù)據(jù)庫(kù)分類與層次

GDBMS(GPU database management system or GPU accelerated database management system),顧名思義,就是使用GPU 進(jìn)行或加速數(shù)據(jù)增刪改查的數(shù)據(jù)庫(kù)管理系統(tǒng).從GDBMS 的系統(tǒng)形態(tài)上,本文將其分為研究原型(R-GDBMS:for research)和商用系統(tǒng)(C-GDBMS:for commercial)兩大類,如圖1 所示.

商用GDBMS 中,進(jìn)一步可以分為3 類.

? 第1 類是支持GPU 計(jì)算的傳統(tǒng)數(shù)據(jù)庫(kù).這類GDBMS 在已有傳統(tǒng)數(shù)據(jù)庫(kù)基礎(chǔ)之上,將特定算子部署到GPU 上用以加速的查詢處理,包括以PostgreSQL 為基礎(chǔ)的PG-Storm 系統(tǒng)和DB2 的擴(kuò)展模塊DB2 BLU.這類數(shù)據(jù)庫(kù)與現(xiàn)有數(shù)據(jù)庫(kù)集成度高、周邊工具完善、且具有一定的與OLTP 系統(tǒng)集成的能力;

? 第2 類是非內(nèi)存型GDBMS,使用GPU 完成全部或者大部分?jǐn)?shù)據(jù)庫(kù)關(guān)系運(yùn)算,可以分析超過(guò)10TB 的數(shù)據(jù)量,包括SQream 和BlazingDB;

? 第3 類是內(nèi)存型GDBMS,該類系統(tǒng)將數(shù)據(jù)全部駐留內(nèi)存,以發(fā)揮GPU 的全部潛在性能、提高數(shù)據(jù)處理速度,可以處理1TB～10TB 的較小數(shù)據(jù)集,包括OmniSci(原MapD),Kinetica(原GPUDB),MegaWise,Brytlyt.

一般來(lái)說(shuō),后兩類GDBMS 由于專為GPU 計(jì)算設(shè)計(jì),沒(méi)有傳統(tǒng)數(shù)據(jù)庫(kù)中束縛性能的遺留冗余模塊,所以性能更高.

Fig.1 GDBMS landscape圖1 GDBMS 系統(tǒng)全景圖

目前,商用GDBMS 普遍比基于CPU 的解決方案在性能上有幾個(gè)數(shù)量級(jí)的提升.比如:根據(jù)OmniSci(MapD)最新的白皮書介紹[4],在十億行出租車時(shí)空數(shù)據(jù)查詢分析中,性能超過(guò)PostgreSQL 達(dá)722 倍～7 238 倍,更是比Spark 快1 884 倍～43 000 倍.在應(yīng)用場(chǎng)景上,商用GDBMS 以超高速端到端的時(shí)空數(shù)據(jù)分析和數(shù)據(jù)可視化為特色,結(jié)合機(jī)器學(xué)習(xí)與AI 系統(tǒng)(H2O.ai 等),以一臺(tái)普通服務(wù)器配備多個(gè)GPU 顯卡就能取得分布式大數(shù)據(jù)系統(tǒng)一個(gè)集群的處理能力.超大吞吐量、超低時(shí)延以及更低的成本,讓GDBMS 在OLAP 業(yè)務(wù)上優(yōu)勢(shì)明顯.

研究原型GDBMS 將重點(diǎn)放在了全GPU 計(jì)算上,研究數(shù)據(jù)可以在GPU 顯存上存儲(chǔ)的情況下,GPU 加速所能獲得的最高性能.根據(jù)支持顯卡廠商,可分為專用GDBMS 和通用GDBMS:前者因?yàn)槭褂肅UDA 而只能在Nvidia 顯卡上運(yùn)行,包括MapD(OmniSci)[5],CoGaDB[6?15],GDB(GPUQP)[16,17],MultiQX-GPU[18],YDB(YSmart)[19],Alenka[20],GalacticaDB[21],HippogriffDB[22],G-SDMS[23,24];后者使用OpenCL,在Nvidia 卡和AMD 卡上都可以運(yùn)行,實(shí)現(xiàn)了一定程度的平臺(tái)無(wú)關(guān)性,包括GPUDB(Kinetica)[19],Ocelot[13],OmniDB[25],Virginian[26?28]這4 個(gè)數(shù)據(jù)庫(kù).絕大多數(shù)GDBMS 研究原型針對(duì)OLAP 業(yè)務(wù),只有GPUTx[29]系統(tǒng)實(shí)現(xiàn)了部分OLTP 事務(wù)功能.文獻(xiàn)[30]總結(jié)了GDBMS 設(shè)計(jì)上的諸多原則,提出了GDBMS 的共有系統(tǒng)層次架構(gòu),如圖2 所示.該文將GDBMS 分為7 層,分別為SQL 解析和邏輯優(yōu)化層、物理優(yōu)化層、算子層、數(shù)據(jù)訪問(wèn)層、數(shù)據(jù)并發(fā)原語(yǔ)層、數(shù)據(jù)管理策略層和數(shù)據(jù)存儲(chǔ)層.該文中為了突出GDBMS 與傳統(tǒng)的基于硬盤的數(shù)據(jù)庫(kù)和內(nèi)存數(shù)據(jù)庫(kù)兩者的區(qū)別,特別將GDBMS 獨(dú)有的模塊標(biāo)注為深色.本文認(rèn)為:GDBMS 作為一個(gè)獨(dú)立的數(shù)據(jù)庫(kù)分支,其設(shè)計(jì)是為了適應(yīng)GPU 并行計(jì)算的特點(diǎn),因而傳統(tǒng)數(shù)據(jù)庫(kù)中與GPU 計(jì)算不適應(yīng)的模塊沒(méi)有必要存在.因此,本文將GDBMS 分為查詢編譯器、查詢執(zhí)行器、查詢優(yōu)化器和存儲(chǔ)管理器這4 個(gè)核心模塊.對(duì)比文獻(xiàn)[30]的7 層結(jié)構(gòu),我們將其中SQL 解析和邏輯優(yōu)化層歸屬于查詢編譯器;算子層、數(shù)據(jù)訪問(wèn)層和數(shù)據(jù)并發(fā)原語(yǔ)層是頂層功能和底層實(shí)現(xiàn)的關(guān)系,在邏輯上屬于一個(gè)統(tǒng)一的整體,對(duì)應(yīng)于本文的查詢處理器;物理優(yōu)化層對(duì)應(yīng)于查詢優(yōu)化器;而數(shù)據(jù)管理策略層和數(shù)據(jù)存儲(chǔ)層密不可分,也應(yīng)該視為一個(gè)模塊(存儲(chǔ)管理器).在異構(gòu)查詢編譯、CPUGPU 異構(gòu)計(jì)算任務(wù)調(diào)度、異構(gòu)查詢優(yōu)化、代價(jià)模型構(gòu)建、GPU 關(guān)系數(shù)據(jù)并發(fā)算法設(shè)計(jì)、顯存-內(nèi)存異構(gòu)存儲(chǔ)體系管理等方面,GDBMS 面對(duì)與傳統(tǒng)CPU 數(shù)據(jù)庫(kù)完全不同的問(wèn)題和挑戰(zhàn),需要重新設(shè)計(jì)或擴(kuò)展原有的功能模塊,以充分發(fā)揮GPU 的計(jì)算性能優(yōu)勢(shì).

Fig.2 Layered architecture of GDBMS[30]圖2 GDBMS 層次架構(gòu)圖[30]

2 查詢編譯器

數(shù)據(jù)庫(kù)管理系統(tǒng)大都使用SQL 或其他高層邏輯API,而查詢編譯器作為將SQL 轉(zhuǎn)化為數(shù)據(jù)庫(kù)內(nèi)部執(zhí)行邏輯并向用戶返回結(jié)果的重要組件,處在GDBMS 的前端,與查詢處理器、查詢優(yōu)化器、存儲(chǔ)管理器深度耦合協(xié)同工作,共同為用戶提供查詢服務(wù).

傳統(tǒng)數(shù)據(jù)庫(kù)中,SQL 編譯器的詞法分析、大部分編譯技術(shù)同樣適用GDBMS,所不同的是,GDBMS 需要應(yīng)對(duì)的異構(gòu)計(jì)算硬件環(huán)境和數(shù)據(jù)處理模式變化的雙重挑戰(zhàn).

? 首先,查詢編譯器需要利用CUDAOpenCL 編譯工具生成GPU 可執(zhí)行代碼,同時(shí)要?jiǎng)?chuàng)新SQL 編譯模式,盡可能減少SQL 編譯的開銷,使整體的性能最優(yōu);

? 其次,傳統(tǒng)的“火山模型”不適合GPU 計(jì)算,GDBMS 查詢編譯器面臨著關(guān)系數(shù)據(jù)處理模式的變化,需要將向量化(vector-wise)、一次一算子(operator-at-a-time)和批量執(zhí)行(bulk processing model)這3 種策略結(jié)合起來(lái).

? 向量化,原指將多個(gè)關(guān)系型數(shù)據(jù)以向量形式作為一個(gè)SIMD(single instruction multiple data)指令的多個(gè)操作數(shù)來(lái)處理的方法,可以有效提高查詢處理吞吐量.在GPU 中,向量化思想可以用GPU的單指令多線程(single instruction multiple thread,簡(jiǎn)稱SIMT)進(jìn)一步加大數(shù)據(jù)處理的吞吐量;

?“一次一算子”與“一次一數(shù)據(jù)”是數(shù)據(jù)處理的兩種模式:前者就是先將所有數(shù)據(jù)同時(shí)完成第1 個(gè)算子的處理,并保存中間結(jié)果,作為下一個(gè)算子的輸入數(shù)據(jù),直至全部處理完;而后者是指先讓一條數(shù)據(jù)經(jīng)過(guò)所有算子計(jì)算得出結(jié)果,再計(jì)算下一條數(shù)據(jù)的策略,是基于CPU 計(jì)算常采用的策略;

? 批量執(zhí)行就是盡可能一批處理更多的數(shù)據(jù),通過(guò)提高單次處理數(shù)據(jù)的數(shù)量,彌補(bǔ)處理頻次不高的缺點(diǎn);

由于GPU 由于編程模型和計(jì)算架構(gòu)與CPU 不同,GDBMS 借鑒了CPU 計(jì)算中的向量化、“一次一算子”、批量執(zhí)行這3 種策略,并使之適應(yīng)GPU 大規(guī)模并發(fā)計(jì)算的特點(diǎn),我們將在第3.2 節(jié)詳細(xì)介紹GDBMS 編譯器的數(shù)據(jù)處理模式.

2.1 GDBMS編譯模型

傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)支持SQL 作為查詢語(yǔ)言,在大數(shù)據(jù)集合上進(jìn)行ad-hoc 查詢.數(shù)據(jù)庫(kù)系統(tǒng)直到運(yùn)行時(shí)才能知道用戶查詢的語(yǔ)義信息,因此,DBMS 大多采用解釋型的SQL 前端,通過(guò)語(yǔ)法解析、語(yǔ)義解析模塊將查詢query解析為可為查詢執(zhí)行引擎使用的內(nèi)部任務(wù)表示,即邏輯執(zhí)行樹.盡管傳統(tǒng)的基于迭代的查詢執(zhí)行模型(即火山模型或tuple-at-a-time)具有很高的靈活性,但是由于生成查詢計(jì)劃的過(guò)程必然經(jīng)過(guò)多次虛函數(shù)的調(diào)用,這種在CPU 環(huán)境中行之有效的編譯方案,在GPU 上執(zhí)行效率卻很低,不符合GPU 大規(guī)模線程并發(fā)SIMT 的編程范式,使查詢編譯消耗的時(shí)間日益成為高性能數(shù)據(jù)庫(kù)查詢處理時(shí)延的主要部分,進(jìn)而使查詢編譯器處于數(shù)據(jù)庫(kù)性能優(yōu)化的關(guān)鍵路徑.

為提高查詢編譯性能,GDBMS 采用解釋型查詢編譯器,采用JIT 即時(shí)編譯技術(shù),通過(guò)將常用的query 子句預(yù)編譯為可執(zhí)行代碼塊,并在運(yùn)行時(shí)組合調(diào)用,實(shí)踐中可取得與編譯原生代碼幾乎相同的性能.SQL 是非常適合JIT 技術(shù)的語(yǔ)言,這方面技術(shù)解決方案也非常多.早在1999 年,AT&T 實(shí)驗(yàn)室的Daytona 數(shù)據(jù)管理系統(tǒng)(1999)支持SQL 作為子集的高級(jí)查詢語(yǔ)言(cymbal)[31],將高級(jí)語(yǔ)言編譯為C 語(yǔ)言,再在運(yùn)行時(shí)將C 編譯為可執(zhí)行代碼模塊.SQLite 使用類似虛擬機(jī)的技術(shù),將SQL 解釋為虛擬機(jī)操作指令,而虛擬機(jī)指令是預(yù)先存儲(chǔ)在硬件層面的,根據(jù)代碼局部性原理可獲得較高的執(zhí)行效率.

因此,GDBMS 查詢編譯器采用3 種不同的編譯模型來(lái)解決異構(gòu)環(huán)境下SQL 編譯難題,即JIT 代碼生成(并發(fā)原語(yǔ))、SQL 虛擬機(jī)和適配器模式.

? 第一,MapD[5],CoGaDB[10]等系統(tǒng)使用nvcc 編譯工具鏈,基于底層虛擬機(jī)(LLVM)編譯器框架來(lái)即時(shí)編譯SQL 代碼,是目前GDBMS 系統(tǒng)編譯器實(shí)現(xiàn)的主流方法.該方法使用基于LLVM[32]的nvcc 編譯器,將關(guān)系算子分為更小的原語(yǔ)primitives,并把原語(yǔ)預(yù)編譯為架構(gòu)無(wú)關(guān)匯編代碼PTX,在運(yùn)行時(shí),由編譯器只需完成SQL 語(yǔ)言到算子的編譯工作,而由查詢執(zhí)行器在優(yōu)化器指導(dǎo)之下完成算子到并發(fā)原語(yǔ)的映射.這種方法通過(guò)預(yù)編譯并發(fā)原語(yǔ)的方法,降低了實(shí)時(shí)編譯SQL 語(yǔ)言的工作負(fù)載,同時(shí)保留了交互式編譯執(zhí)行的靈活性,是GDBMS 編譯器的主流技術(shù).此外,Google 公司推出了不同于nvcc 的gpucc[33]編譯器.文獻(xiàn)[34]提出了另外一種CUDA 編譯器,使用了核函數(shù)融合kernel 的技術(shù).借助對(duì)CUDA 編譯器的改進(jìn),預(yù)計(jì)將來(lái),GDBMS 可以更好地使用JIT 編譯技術(shù),進(jìn)一步縮短SQL 編譯流程;

? 第二,在SQL 虛擬機(jī)模式下[26?28],以SQLite 為基礎(chǔ)的GDBMS 系統(tǒng)——Virginian 系統(tǒng)將SQL 編譯為操作碼(opcode)作為中間表示,將整個(gè)DB 系統(tǒng)視為一個(gè)虛擬機(jī),Opcode 操作碼對(duì)應(yīng)的算子被預(yù)編譯為cudabin 可執(zhí)行代碼,直接發(fā)送到GPU 端執(zhí)行.虛擬機(jī)模式有效減少了運(yùn)行時(shí)編譯負(fù)載,讓數(shù)據(jù)可以超過(guò)GPU 顯存容量而運(yùn)行,缺點(diǎn)是所有算子只能在GPU 上運(yùn)行,缺少了基于并發(fā)原語(yǔ)方案中CPU 和GPU 一起執(zhí)行查詢的靈活性,進(jìn)而在系統(tǒng)整體性能上略低于并發(fā)原語(yǔ)方案;同時(shí),虛擬機(jī)模式放棄了SQL 優(yōu)化的機(jī)會(huì),無(wú)法提供查詢重寫、基于代價(jià)的優(yōu)化;

? 第三,在適配器模式主要是解決不同廠商GPU 接口不兼容的問(wèn)題.GPUDB 編譯器直接使用代碼生成模塊,將SQL 直接編譯為CUDA 或OpenCL 驅(qū)動(dòng)能執(zhí)行的代碼,以算子為單位進(jìn)行即時(shí)編譯[19].適配器模式在運(yùn)行時(shí)的編譯負(fù)載會(huì)比較高,在提高了系統(tǒng)對(duì)顯卡種類多樣性的同時(shí),犧牲了針對(duì)特定顯卡的性能優(yōu)化,需要結(jié)合查詢并行、分布式計(jì)算等技術(shù)來(lái)提升性能.此外,為應(yīng)對(duì)GPU 硬件的多樣性,尤其是為彌合NVIDIA 顯卡和AMD 顯卡兩家處于競(jìng)爭(zhēng)中的兩種架構(gòu)之間的不同,Ocelot[35]等系統(tǒng)使用OpenCL 框架,避免為GPU 不同架構(gòu)分別編寫代碼造成的代碼膨脹問(wèn)題.

基于LLVM 中間表示的GPU 通用編譯工具能夠很好地隔離硬件多樣性,做到編譯各階段彼此孤立,給GDBMS 在編譯的各個(gè)階段進(jìn)行優(yōu)化提供了可能.未來(lái),基于編譯自動(dòng)化工具的研究將極大提升GDBMS 系統(tǒng)的性能.

2.2 GPU數(shù)據(jù)處理模型

數(shù)據(jù)庫(kù)中,從數(shù)據(jù)處理模型來(lái)看,可分為3 種:迭代模式(iteration)、批量模式(batching)或二者的混合.傳統(tǒng)的DBMS 往往采用一次一行的流式迭代模型,也就是著名的火山模型(volcano model)處理查詢請(qǐng)求.時(shí)至今日,研究界和工業(yè)界提出了各種改進(jìn)版的火山模型來(lái)規(guī)避其缺點(diǎn),比如增加每次迭代的數(shù)據(jù)量、使用SIMD 指令一次處理多個(gè)數(shù)據(jù)、推拉結(jié)合的數(shù)據(jù)獲取方式等,目前仍然是數(shù)據(jù)庫(kù)中的主流編譯技術(shù).批量模式是將每個(gè)查詢編譯為可執(zhí)行代碼,采用完全物化的方式處理所有數(shù)據(jù).批量模式相較火山模型的迭代模式,在提高局部性、減少運(yùn)行時(shí)解釋開銷、使用SIMD 指令方面有很大優(yōu)勢(shì),但在實(shí)現(xiàn)ad-hoc 查詢上,面臨靈活度不夠、物化存儲(chǔ)空間要求過(guò)高的問(wèn)題.因此,實(shí)踐中將兩者結(jié)合的方式更有優(yōu)勢(shì),比如微批量化查詢處理.該類方案使用不同的粒度作為數(shù)據(jù)處理的單元,仍然在邏輯上組織成樹型結(jié)構(gòu),讓數(shù)據(jù)自底向上流動(dòng)完成查詢操作,兼具迭代模型的靈活性和批處理的高吞吐量的優(yōu)點(diǎn).

GDBMS 普遍采用向量化一次一算子數(shù)據(jù)處理模式,并以此改造查詢編譯器.

? 首先,迭代模式并不適合GDBMS,因?yàn)榛鹕侥Ｐ唾囈源嬖诘奶摵瘮?shù)機(jī)制因?yàn)镚PU 缺乏對(duì)應(yīng)的復(fù)雜邏輯控制模塊,在GPU 上不可實(shí)現(xiàn)或者引起嚴(yán)重的線程分支惡化問(wèn)題.迭代模型的靈活性是“彼之蜜糖,我之毒藥”,實(shí)際上會(huì)損害GPU 的性能.GPU 的SIMT 采用大規(guī)模線程并發(fā)的方式來(lái)提高數(shù)據(jù)處理的速度,批量執(zhí)行可以有效降低生成計(jì)劃的函數(shù)調(diào)用次數(shù),將列數(shù)據(jù)細(xì)粒度分配給GPU 線程,并用循環(huán)展開的方式,可有效減少控制指令總量,有效降低分支惡化的風(fēng)險(xiǎn);

? 其次,列式處理更適合GDBMS.一次一行的處理數(shù)據(jù)方式在代碼上需要做大量的邏輯判斷,而這正是GPU 的劣勢(shì);一次一列來(lái)處理數(shù)據(jù)時(shí),由于每列數(shù)據(jù)類型一致,可以用向量化方式處理,避免了分支判斷劣化性能問(wèn)題,更適合GPU 計(jì)算.此外,有研究[36]證實(shí):對(duì)于OLAP 業(yè)務(wù),按行為單位的處理模型即使行被合理分區(qū)并增加列索引等優(yōu)化策略后,仍然不如列式處理高效.事實(shí)上,列式處理模型自MonetDB[37]首次引入后,其后續(xù)系統(tǒng)X100[38]將流水化(pipelining)引入列式處理模型中.GDBMS 系統(tǒng)普遍采用列式處理模型[30],比如Ocelot[13],CoGaDB[10]等;

? 再次,由于GPU 的大規(guī)模并行編程模型依賴于對(duì)數(shù)據(jù)的并行處理,很多算法想在GPU 上運(yùn)行必須適應(yīng)單指令多線程(SIMT)的編程范式,所以需要對(duì)關(guān)系算子進(jìn)行并行化改造,使得同一指令同時(shí)處理多個(gè)關(guān)系數(shù)據(jù)處理需求,充分利用GPU 的并發(fā)編程優(yōu)勢(shì).“一次一算子”的數(shù)據(jù)處理模式就是:讓數(shù)據(jù)在GPU向量化算子間流動(dòng),每次采用完全物化的策略保存算子輸出的中間結(jié)果,作為下一個(gè)算子的輸入數(shù)據(jù);

? 最后,為了降低物化代價(jià),通過(guò)適當(dāng)分區(qū)切分?jǐn)?shù)據(jù),可以使GDBMS 兼具迭代模式的最大的優(yōu)點(diǎn)——流水化處理數(shù)據(jù)的能力[39].為了加速數(shù)據(jù)處理以及利用合理分區(qū)數(shù)據(jù),采用數(shù)據(jù)流水化處理(pipelining data processing),有效提高數(shù)據(jù)處理并行度.文獻(xiàn)[40]通過(guò)細(xì)粒度劃分?jǐn)?shù)據(jù),將處理整個(gè)列的算子切成更小的算子單元,在GPU 上實(shí)現(xiàn)了相關(guān)算子間流水化處理數(shù)據(jù).

3 查詢處理器

GDBMS 查詢處理引擎接受處理查詢編譯器輸出的查詢計(jì)劃樹QEP(query execution plan)并執(zhí)行查詢返回結(jié)果,是利用GPU-CPU 異構(gòu)計(jì)算處理用戶查詢請(qǐng)求的核心模塊.從功能角度來(lái)看,GDBMS 查詢處理引擎面對(duì)的核心問(wèn)題就是如何利用GPU 實(shí)現(xiàn)關(guān)系代數(shù)運(yùn)算,即實(shí)現(xiàn)選擇、投影、連接、聚合基本的關(guān)系算子,同時(shí)還需要實(shí)現(xiàn)的空間數(shù)據(jù)(geo-spatial data)處理、OLAP 聚合查詢等功能復(fù)雜的算子,這是GDBMS 查詢處理引擎面臨的功能挑戰(zhàn).在執(zhí)行模式上,GPU 上執(zhí)行的代碼被稱為kernel 核函數(shù),以核函數(shù)為基礎(chǔ)的查詢處理技術(shù)(KBE)是GDBMS 查詢處理引擎的必然選擇.但是核函數(shù)的并發(fā)執(zhí)行并不完全在程序的控制之下,如何在GPU 高并發(fā)SIMT 模式下以何種粒度切分關(guān)系查詢樹來(lái)最大化查詢處理性能,是GDBMS 面臨的性能挑戰(zhàn).

面對(duì)查詢功能挑戰(zhàn)和性能挑戰(zhàn),GDBMS 采用了分而治之的策略,在邏輯查詢樹級(jí)別,用KBE 融合或切分的策略,提升GPU 的資源利用率和查詢并發(fā)度;而在算子級(jí)別,則采用了設(shè)計(jì)專門針對(duì)GPU 優(yōu)化的算子的方法,即數(shù)據(jù)并發(fā)原語(yǔ)的方法.

3.1 GPU關(guān)系代數(shù)和并發(fā)原語(yǔ)

在GPU 上實(shí)現(xiàn)選擇、投影、連接等基本關(guān)系代數(shù)算子,是實(shí)現(xiàn)GDBMS 數(shù)據(jù)庫(kù)的基礎(chǔ).傳統(tǒng)的數(shù)據(jù)庫(kù)系統(tǒng)中,關(guān)系代數(shù)多由CPU 算法實(shí)現(xiàn),GDBMS 必須將關(guān)系算子用相應(yīng)的GPU 算法達(dá)到相同目的,而GPU 算法在編程模型、并發(fā)執(zhí)行、訪存方式、控制邏輯上與CPU 存在很大不同,這是制約GDBMS 發(fā)展的難點(diǎn)之一.早期的GDBMS 使用圖形流式編程接口[1],采用圖形接口(graphic API)來(lái)編寫數(shù)據(jù)庫(kù)內(nèi)核,需要很深的計(jì)算機(jī)圖形學(xué)基礎(chǔ),并且必須按照光線渲染流程編寫代碼,這嚴(yán)重制約了人們的創(chuàng)造力;而且專用顯存(紋理顯存等)容量小、訪存方式復(fù)雜、讀寫保護(hù)機(jī)制嚴(yán)格,這些因素都嚴(yán)重制約了GDBMS 處理大規(guī)模數(shù)據(jù)的能力.自2006 年統(tǒng)一計(jì)算設(shè)備架構(gòu)CUDA(compute unified device architecture)和OpenCL異構(gòu)計(jì)算框架相繼推出之后,可用于高性能通用計(jì)算的CPU-GPU 異構(gòu)計(jì)算技術(shù)(GPGPU)被引入到GDBMS 系統(tǒng)中來(lái),并迅速占據(jù)主導(dǎo)地位.比如:GPUQP[16]系統(tǒng)早期采用圖形化接口和通用CUDA 共同完成數(shù)據(jù)庫(kù)查詢處理,但隨后完成了向通用計(jì)算技術(shù)的轉(zhuǎn)化.CUDA/OpenCL 賦予了程序員使用CC++代碼控制GPU 大規(guī)模并行環(huán)境的能力,簡(jiǎn)化了GDBMS 開發(fā)的難度,促進(jìn)了GDBMS 的繁榮.

GDBMS 系統(tǒng)普遍借鑒了GDB[17]分而治之的分層設(shè)計(jì),將關(guān)系代數(shù)功能拆解為算子層(operator)和原語(yǔ)層(primitives)兩部分,設(shè)計(jì)了一系列的適應(yīng)GPU 計(jì)算的數(shù)據(jù)并行原語(yǔ)(primitives),表1 列出了大部分的GPU 并發(fā)原語(yǔ).在此基礎(chǔ)之上,CoGaDB[10]通過(guò)調(diào)用GPU 優(yōu)化的高效數(shù)據(jù)結(jié)構(gòu)庫(kù)Thrust 來(lái)實(shí)現(xiàn)相同的關(guān)系代數(shù)算法.這種使用 NVIDIA 官方程序庫(kù)的方法具有性能高、升級(jí)成本低等優(yōu)點(diǎn),也是系統(tǒng)走向成熟的必經(jīng)之路.此外,Diamos[41]等人于2012 年提出了基于算法框架(algorithm skeleton)的處理行數(shù)據(jù)的關(guān)系代數(shù)原語(yǔ)實(shí)現(xiàn),給我們提供了列數(shù)據(jù)之外的另一種解決方案.

Table 1 Data parallel primitives’ description表1 并發(fā)原語(yǔ)功能說(shuō)明

采用并發(fā)原語(yǔ)機(jī)制具有如下優(yōu)點(diǎn)[42]:首先,可以充分利用處理器間的通信機(jī)制,相比CPU 解決方案獲得4 倍～10 倍的內(nèi)存帶寬提升;其次,并行原語(yǔ)在同步和分支負(fù)載很小,因此可以發(fā)揮GPU 極限性能;再次,并行原語(yǔ)可以方便地?cái)U(kuò)展到大規(guī)模處理器上;最后,并行原語(yǔ)設(shè)計(jì)之初考慮到數(shù)據(jù)傾斜的影響,可以取得確定性的性能下限.比如:scatter 原語(yǔ)[43]通過(guò)分區(qū)散射操作,在每個(gè)load-store 周期內(nèi)處理一個(gè)分區(qū)的散射操作,增加了數(shù)據(jù)訪問(wèn)聚合讀寫,避免了隨機(jī)讀寫模式下運(yùn)行性能不可控的問(wèn)題.很多算子映射成原語(yǔ)的單個(gè)或多個(gè)組合,能夠充分利用GPU 高并發(fā)計(jì)算能力.通過(guò)以上原語(yǔ)的排列組合,大部分簡(jiǎn)單的關(guān)系代數(shù)算子可以進(jìn)行有效拆解.比如選擇算子可以用filter 原語(yǔ)實(shí)現(xiàn),同時(shí),filter 原語(yǔ)是由map 原語(yǔ)、prefix sum 原語(yǔ)和scatter 原語(yǔ)實(shí)現(xiàn)的.

基于并發(fā)原語(yǔ)的算子實(shí)現(xiàn)方法可以在實(shí)現(xiàn)中充分利用GPU 編程特點(diǎn)進(jìn)行優(yōu)化,如用寫入位置不同解決并發(fā)沖突、合并訪存方法、shared memory 優(yōu)化、用計(jì)算隱藏?cái)?shù)據(jù)傳輸時(shí)延、循環(huán)展開等技術(shù),寫出高效的CUDA程序.同時(shí),并發(fā)原語(yǔ)策略也是一種分解合并問(wèn)題的策略,采用了分層隔離的設(shè)計(jì)理念,未來(lái)還可根據(jù)GPGPU 技術(shù)發(fā)展對(duì)原語(yǔ)進(jìn)行升級(jí)而不影響上層應(yīng)用.盡管如此,并發(fā)原語(yǔ)策略以增加算子處理步驟為代價(jià),進(jìn)而增加了物化中間結(jié)果的代價(jià),存在一定的顯存浪費(fèi).每個(gè)原語(yǔ)按需請(qǐng)求顯存資源的方式給全局顯存管理提出了挑戰(zhàn),增大了算子失敗的概率.而算子一旦失敗,會(huì)造成多個(gè)關(guān)聯(lián)算子的級(jí)聯(lián)失敗,造成嚴(yán)重的性能問(wèn)題.

3.2 復(fù)雜關(guān)系算子

相較于選擇、投影、掃描等基本的關(guān)系代數(shù)算子,復(fù)雜的關(guān)系代數(shù)算子(join 連接算子、聚集函數(shù))因其邏輯功能復(fù)雜,相對(duì)計(jì)算量大,更能發(fā)揮GPU 大規(guī)模并發(fā)計(jì)算的優(yōu)勢(shì),因此成為GDBMS 優(yōu)勢(shì)所在.

3.2.1 Join 算子

Join 連接算子對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)至關(guān)重要,往往成為一個(gè)查詢計(jì)劃的性能瓶頸,是數(shù)據(jù)庫(kù)查詢優(yōu)化的重點(diǎn).Join 算子本身的計(jì)算量大,適合利用GPU 大規(guī)模并發(fā)線程技術(shù)進(jìn)行計(jì)算.文獻(xiàn)[46]指出:盡管現(xiàn)有硬件(CPU)已經(jīng)足夠智能,對(duì)隱藏緩存失效、TLB 失配延遲做的足夠好,但是針對(duì)特定硬件的優(yōu)化仍然可以有效提升join 算子的性能.文獻(xiàn)[42]采用數(shù)據(jù)并發(fā)原語(yǔ)機(jī)制(scan,scatter,split)來(lái)實(shí)現(xiàn)最常用的join 算子:有和無(wú)索引的Nest Loop Join、歸并連接Merge Join 以及哈希連接Hash Join.其后續(xù)研究成果[17]用CUDA 重寫了數(shù)據(jù)并發(fā)原語(yǔ),并將4種join 算法集成到GDB 系統(tǒng)中.實(shí)驗(yàn)表明:對(duì)于JOIN 算子,GPU 實(shí)現(xiàn)性能可以提升2 倍～20 倍.而另一個(gè)GDBMS系統(tǒng)CoGaDB[10]則將join 算法實(shí)現(xiàn)為3 種模式:通用join 算子、主鍵-外鍵連接(適用于事實(shí)表和維表的連接)、預(yù)取join(使用invisible-join[36]算法).文獻(xiàn)[47]在Virginian 系統(tǒng)上實(shí)現(xiàn)了多表連接算子,將查詢處理引擎視為執(zhí)行SQL 查詢的虛擬機(jī),使用代碼生成技術(shù)將多表連接查詢編譯為op 操作碼,由SQL 虛擬機(jī)完成CUDA 計(jì)算任務(wù)映射.受CUDA 核函數(shù)維度的限制,該方法同時(shí)最多只能做3 個(gè)表的連接操作.文獻(xiàn)[48]實(shí)現(xiàn)了高效的4 種Join算法(無(wú)索引連接NIJ、索引連接IJ、排序索引連接SIJ 和哈希連接HJ),無(wú)索引情況下,首先對(duì)連接表劃分子表,再對(duì)子表對(duì)做笛卡爾乘積;在有索引時(shí),先分別對(duì)連接表進(jìn)行索引劃分,再進(jìn)行連接.文獻(xiàn)[24]在G-SDMS[23]系統(tǒng)中改進(jìn)了hash-join 和sort-merge-join,利用CUDA 超大寄存器組來(lái)加速連接操作,并首次解決了連接表大小超過(guò)單塊GPU 顯存的問(wèn)題.

在CPU-GPU 集成架構(gòu)上,文獻(xiàn)[49]利用集成顯卡架構(gòu)下CPU 和GPU 共享內(nèi)存無(wú)需數(shù)據(jù)傳輸?shù)奶攸c(diǎn),動(dòng)態(tài)地在CPU 和GPU 間劃分計(jì)算任務(wù),并依據(jù)代價(jià)模型做負(fù)載均衡,創(chuàng)造性地提出了異構(gòu)計(jì)算環(huán)境下的hash join新算法.該算法有效避免了PCIe 總線傳輸瓶頸,但現(xiàn)階段集成式GPU 架構(gòu)的計(jì)算能力比分離式低得多,造成了其整體性能不佳.受動(dòng)態(tài)調(diào)度的啟發(fā),文獻(xiàn)[50]提出適用于列式存儲(chǔ)的異構(gòu)并發(fā)join 算法:利用ICMD(improved coordinate module distribution)給數(shù)據(jù)劃分成彼此查詢正交的獨(dú)立分區(qū),并在CPU-GPU 架構(gòu)中動(dòng)態(tài)調(diào)度來(lái)均衡負(fù)載,達(dá)到并行化join 算子的目的;此外,該研究是基于Ocelot[13]的,能夠利用分離式GPU 高效的計(jì)算性能.

實(shí)踐表明:GDBMS 在處理Join 算子上比CPU 方案效果好得多,平均可以取得2 倍～15 倍的加速比.這是由于Join 算子是計(jì)算制約算子(compute-bounded)決定的,也是GDBMS 主要的優(yōu)勢(shì)所在.未來(lái),如何進(jìn)一步優(yōu)化GPU 上Join 算子算法以及如何調(diào)整連接順序(join-order problem),仍是GDBMS 領(lǐng)域收益最高的研究熱點(diǎn)之一.

3.2.2 OLAP 聚集函數(shù)算子

聚集函數(shù)算子是又一個(gè)計(jì)算負(fù)載很高(compute-bounded)的關(guān)系代數(shù)算子,適合使用GPU 加速.在OLAP 分析工作任務(wù)中,切片(slicing)、切塊(dicing)、上卷(Roll-up)、向下鉆取(drill-down)以及數(shù)據(jù)立方(cube)函數(shù)是OLAP 業(yè)務(wù)中經(jīng)常用到的算子,結(jié)合sum,average,maximum,minimum,median,count 等各類聚集函數(shù),提供給用戶強(qiáng)大的分類匯總復(fù)雜信息的能力.借助GPU 高并發(fā)高性能計(jì)算能力加速聚集函數(shù)算子,可以有效提升GDBMS競(jìng)爭(zhēng)力.

現(xiàn)有研究聚焦到如何用GPU 的高并發(fā)計(jì)算能力和可編程的存儲(chǔ)層次結(jié)構(gòu)加速多維聚集算子.文獻(xiàn)[51]提出了MC-Cubing 算法,通過(guò)改進(jìn)自底向上廣度優(yōu)先cache 優(yōu)化算法CC-BUC,在多核環(huán)境下,充分利用CPU-GPU異構(gòu)計(jì)算能力實(shí)現(xiàn)了高效的Cube 算子,相比于CC-BUC,取得了6 倍的加速比.文獻(xiàn)[52]提出了適用GPU 的OLAP 數(shù)據(jù)立方表示數(shù)據(jù)結(jié)構(gòu)以及配套算法集合,在GPU 上實(shí)現(xiàn)了高效的多維聚合操作.作為底層模塊支持OLAP 算子的運(yùn)行,該算法可以通過(guò)組合map,reduce,scatter 等原語(yǔ)實(shí)現(xiàn),并通過(guò)預(yù)先計(jì)算的方式用空間換時(shí)間加快運(yùn)行時(shí)查詢性能、縮短總體響應(yīng)時(shí)間.文獻(xiàn)[53]提出一種壓縮多維數(shù)據(jù)立方的semi-MOLAP 模型,使用維坐標(biāo)ID 索引表數(shù)據(jù),解決了稀疏數(shù)據(jù)的GPU 存儲(chǔ)和查詢優(yōu)化問(wèn)題.文獻(xiàn)[54]對(duì)比了GPU 和多CPU 的OLAP cube創(chuàng)建算法的性能、可擴(kuò)展性和優(yōu)化策略,通過(guò)實(shí)驗(yàn)證明,GPU 可以比CUP 實(shí)現(xiàn)10 倍的加速比.但是文獻(xiàn)同時(shí)指出,多GPU 的數(shù)據(jù)立方算法并沒(méi)有預(yù)期的那么高,如何實(shí)現(xiàn)多GPU 數(shù)據(jù)立方算法還有待解決.文獻(xiàn)[55]通過(guò)實(shí)現(xiàn)聚合核函數(shù)(SUMMAXMIN)來(lái)加速簡(jiǎn)單聚合函數(shù)算子,實(shí)驗(yàn)表明,GPU 聚合核函數(shù)方案能將算法復(fù)雜度從線性降到對(duì)數(shù)級(jí)別,比對(duì)應(yīng)CPU 并行算法可提高平均32 倍的加速比.文獻(xiàn)[56]系統(tǒng)對(duì)比了GPU 上實(shí)現(xiàn)TopK 算子的各類可能算法,包括基于排序、堆數(shù)據(jù)結(jié)構(gòu)、高位前綴算法,提出了性能最優(yōu)的基于二進(jìn)制位歸并的TopK 算子(bitonic top-k).

3.3 空間數(shù)據(jù)查詢

隨著移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、車聯(lián)網(wǎng)的發(fā)展,基于位置服務(wù)越來(lái)越普及,空間數(shù)據(jù)查詢變得越來(lái)越重要.為應(yīng)對(duì)大規(guī)?？臻g數(shù)據(jù)處理的需求,大數(shù)據(jù)處理平臺(tái)開發(fā)出了一系列產(chǎn)品,比如 HadoopGIS,SpatialHadoop,SpatialSpark,GeoSpark,LocationSpark 等.綜述文獻(xiàn)[57]調(diào)研了基于Hadoop,Spark 系列的處理空間數(shù)據(jù)的產(chǎn)品,系統(tǒng)對(duì)比了其功能性、性能指標(biāo)、實(shí)現(xiàn)方法等方面的優(yōu)缺點(diǎn).但基于Hadoop 系列的時(shí)空數(shù)據(jù)分析平臺(tái)采用批處理方式進(jìn)行查詢,響應(yīng)時(shí)間過(guò)長(zhǎng).而在傳統(tǒng)的數(shù)據(jù)領(lǐng)域,各DBMS 以GIS 插件形式提供了空間數(shù)據(jù)的處理,比如PostgreSQL 的PostGIS、Oracle 的Oracle Spatial、IBM 的DB2 Spatial Extender、Informix 的Spatial DataBlade等等.PG-Storm 等系統(tǒng)基于PostgreSQL,對(duì)Geo 地理數(shù)據(jù),早在1988 年,研究人員就試圖將關(guān)系代數(shù)的成功經(jīng)驗(yàn)引入到地理位置信息系統(tǒng)GIS 中去[58].同樣,傳統(tǒng)數(shù)據(jù)庫(kù)的GIS 插件,在處理數(shù)據(jù)量、響應(yīng)時(shí)間、查詢吞吐量上都差強(qiáng)人意.

GDBMS 作為新興數(shù)據(jù)庫(kù)分支,以超過(guò)傳統(tǒng)GIS 系統(tǒng)兩到三個(gè)數(shù)量級(jí)的時(shí)空數(shù)據(jù)處理速度和數(shù)據(jù)可視化交互式查詢接口,引領(lǐng)了時(shí)空信息系統(tǒng)的發(fā)展潮流.其中,OmniSci(MapD)與Kinetica 數(shù)據(jù)庫(kù)可以借助GPU 優(yōu)秀的高速并發(fā)處理和圖形化渲染兩大優(yōu)勢(shì)的結(jié)合,以接近實(shí)時(shí)的處理速度進(jìn)行時(shí)空大數(shù)據(jù)量查詢和可視化,取得了極佳的用戶體驗(yàn).GDBMS 原型系統(tǒng)GalacticaDB[21]通過(guò)使用CUDAset 作為GPU 并發(fā)數(shù)據(jù)格式,處理大規(guī)?？臻g數(shù)據(jù)查詢,其架構(gòu)設(shè)計(jì)合理、實(shí)現(xiàn)代碼開源有很大的參考價(jià)值.文獻(xiàn)[59]利用GPU 的大規(guī)模并發(fā)計(jì)算能力為曲線的每一條邊界(line)分配線程并發(fā)查詢,在分布式計(jì)算框架(impala)上,使用均衡分區(qū)方法實(shí)現(xiàn)了空間連接的分布式并行計(jì)算.空間數(shù)據(jù)處理業(yè)已成為GDBMS 獨(dú)有的殺手級(jí)應(yīng)用,性能遠(yuǎn)超大數(shù)據(jù)平臺(tái)和傳統(tǒng)DBMS.

在算法設(shè)計(jì)層面,綜述文獻(xiàn)[60]對(duì)空間連接(spatial join)的3 個(gè)典型算法模塊——數(shù)據(jù)分區(qū)技術(shù)、在子區(qū)間做空間連接、多邊形相交檢測(cè)進(jìn)行深入詳盡的調(diào)研.由于二維空間下很難定義大小偏序關(guān)系,因此merge join 或hash join 不適用于空間連接,因此,傳統(tǒng)的空間連接實(shí)現(xiàn)方法包括嵌套循環(huán)連接(nest-loop-join)、平面刪除算法(plane sweep)、多維刪除算法(Z-Order)及其變種.

在空間索引方面,將歷史數(shù)據(jù)構(gòu)建駐留GPU 的空間索引,能夠處理大部分時(shí)空數(shù)據(jù)查詢,是未來(lái)發(fā)展方向之一.文獻(xiàn)[61]在GPU 上實(shí)現(xiàn)了基于排序批量裝載的R-Tree,并詳細(xì)對(duì)比了各種GPU 上的R-Tree 實(shí)現(xiàn)的性能.空間數(shù)據(jù)的可視化問(wèn)題需要運(yùn)行大量空間聚合函數(shù)查詢,即將點(diǎn)映射到任意形狀的區(qū)域并統(tǒng)計(jì)信息.文獻(xiàn)[62]利用GPU 渲染通道實(shí)現(xiàn)空間聚合查詢,實(shí)現(xiàn)了任意形狀的空間聚合查詢功能,同時(shí)保證了處理數(shù)據(jù)的實(shí)時(shí)性.STIG[63]通過(guò)改進(jìn)GPU 多維kd-tree,實(shí)現(xiàn)了包含時(shí)間信息的可交互空間數(shù)據(jù)查詢(PIP,多邊形范圍內(nèi)點(diǎn)查詢).G-PICS[64]在GPU 上實(shí)現(xiàn)了四叉樹(quadtree)索引,較STIG 查詢并發(fā)度更高,且支持動(dòng)態(tài)更新.

在GPU 空間查詢理論方面,文獻(xiàn)[65]提出了一種全新的GPU 友好的空間數(shù)據(jù)表示方法及空間代數(shù),將點(diǎn)、線、面統(tǒng)一成一種稱為“Canvas”的統(tǒng)一空間數(shù)據(jù)對(duì)象,并重新定義了針對(duì)Canvas 對(duì)象的5 種基本空間算子:形變(geometric transfer)、值變(value transfer)、選取(Mask)、相交(Blend)和分解(dissect).該文獻(xiàn)將空間查詢變成基于Canvas 對(duì)象的代數(shù)幾何運(yùn)算,利用了GPU 擅長(zhǎng)處理二維圖像數(shù)據(jù)的特點(diǎn),實(shí)現(xiàn)了空間數(shù)據(jù)的范圍選擇、距離選擇、形狀選擇、空間連接、聚集函數(shù)和近鄰查詢.實(shí)驗(yàn)表明:基于Canvas 的GPU 空間數(shù)據(jù)查詢相較于CPU方法,可以取得100 倍～1 000 倍的加速比.

3.4 KBE查詢執(zhí)行引擎

在查詢執(zhí)行引擎實(shí)現(xiàn)方式上,由于GDBMS 普遍采用的CUDAOpenCL 以核函數(shù)(kernel)為載體執(zhí)行協(xié)處理器計(jì)算,所以大部分GDBMS 使用基于核函數(shù)(kernel based execution,簡(jiǎn)稱KBE)[40]的查詢執(zhí)行引擎.一種自然的實(shí)現(xiàn)KBE 的方法就是將每個(gè)關(guān)系算子以一個(gè)kernel 函數(shù)執(zhí)行,大部分GDBMS 基于此實(shí)現(xiàn)自己的查詢處理引擎,比如CoGaDB,MapD 等.在此基礎(chǔ)之上,已有研究在核函數(shù)的層次上進(jìn)行合并融合或細(xì)致切分兩種策略:針對(duì)數(shù)據(jù)量大或計(jì)算復(fù)雜的任務(wù),通過(guò)將多個(gè)核函數(shù)融合(kernel fusion)到一起,共同完成查詢處理;而對(duì)于相對(duì)簡(jiǎn)單的任務(wù),則進(jìn)一步切分核函數(shù)(mini-kernel),做到精細(xì)化管理,以合理利用GPU 資源.

在核函數(shù)融合方面,文獻(xiàn)[18]提出了MultiQx-GPU(multi-query execution on GPU)框架,通過(guò)提高查詢并發(fā)度來(lái)提升設(shè)備資源利用率,即:通過(guò)將多個(gè)查詢請(qǐng)求編譯到一個(gè)核函數(shù)中,達(dá)到核函數(shù)復(fù)用的效果,提升GDBMS的整體性能.GDBMS 系統(tǒng)GPUQP[16]以10 個(gè)算子組成的查詢子樹為一個(gè)核函數(shù)執(zhí)行查詢處理.文獻(xiàn)[66]提出了基于核函數(shù)合并的查詢編譯優(yōu)化方案Kernel Weaver,通過(guò)分析核函數(shù)之間對(duì)數(shù)據(jù)的依賴性,將承載處理相同數(shù)據(jù)的算子的核函數(shù)合并為一個(gè),不但減少了整體核函數(shù)的數(shù)量,同時(shí)降低了數(shù)據(jù)在主機(jī)端和設(shè)備端的傳輸開銷;最為重要的是,增加了編譯器的對(duì)GDBMS 用戶查詢的優(yōu)化空間.文獻(xiàn)[67]使用數(shù)據(jù)預(yù)取和SIMD 指令并行機(jī)制,實(shí)現(xiàn)松弛融合算子技術(shù)(relaxed operator fusion),可以有效提升查詢并發(fā)程度,并降低物化中間結(jié)果的負(fù)載.核函數(shù)融合技術(shù)通過(guò)增加GPU 函數(shù)處理操作的數(shù)量來(lái)優(yōu)先使用GPU 資源,使得同樣配置下更能發(fā)揮GPU 高并發(fā)高速率的優(yōu)勢(shì),同時(shí)減少核函數(shù)的數(shù)量,減低了系統(tǒng)調(diào)用和管理的開銷,非常適合GPU 多計(jì)算少邏輯控制的硬件特性.但是核函數(shù)融合技術(shù)并不能增加單位數(shù)據(jù)的計(jì)算強(qiáng)度,不能從根本上提高加速比;其次,核函數(shù)融合技術(shù)增加了單個(gè)核函數(shù)處理所需要的資源,以降低GPU 資源重復(fù)利用率為代價(jià);最后,核函數(shù)融合技術(shù)目前還不能有效地跟查詢優(yōu)化器結(jié)合起來(lái),如何有效融入真實(shí)GDBMS 系統(tǒng)中是個(gè)未解之題.

在核函數(shù)切分方面,文獻(xiàn)[68]提出進(jìn)一步切分核函數(shù),并通過(guò)精細(xì)化調(diào)度來(lái)提升系統(tǒng)資源利用率.文獻(xiàn)[40]提出了流水線化查詢執(zhí)行樹的查詢執(zhí)行框架GPL,充分利用核函數(shù)計(jì)算和IO 指令交替使用不同硬件的特點(diǎn),通過(guò)切分核函數(shù)和核函數(shù)之間數(shù)據(jù)流水化技術(shù),在GPU 并發(fā)調(diào)度不可知的情況下,解決了核函數(shù)并發(fā)執(zhí)行多個(gè)關(guān)系代數(shù)算子的問(wèn)題,提高了GPU 資源的利用率,使性能提升48%.MapD(OmniSci)通過(guò)將數(shù)據(jù)分區(qū),對(duì)分區(qū)數(shù)據(jù)執(zhí)行粒度更精細(xì)的核函數(shù)執(zhí)行,不但實(shí)現(xiàn)了超過(guò)GPU 顯存容量的查詢技術(shù),而且有效提高了數(shù)據(jù)并發(fā)度,實(shí)現(xiàn)分塊數(shù)據(jù)流水化處理的效果.CoGaDB 使用硬件無(wú)關(guān)的優(yōu)化器HyPE 來(lái)進(jìn)行并發(fā)查詢時(shí)資源的優(yōu)化利用[11],著重解決運(yùn)行時(shí)處理器負(fù)載分配問(wèn)題,即所謂的算子分配問(wèn)題.而文獻(xiàn)[14]則在CoGaDB 上提出根據(jù)數(shù)據(jù)所在位置(內(nèi)存或設(shè)備顯存)驅(qū)動(dòng)查詢樹切分的策略,減少數(shù)據(jù)在總線上的傳輸,從而消除PCIe 瓶頸.GDB[17]系統(tǒng)首次引入數(shù)據(jù)并發(fā)原語(yǔ)的概念,將核函數(shù)切分為更細(xì)粒度的數(shù)據(jù)并發(fā)原語(yǔ)來(lái)實(shí)現(xiàn)關(guān)系代數(shù)功能,實(shí)現(xiàn)了理論上的突破,成為GDBMS 處理關(guān)系代數(shù)的事實(shí)上的標(biāo)準(zhǔn).核函數(shù)切分能夠以更精細(xì)的粒度管理GPU 資源,使流水化成為可能,提高了資源利用率的同時(shí),降低了單個(gè)核函數(shù)的運(yùn)行周期,可以進(jìn)一步提高查詢并發(fā)度.但是核函數(shù)切分是以更頻繁的核函數(shù)調(diào)度為代價(jià)的,數(shù)據(jù)換入換出頻率更高,受PCIe 總線瓶頸影響更大,如果控制不當(dāng),很可能降低系統(tǒng)整體性能.

此外,為了適應(yīng)未來(lái)GPU 的性能擴(kuò)展以及多廠商間編程接口的差異,使用核函數(shù)適配的方式可以賦予GDBMS 一定的硬件無(wú)關(guān)性,減少系統(tǒng)開發(fā)和維護(hù)成本.GDBMS 系統(tǒng)OmniDB[25]以GPUQP 系統(tǒng)為藍(lán)本,使用核函數(shù)適配的技術(shù),對(duì)于同一個(gè)SQL 請(qǐng)求,使用適配技術(shù)生成不同的代碼來(lái)處理查詢,統(tǒng)一了不同廠商間GPU 編程接口的不同,是一種提升GDBMS 應(yīng)用場(chǎng)景的技術(shù).但是現(xiàn)有適配器模式只能針對(duì)編譯好的SQL 存儲(chǔ)過(guò)程,在SQL 執(zhí)行的關(guān)鍵路徑上增加了編譯開銷,離商用Ad-hoc 查詢還有一定距離.

基于核函數(shù)的查詢執(zhí)行模式適應(yīng)GPU 編程的范式,是目前GDBMS 采用的主流技術(shù).該技術(shù)兼顧靈活性和實(shí)效性,通過(guò)將算子預(yù)編譯為不同粒度的核函數(shù),在運(yùn)行時(shí)根據(jù)數(shù)據(jù)的規(guī)模啟動(dòng)不同維度的線程塊(warp)執(zhí)行查詢,同時(shí)保留了進(jìn)一步優(yōu)化的空間.但是,基于核函數(shù)的執(zhí)行策略還面臨數(shù)據(jù)傳輸瓶頸的考驗(yàn)和核函數(shù)容易崩潰的問(wèn)題,當(dāng)數(shù)據(jù)超過(guò)一定限度或者中間結(jié)果物化代價(jià)過(guò)大超過(guò)顯存容量時(shí),需要引入全局的優(yōu)化策略避免核函數(shù)失敗重做的代價(jià).同時(shí),KBE 策略普遍沒(méi)有考慮數(shù)據(jù)規(guī)模的問(wèn)題,依賴于在運(yùn)行時(shí)啟動(dòng)多少核函數(shù)、分配多大顯存的策略,在實(shí)踐中,這樣的策略往往過(guò)于復(fù)雜而采用全列運(yùn)算來(lái)避歸,付出了過(guò)大的計(jì)算代價(jià).

3.5 GPU事務(wù)處理

保證事務(wù)的ACID 屬性,是支撐OLTP 業(yè)務(wù)的關(guān)鍵.可惜,眾多GDBMS 并沒(méi)有致力于解決并發(fā)事務(wù)處理的問(wèn)題.GPUTx[29]在理論上討論了GPU 實(shí)現(xiàn)事務(wù)并發(fā)控制算法的可能,該文獻(xiàn)假設(shè)事務(wù)的所有讀寫操作可以在一瞬間完成,因而在賦予事務(wù)全局唯一的時(shí)間戳并以數(shù)據(jù)為中心排序事務(wù)操作之后,形成的事務(wù)依賴圖 Tdependency 是無(wú)環(huán)的,可以用簡(jiǎn)單的拓?fù)渑判蛐纬啥鄠€(gè)無(wú)沖突的事務(wù)集.在K-Set 無(wú)沖突事務(wù)集前提下,GPUTx實(shí)驗(yàn)了3 種并發(fā)控制算法:兩階段鎖、單分區(qū)單事務(wù)、K-Set 無(wú)沖突事務(wù)集,并在GPU 上實(shí)現(xiàn)了以數(shù)據(jù)為中心對(duì)操作排序執(zhí)行的高性能GPU 事務(wù)處理模式,比CPU 算法提升4 倍～10 倍的吞吐量.但是GPUTx 對(duì)事務(wù)的操作在同一時(shí)刻完成的假設(shè)過(guò)強(qiáng),在實(shí)踐中面臨事務(wù)并發(fā)讀寫沖突、無(wú)法支撐ad-hoc 查詢、長(zhǎng)事務(wù)執(zhí)行、排序操作負(fù)載過(guò)大等問(wèn)題.目前,如何在GPU 上實(shí)現(xiàn)數(shù)據(jù)庫(kù)事務(wù)的并發(fā)執(zhí)行還是一個(gè)開放問(wèn)題,需要在GPU 并發(fā)控制算法、GPU 數(shù)據(jù)高效獲取、日志和故障恢復(fù)機(jī)制、GPU 高效鎖實(shí)現(xiàn)機(jī)制、樂(lè)觀并發(fā)控制策略等方面進(jìn)一步研究.

3.6 小 結(jié)

查詢執(zhí)行器是GDBMS 所有計(jì)算真正執(zhí)行的核心引擎,決定了GDBMS 的幾乎全部的功能特性,是真正為用戶提供價(jià)值的重要組件.數(shù)據(jù)庫(kù)技術(shù)發(fā)展到今天,很難有一體適用的數(shù)據(jù)庫(kù)技術(shù)包打天下,而GDBMS 作為后來(lái)者,盡管有很大的應(yīng)用前景和性能提升潛力,其功能應(yīng)該是GDBMS 設(shè)計(jì)者應(yīng)該關(guān)注的重點(diǎn).GDBMS 查詢執(zhí)行引擎核心功能是實(shí)現(xiàn)關(guān)系代數(shù)算子,目前主流的方法是采用并發(fā)數(shù)據(jù)原語(yǔ)分解關(guān)系代數(shù)的功能

目前,GDBMS 更多地面向OLAP 業(yè)務(wù),在查詢與報(bào)表工具、多維分析工具、統(tǒng)計(jì)工具、空間數(shù)據(jù)處理、數(shù)據(jù)可視化、人工智能系統(tǒng)等方面努力尋找商業(yè)應(yīng)用場(chǎng)景,業(yè)已在殘酷的商業(yè)化競(jìng)爭(zhēng)中占有一席之地.但是我們也注意到,鮮有研究[29]關(guān)注GDBMS 事務(wù)的ACID,這導(dǎo)致GDBMS 無(wú)法支撐OLTP 業(yè)務(wù),嚴(yán)重制約了GDBMS的應(yīng)用場(chǎng)景,對(duì)此,筆者表示非常遺憾.

4 查詢優(yōu)化器

GDBMS 查詢優(yōu)化器按功能可分為代價(jià)估計(jì)系統(tǒng)、查詢重寫規(guī)則、任務(wù)調(diào)度系統(tǒng)這3 大部分,以查詢編譯器輸出的邏輯執(zhí)行計(jì)劃作為輸入,以生成適應(yīng)CPU-GPU 異構(gòu)計(jì)算環(huán)境的代價(jià)最優(yōu)的異構(gòu)查詢樹為目標(biāo),并指導(dǎo)查詢處理引擎執(zhí)行計(jì)劃.目前,大多數(shù)的GDBMS 或者缺乏統(tǒng)一的優(yōu)化器,由查詢執(zhí)行器按規(guī)則決定如何執(zhí)行查詢操作;或者用任務(wù)調(diào)度來(lái)代替優(yōu)化器的作用,這就造成了一旦SQL 編譯完成,其執(zhí)行過(guò)程就已經(jīng)固定,放棄了優(yōu)化查詢的機(jī)會(huì).而研究表明,未經(jīng)優(yōu)化的查詢計(jì)劃與最優(yōu)的查詢計(jì)劃之間的性能可能有數(shù)量級(jí)上的差距.未來(lái),優(yōu)化器將扮演越來(lái)越重要的角色,是GDBMS 能否在CPU-GPU 異構(gòu)計(jì)算環(huán)境下高效執(zhí)行、發(fā)揮全部硬件性能的關(guān)鍵,也是保障查詢安全、提高系統(tǒng)健壯性的核心部件,值得深究:首先,如何建立GDBMS 查詢處理的代價(jià)模型,是查詢優(yōu)化的核心問(wèn)題;其次,在代價(jià)模型指導(dǎo)下,構(gòu)建適應(yīng)GPU 查詢處理的啟發(fā)式規(guī)則體系對(duì)查詢樹進(jìn)行等價(jià)改寫,是GDBMS 優(yōu)化器的重要問(wèn)題;再次,GDBMS 查詢優(yōu)化問(wèn)題在一定程度上可以抽象為算子在何種類型的計(jì)算核心(CPU or GPU)上進(jìn)行處理的問(wèn)題,即算子分配問(wèn)題,解決了算子分配問(wèn)題,就能最大程度地發(fā)揮GDBMS 整體性能優(yōu)勢(shì);最后,如何在真實(shí)系統(tǒng)中設(shè)計(jì)實(shí)時(shí)高效的查詢優(yōu)化器,與數(shù)據(jù)庫(kù)系統(tǒng)的其他模塊協(xié)同工作,是制約GDBMS 發(fā)展的關(guān)鍵問(wèn)題.

4.1 代價(jià)模型

代價(jià)是數(shù)據(jù)庫(kù)內(nèi)核對(duì)給定SQL 任務(wù)執(zhí)行成本的估計(jì),在傳統(tǒng)數(shù)據(jù)庫(kù)中包括CPU 執(zhí)行代價(jià)和IO 代價(jià)兩部分,是邏輯查詢計(jì)劃向物理查詢計(jì)劃轉(zhuǎn)化過(guò)程中選擇最優(yōu)物理執(zhí)行計(jì)劃的依據(jù).構(gòu)建GDBMS 代價(jià)模型,需要考慮GPU-CPU 混合計(jì)算和異構(gòu)存儲(chǔ)層次特點(diǎn),特別是PCI-E 總線瓶頸問(wèn)題,使其仍是一個(gè)未解決的開放問(wèn)題.下面介紹構(gòu)建GDBMS 代價(jià)模型所面臨的挑戰(zhàn)以及兩種常用的采用代價(jià)估計(jì)方法——基于代碼分析的“白盒方法”和基于學(xué)習(xí)的“黑盒方法”,并簡(jiǎn)要介紹算子選擇率的估計(jì)方法.

4.1.1 GDBMS 代價(jià)模型之難

SQL 優(yōu)化過(guò)程可以分為邏輯優(yōu)化和物理優(yōu)化兩個(gè)階段:在邏輯優(yōu)化階段,優(yōu)化器根據(jù)關(guān)系代數(shù)等價(jià)定律、算子下推啟發(fā)式規(guī)則、子查詢重寫等規(guī)則對(duì)邏輯執(zhí)行計(jì)劃進(jìn)行改寫,以得到執(zhí)行代價(jià)更小的物理執(zhí)行計(jì)劃;而在物理優(yōu)化階段,需要為邏輯查詢計(jì)劃中的算子選擇特定的算法和數(shù)據(jù)訪問(wèn)方法,并選擇其中代價(jià)最低的一條生成路徑作為最終的查詢計(jì)劃.這里非常關(guān)鍵的一點(diǎn)是如何估算查詢的代價(jià).傳統(tǒng)的以磁盤為中心的數(shù)據(jù)庫(kù)在查詢執(zhí)行代價(jià)估計(jì)方面有很成熟的經(jīng)驗(yàn),一般以磁盤IO 和CPU 計(jì)算的加權(quán)平均和作為最終的查詢執(zhí)行代價(jià);在分布式數(shù)據(jù)庫(kù)系統(tǒng)中,通信代價(jià)也是非常重要的度量標(biāo)準(zhǔn);在內(nèi)存數(shù)據(jù)庫(kù)中,由于數(shù)據(jù)盡量放在內(nèi)存中,消除了磁盤IO,代價(jià)估計(jì)的重點(diǎn)是內(nèi)存訪問(wèn).而在GDBMS 中,查詢代價(jià)的估計(jì)問(wèn)題變得很不一樣.

? 首先,GDBMS 的計(jì)算代價(jià)不僅僅包括CPU 計(jì)算,還包括GPU 計(jì)算,而GPU 計(jì)算能力往往是CPU 的10倍以上.傳統(tǒng)的方法以查詢涉及的tuple 條目的數(shù)量之和來(lái)估計(jì)其計(jì)算代價(jià),這是基于各CUP 的計(jì)算能力大致相同的假設(shè);但在GDBMS 中,必須根據(jù)tuple 計(jì)算的位置(在CUP 中還是在GPU 中)來(lái)分別計(jì)算其代價(jià).在GPU 中,計(jì)算的代價(jià)由于其速率更高所以必須乘以一個(gè)經(jīng)驗(yàn)系數(shù)(比如0.1);

? 其次,GDBMS 訪存代價(jià)的估計(jì)變得更加復(fù)雜.與內(nèi)存數(shù)據(jù)庫(kù)類似,GDBMS 將數(shù)據(jù)盡可能地存放在內(nèi)存中以消除磁盤IO 瓶頸,甚至有的方案將數(shù)據(jù)完全放在GPU 顯存中,因此,GDBMS 中存儲(chǔ)層次體系更加復(fù)雜——既包括傳統(tǒng)的緩存-內(nèi)存-硬盤三級(jí)存儲(chǔ)管理,又包括主機(jī)內(nèi)存與GPU 設(shè)備內(nèi)存的異構(gòu)存儲(chǔ)體系管理,這決定了GDBMS 必須設(shè)計(jì)獨(dú)有的、能夠充分反映GDBMS 存儲(chǔ)特性的訪存代價(jià)估計(jì)函數(shù);

? 最后,GDBMS 的性能瓶頸在于主機(jī)內(nèi)存與GPU 顯存之間的數(shù)據(jù)拷貝,可以類比于分布式數(shù)據(jù)庫(kù)中的網(wǎng)絡(luò)通信開銷,這也是在代價(jià)估計(jì)中必須考慮的最重要的因素.文獻(xiàn)[69]等研究指出:PCIe 總線瓶頸是所有GPGPU 算法不能忽視的性能開銷,也是GDBMS 的性能瓶頸所在.文獻(xiàn)[20]對(duì)開源Alenka 系統(tǒng)運(yùn)行TPC-H 基準(zhǔn)測(cè)試進(jìn)行了詳盡的性能分析,發(fā)現(xiàn)只有5%用在了GPU 計(jì)算上,大部分開銷都用在了數(shù)據(jù)傳輸上.其次,在多GPU 環(huán)境的系統(tǒng)中,由于多GPU 往往共享PCIe 總線,因此多GPU 下性能并不呈現(xiàn)簡(jiǎn)單的線性增長(zhǎng),而且與之相關(guān)的管理成本和決策空間也相應(yīng)變大.因此,如何在多GPU 環(huán)境下的優(yōu)化查詢性能仍然是一個(gè)未解難題.

以上因素共同作用,造成了PCIe 總線數(shù)據(jù)傳輸開銷成為了GDBMS 代價(jià)估計(jì)的重點(diǎn)和難點(diǎn).

4.1.2 算子代價(jià)估計(jì)的方法

目前,GDBMS 主要有兩種方法獲取查詢計(jì)劃的代價(jià):基于代碼分析的“白盒”方法(analytical)[17,40,43,49]和基于學(xué)習(xí)(learning-based)[11?13,15,70]的“黑盒”方法.基于代碼分析的方法認(rèn)為,查詢的執(zhí)行取決于開生成指令的代碼,因此可以通過(guò)靜態(tài)的代碼分析方法將GPU 上執(zhí)行的關(guān)系代數(shù)算子的執(zhí)行代價(jià)精確估計(jì),包括傳輸代價(jià)、計(jì)算代價(jià)、傳回代價(jià)及內(nèi)存訪問(wèn)代價(jià).這種方法依賴于對(duì)每個(gè)算子的精確估計(jì).對(duì)于多GPU 協(xié)同運(yùn)算,文獻(xiàn)[71]系統(tǒng)介紹了確定性計(jì)算任務(wù)的多GPU 性能代價(jià)估計(jì)方法,假定每元素和每子集的開銷在多GPU 環(huán)境下具有不變性,同時(shí)考慮了PCIe 通信開銷.文獻(xiàn)[17,42]采用分析型cost 模型,對(duì)一個(gè)實(shí)際的GDBMS 系統(tǒng)——GDB 分析其關(guān)系代數(shù)算子、Join 算子的執(zhí)行cost 代價(jià),其對(duì)查詢時(shí)間的估計(jì)由3 部分組成:傳輸?shù)紾PU 的時(shí)間、GPU 運(yùn)算時(shí)間、傳回到host 端的時(shí)間.該方法針對(duì)特定的算子實(shí)現(xiàn),其準(zhǔn)確率可以達(dá)到90%.但是由于采用了靜態(tài)的“白盒”分析的方法,只能針對(duì)算子級(jí)別進(jìn)行分析,沒(méi)有考慮多查詢并發(fā)情況下算子之間的相互影響以及系統(tǒng)運(yùn)行時(shí)的負(fù)載情況,不可避免地將在運(yùn)行時(shí)發(fā)生錯(cuò)誤;而且隨著系統(tǒng)的進(jìn)化,任何代碼上的微小改動(dòng)都將對(duì)代價(jià)估計(jì)產(chǎn)生影響,對(duì)代價(jià)估計(jì)模塊的維護(hù)成本也隨之增高,在擴(kuò)展性和可維護(hù)性上面臨巨大挑戰(zhàn).

而基于學(xué)習(xí)的方法將算子視作黑盒,通過(guò)機(jī)器學(xué)習(xí)的方法,經(jīng)過(guò)觀測(cè)算子的過(guò)往行為,估計(jì)該算子的執(zhí)行代價(jià),并在運(yùn)行時(shí)利用反饋機(jī)制修正算子代價(jià).這種方法在一定程度上避免了靜態(tài)方法的一些問(wèn)題,但同樣不夠完美:首先,基于學(xué)習(xí)的方法需要一定的訓(xùn)練過(guò)程,這在實(shí)際生產(chǎn)環(huán)境下面臨冷啟動(dòng)缺乏基礎(chǔ)統(tǒng)計(jì)數(shù)據(jù)的問(wèn)題,造成優(yōu)化器可發(fā)揮作用的時(shí)效性低,切換任務(wù)后面臨新的“訓(xùn)練空窗期”;其次,基于學(xué)習(xí)的方法對(duì)算子代價(jià)的估計(jì)是不精確的——執(zhí)行計(jì)劃的代價(jià)估計(jì)需要考慮的空間過(guò)大,很難在訓(xùn)練階段窮舉所有的情況,這就造成了對(duì)算子代價(jià)的估計(jì)模型的訓(xùn)練上面臨訓(xùn)練樣本空間和測(cè)試樣本空間不重疊、訓(xùn)練樣本過(guò)少的問(wèn)題,模型必然存在精度不高和泛化能力不足的問(wèn)題;最后,現(xiàn)有基于學(xué)習(xí)的方法沒(méi)有考慮多顯卡、多計(jì)算節(jié)點(diǎn)分布式的應(yīng)用場(chǎng)景,低估了PCIe 總線瓶頸的影響.基于學(xué)習(xí)的cost 模型中,文獻(xiàn)[15]對(duì)比了sort,indexed scan,update 這3 種常用數(shù)據(jù)庫(kù)算子的性能均衡點(diǎn),證明特定算法在不同輸入情況下,可以根據(jù)性能估計(jì)來(lái)選擇合適的處理器來(lái)優(yōu)化系統(tǒng)的性能.文獻(xiàn)[72]在PostgreSQL 平臺(tái)下,針對(duì)TPC-H 基準(zhǔn)測(cè)試使用基于學(xué)習(xí)的方法,在查詢和算子兩個(gè)粒度下對(duì)查詢的執(zhí)行時(shí)間(query execution latency)進(jìn)行預(yù)測(cè),實(shí)現(xiàn)了線下分析和線上執(zhí)行決策結(jié)合的查詢性能預(yù)測(cè).

在現(xiàn)今復(fù)雜多變的硬件環(huán)境、不斷變化升級(jí)的異構(gòu)計(jì)算圖景(landscape)、分析任務(wù)的越來(lái)越復(fù)雜、與操作系統(tǒng)之間交互的不確定性等原因,分析型的查詢代價(jià)估計(jì)在實(shí)踐中很難做到高精確度,而且基于訓(xùn)練模型再預(yù)測(cè)的學(xué)習(xí)型代價(jià)估計(jì)系統(tǒng)在時(shí)效性、準(zhǔn)確度、泛化能力上難以滿足數(shù)據(jù)庫(kù)系統(tǒng)的要求.因此,將兩種方法結(jié)合的優(yōu)化器cost 模型在未來(lái)會(huì)很有前景,比如用分析模型為學(xué)習(xí)型cost 系統(tǒng)設(shè)定初值,來(lái)解決學(xué)習(xí)型代價(jià)系統(tǒng)的冷啟動(dòng)問(wèn)題.

HyPE[12,13]系統(tǒng)高效地解決了異構(gòu)環(huán)境下算子分配問(wèn)題、負(fù)載均衡問(wèn)題,是不可多得的基于cost 代價(jià)估計(jì)可移植物理查詢優(yōu)化框架.但是我們也應(yīng)該看到:該系統(tǒng)的“學(xué)習(xí)”算法只在算子層級(jí)上決策算子在哪個(gè)計(jì)算核心(CPU OR GPU)上,從理論上無(wú)法保證選出最優(yōu)的執(zhí)行計(jì)劃,仍存在較大的改進(jìn)空間;同時(shí),HyPE 還無(wú)法對(duì)多顯卡架構(gòu)下的并發(fā)環(huán)境進(jìn)行優(yōu)化,同時(shí)無(wú)法適應(yīng)多計(jì)算節(jié)點(diǎn)的分布式計(jì)算環(huán)境,未來(lái)需要做的大量的研究工作.

4.1.3 算子的選擇率估計(jì)

對(duì)于一個(gè)特定的關(guān)系算子來(lái)說(shuō),基數(shù)估計(jì)(cardinality estimation)就是對(duì)算子運(yùn)行前后數(shù)據(jù)的變化量評(píng)估的技術(shù),其中,選擇率(selectivity)評(píng)估占據(jù)了重要的位置.選擇率是指滿足算子條件的數(shù)據(jù)數(shù)量與數(shù)據(jù)總量之間的比值.算子選擇率的精確估計(jì)對(duì)中間結(jié)果大小估計(jì)、算子代價(jià)估計(jì)、最優(yōu)join 順序等都有重要影響,不但直接決定了優(yōu)化器的準(zhǔn)確性,甚至對(duì)GPU 內(nèi)存管理產(chǎn)生直接影響.因此,選擇率的快速而精準(zhǔn)的估計(jì)對(duì)GDBMS 來(lái)說(shuō)十分重要.目前最好的解決方案是基于抽樣的柱狀圖方法,即等寬或等值地抽取數(shù)據(jù),事先建立多區(qū)間的統(tǒng)計(jì)條形圖,查詢時(shí),結(jié)合查詢條件及柱狀圖信息估計(jì)算子的選擇率.

文獻(xiàn)[73]提出了使用GPU 加速的基于核函數(shù)(kernel density estimation)的多維數(shù)據(jù)過(guò)濾算子選擇率估計(jì)方法,該方法使用數(shù)值優(yōu)化KDE 方法,在數(shù)據(jù)更改或查詢執(zhí)行時(shí)可動(dòng)態(tài)調(diào)整選擇率,并將該模型通過(guò)GPU 加速提升算法速度.該方法提供了選擇率估計(jì)的統(tǒng)計(jì)學(xué)方法,精度及適應(yīng)性不如現(xiàn)有的直方圖方法,使用GPU 加速的方式也對(duì)GDBMS 的性能提升幫助有限.

針對(duì)空間join 的選擇率估計(jì)問(wèn)題,文獻(xiàn)[74]提出了多維空間累計(jì)柱形圖histogram 結(jié)構(gòu)和積分表技術(shù)的并發(fā)選擇率計(jì)算方法,能夠在GPU 上使用較少的資源實(shí)現(xiàn)選擇率的并發(fā)估計(jì).該方法需要對(duì)join 數(shù)據(jù)提前分析,不適應(yīng)于運(yùn)行時(shí)查詢的需求.由于需要占用寶貴的GPU 顯存,在應(yīng)用該方法前,需要仔細(xì)權(quán)衡利弊.

目前,由于現(xiàn)有選擇率估計(jì)的精度和性能仍有待提高,無(wú)法根據(jù)其對(duì)數(shù)據(jù)的估計(jì)結(jié)果精確控制用以存儲(chǔ)中間結(jié)果的緩沖區(qū).但是,利用深度學(xué)習(xí)等智能算法計(jì)算選擇率提升空間很大,值得進(jìn)一步探索.比如,可以利用深度神經(jīng)網(wǎng)絡(luò)(DNN)來(lái)預(yù)測(cè)一個(gè)算子的選擇率,而GDBMS 中由于數(shù)據(jù)就在GPU 上,可以進(jìn)行本地訓(xùn)練DNN,可以預(yù)見,其性能將比傳統(tǒng)的CPU 算法要高.

4.2 查詢重寫

查詢重寫是指優(yōu)化器對(duì)邏輯查詢樹等價(jià)變形,以達(dá)到提高查詢效率的目的.在GDBMS 中,傳統(tǒng)的查詢改寫策略同樣適用,當(dāng)然也有細(xì)微的不同之處,比如對(duì)于“下推算子”策略,由于投影操作在列式存儲(chǔ)下可以直接用物理投影解決,因此不存在下推投影的問(wèn)題.目前的研究主要致力于改進(jìn)Join 算子的性能和合理消減copy 算子來(lái)控制數(shù)據(jù)PCIe 總線傳輸總量上.

4.2.1 join 算子改寫

文獻(xiàn)[36]針對(duì)SSBM 測(cè)試提出了invisible join 技術(shù),對(duì)星型模式下的事實(shí)表與多個(gè)維表外鍵連接(star join)進(jìn)行優(yōu)化.該技術(shù)通過(guò)將JOIN 重寫為事實(shí)表上的多個(gè)Select 操作,并用布爾代數(shù)將多個(gè)選擇的結(jié)果合并,以減少后續(xù)JOIN 階段的整體數(shù)據(jù)量.CoGaDB[10]系統(tǒng)通過(guò)位圖(bitmap)改進(jìn)Invisible-Join 技術(shù),實(shí)現(xiàn)了Star Join 查詢.

對(duì)于OLAP 業(yè)務(wù)中最常用的兩個(gè)表間的PK-FK Join,CoGaDB 則使用文獻(xiàn)[42]提到的適應(yīng)GPU 的NLJ(nestloop-join)算法,先對(duì)PK 列排序,再給每個(gè)工作線程組(warp)分配一定數(shù)量的FK 值,warp 用二分查找法在排序PK 列中查找匹配值.該實(shí)現(xiàn)的主要改進(jìn)在于跳過(guò)了線程各自計(jì)數(shù)匹配tuple 數(shù)量的過(guò)程.對(duì)于超過(guò)顯存的大表PK-FK 連接,文獻(xiàn)[75]通過(guò)將事實(shí)表放在主存、維表放在顯存中,試圖利用PCIe 總線非對(duì)稱性帶寬傳輸特點(diǎn),發(fā)揮出全部硬件的潛力,以提升Star-Join 的性能.

表連接的順序是查詢性能優(yōu)化的關(guān)鍵.在現(xiàn)有的GDBMS 中,各系統(tǒng)放棄了連接順序的優(yōu)化,采用確定性的查詢計(jì)劃構(gòu)建方法,留下了較大的優(yōu)化空間.文獻(xiàn)[76]提出一種端到端的表連接順序的基準(zhǔn)測(cè)試——JOB 測(cè)試.文獻(xiàn)[77]在多核CPU 框架下,用動(dòng)態(tài)規(guī)劃算法遍歷所有可能的表鄰接順序,通過(guò)將數(shù)據(jù)分區(qū),用多核的并發(fā)性處理多表連接順序的指數(shù)增長(zhǎng),為優(yōu)化器提供保留了所有可能的連接順序的查詢執(zhí)行樹空間,最多可以處理25 個(gè)表的連接順序問(wèn)題.文獻(xiàn)[78]討論了用GPU 加速多表連接順序問(wèn)題的動(dòng)態(tài)規(guī)劃算法所面臨的挑戰(zhàn):首先,動(dòng)態(tài)規(guī)劃算法是順序算法,不易并行化,現(xiàn)有的CPU 順序算法的上限可以解決12 個(gè)表的連接順序問(wèn)題;而GPU 擁有更大規(guī)模的并發(fā)處理能力,理論上有潛力徹底解決多表連接順序問(wèn)題,但是需要解決分支消除、傳輸瓶頸、優(yōu)化訪存、并行計(jì)算等問(wèn)題.目前,多表連接順序判定仍然是數(shù)據(jù)庫(kù)優(yōu)化領(lǐng)域開放問(wèn)題之一,還沒(méi)有一個(gè)可以利用GPU 加速該問(wèn)題求解的成熟方案.

4.2.2 減少copy 算子

對(duì)于查詢優(yōu)化,可以通過(guò)查詢重寫技術(shù)減少copy 算子的數(shù)量為目標(biāo),來(lái)減少在PCIe 上來(lái)回反復(fù)傳輸?shù)臄?shù)據(jù)量,從而提升性能.文獻(xiàn)[70]在算子序列化階段,通過(guò)窮舉copy 算子位置不同的算子執(zhí)行計(jì)劃,并用貪心策略找到能使GPU 算子盡可能多(兩個(gè)copy 中間算子盡可能長(zhǎng))的執(zhí)行計(jì)劃,以減少數(shù)據(jù)在PCIe 總線上的傳輸,最大化利用GPU 的計(jì)算能力.但是此方法只適用于單查詢執(zhí)行計(jì)劃的情況,且沒(méi)有考慮算子間的依賴關(guān)系,而其基于貪心的策略并不能保證生成最優(yōu)的查詢計(jì)劃.

文獻(xiàn)[14]提出一種根據(jù)數(shù)據(jù)位置驅(qū)動(dòng)算子分配的優(yōu)化策略,即:只在算子需要的數(shù)據(jù)已經(jīng)在GPU 上時(shí),才將算子分配給該GPU 執(zhí)行計(jì)算.在數(shù)據(jù)管理上,該文將GPU 顯存劃分為管理算子輸入輸出數(shù)據(jù)的Cache 緩沖區(qū)和存儲(chǔ)中間數(shù)據(jù)結(jié)構(gòu)Heap 堆?？臻g,通過(guò)對(duì)并發(fā)查詢占用資源的集中控制,來(lái)解決緩存抖動(dòng)問(wèn)題和數(shù)據(jù)反復(fù)遷移(數(shù)據(jù)ping-pong)問(wèn)題.

此外,前文提到的KBE 核函數(shù)執(zhí)行策略中,核函數(shù)融合技術(shù)能夠有效減少copy 算子的數(shù)目;而核函數(shù)切分則會(huì)顯著增加copy 算子數(shù)量,增加本就繁重的PCIe 通信成本.綜合應(yīng)用核函數(shù)融合和切分技術(shù),有望進(jìn)一步提高GDBMS 的查詢性能.如何有效綜合各種優(yōu)化策略來(lái)減少copy 算子,將成為未來(lái)GDBMS 優(yōu)化器設(shè)計(jì)的重中之重.

4.3 異構(gòu)計(jì)算任務(wù)隊(duì)列

GDBMS 與傳統(tǒng)CPU 數(shù)據(jù)庫(kù)的不同之處在于,可以利用CPU-GPU 異構(gòu)計(jì)算平臺(tái)并行處理數(shù)據(jù).為保證多個(gè)計(jì)算設(shè)備(CPU 和GPU)處于“繁忙”狀態(tài),保證系統(tǒng)整體性能[12],給每個(gè)計(jì)算核心維護(hù)一個(gè)工作隊(duì)列,根據(jù)啟發(fā)式規(guī)則,將查詢計(jì)劃樹中相互獨(dú)立的算子分配給工作隊(duì)列并發(fā)執(zhí)行.

以響應(yīng)時(shí)間為優(yōu)化目標(biāo)下,可以使用SRT(simple response time 簡(jiǎn)單響應(yīng)時(shí)間最小策略)或WTAR(waiting time-aware response time,停等時(shí)間最少)調(diào)度策略[7].對(duì)于SRT,系統(tǒng)估計(jì)單個(gè)算子的執(zhí)行時(shí)間,選擇工作隊(duì)列中執(zhí)行該算子代價(jià)最小(時(shí)間最短)的隊(duì)列分配即可.而在WTAR 策略下,系統(tǒng)需要對(duì)整個(gè)工作隊(duì)列中所有已經(jīng)就緒算子的執(zhí)行總時(shí)間以及算子各計(jì)算核心的執(zhí)行時(shí)間來(lái)計(jì)算各任務(wù)隊(duì)列的停等時(shí)間,以系統(tǒng)整體停等時(shí)間最短為原則分配算子.細(xì)致的實(shí)驗(yàn)對(duì)比下,WTAR 策略效果在所有情況下都效果最佳.

以系統(tǒng)整體吞吐率[11]為優(yōu)化目標(biāo),則可以使用公平輪詢(RR)、基于閾值(TBO)、基于概率(PBO)這3 種調(diào)度策略.

? Round-robin(RR)策略將算子輪番均分給各個(gè)任務(wù)隊(duì)列,以公平的策略進(jìn)行調(diào)度;

? TBO(thread-based optimization)基于閾值,給每個(gè)計(jì)算核心CU 一個(gè)閾值,超過(guò)閾值之后就不再往該任務(wù)隊(duì)列中分配任務(wù).這樣有兩點(diǎn)好處:首先,TBO 解決了SRT 策略負(fù)載不均衡的問(wèn)題,避免了因并發(fā)算子過(guò)多引起的資源耗盡問(wèn)題;其次,TBO 給了我們選擇次優(yōu)執(zhí)行計(jì)劃的能力,這在一定程度上避免了cost代價(jià)估計(jì)不準(zhǔn)而造成的分配失效的問(wèn)題;

? PBO 利用歸一化指數(shù)概率函數(shù)Softmax計(jì)算最優(yōu)計(jì)算核心CU(CUP/GPU)的概率值,并在算子分配時(shí)按概率分配計(jì)算任務(wù).PBO 策略可以并發(fā)使用多CU 來(lái)提高系統(tǒng)吞吐率,同時(shí)以最大概率將算子分配給最快的CU.

RRTBOPBO 都是在算子層面上對(duì)最佳CU 選擇上的調(diào)度策略,在保證響應(yīng)時(shí)間接近最優(yōu)的情況下,以負(fù)載均衡的方式提升系統(tǒng)整體的吞吐量.

現(xiàn)有研究表明:啟發(fā)式調(diào)度策略解決算子分配問(wèn)題,WTAR 策略是最優(yōu)的方案.但是在更大的范圍來(lái)看,GDBMS 算子分配問(wèn)題是一個(gè)多目標(biāo)的優(yōu)化問(wèn)題,啟發(fā)式調(diào)度算子策略無(wú)法解決關(guān)聯(lián)算子切換CU 過(guò)程中引起的數(shù)據(jù)傳輸代價(jià),還需要進(jìn)一步改進(jìn)以擴(kuò)大優(yōu)化視野.

4.4 真實(shí)GDBMS系統(tǒng)中的優(yōu)化器

HyPE 優(yōu)化器框架采用可移植分層設(shè)計(jì),在很好地解決了查詢性能預(yù)測(cè)(query performance prediction)和算子分配問(wèn)題的基礎(chǔ)上,可通過(guò)與特定數(shù)據(jù)庫(kù)兼容的適配層,理論上有與任何GDBMS 結(jié)合的可能性[7,8,10?13,70].異構(gòu)查詢處理優(yōu)化引擎HyPE(a hybrid query-processing engine)[12,70,79]采用靈活的分層設(shè)計(jì),針對(duì)異構(gòu)環(huán)境下查詢物理優(yōu)化.該系統(tǒng)采用基于學(xué)習(xí)的方法,由3 個(gè)部分組成:代價(jià)估計(jì)器(cost estimator,簡(jiǎn)稱STEMOD)、算法選擇器(device-algorithm selector,簡(jiǎn)稱ALRIC)、異構(gòu)查詢優(yōu)化器(hybrid query optimizer,簡(jiǎn)稱HOPE).配合與特定數(shù)據(jù)庫(kù)適配層,有與任何GDBMS 配合使用的能力.通過(guò)與CoGaDB[10]結(jié)合,證明了其與基于CUDA 框架的GDBMS 的結(jié)合能力;而Ocelot[13]與HyPE 的融合,再次證明了硬件無(wú)關(guān)優(yōu)化器框架HyPE 能夠與所有基于OpenCL 的GDBMS 配合使用.圖3 描述了HyPE 的工作過(guò)程.

Fig.3 HyPE workflow圖3 HyPE 工作流程圖

? 首先,在HyPE 中,假設(shè)算子跟其處理的數(shù)據(jù)是一個(gè)整體OP(A,D),OP表示算子、A表示使用的算法、D表示處理的數(shù)據(jù),則物理執(zhí)行計(jì)劃可視為一個(gè)算子的流處理器.對(duì)于邏輯執(zhí)行樹進(jìn)行拓?fù)渑判騺?lái)序列化算子,消除算子間的數(shù)據(jù)依賴,保證每個(gè)算子執(zhí)行時(shí)其子算子均已執(zhí)行完畢;

? 其次,算子流中的算子依次經(jīng)過(guò)優(yōu)化器HyPE 中,經(jīng)由代價(jià)估計(jì)器(cost estimator,簡(jiǎn)稱STEMOD)[15,72]、算法選擇器(device-algorithm selector,簡(jiǎn)稱ALRIC)[15,72]、異構(gòu)查詢優(yōu)化器(hybrid query optimizer,簡(jiǎn)稱HOPE)[70],為特定算子選擇合適的實(shí)現(xiàn)算法,并根據(jù)啟發(fā)規(guī)則為算子分配合適的處理器.

HyPE 的3 個(gè)模塊內(nèi)部工作流程如圖4 所示,對(duì)于查詢計(jì)劃中的每個(gè)算子O,在算法選擇器中選出其對(duì)應(yīng)的CPUGPU 算法A,經(jīng)由代價(jià)估計(jì)器,以測(cè)試數(shù)據(jù)集D和算子的參數(shù)P運(yùn)行機(jī)器學(xué)習(xí)算法,估計(jì)對(duì)應(yīng)算法的代價(jià),最后由異構(gòu)查詢優(yōu)化器按照啟發(fā)式規(guī)則選擇最終的算法和執(zhí)行計(jì)算核心,并將選擇結(jié)果反饋給系統(tǒng)作為后續(xù)代價(jià)估計(jì)的依據(jù).

Fig.4 HyPE architecture[12]圖4 HyPE 架構(gòu)圖[12]

盡管HyPE 優(yōu)化器基于機(jī)器學(xué)習(xí)的方法估計(jì)算子執(zhí)行代價(jià),并組合多種啟發(fā)式規(guī)則選擇算子的物理實(shí)現(xiàn)算法,但是將查詢優(yōu)化問(wèn)題等價(jià)為在運(yùn)行時(shí)處理算子分配問(wèn)題的優(yōu)化策略對(duì)GDBMS 來(lái)說(shuō)未必是最有效的.文獻(xiàn)[80]指出了HyPE 采用局部?jī)?yōu)化(local optimize)策略,直到優(yōu)化期再考慮的算子分配問(wèn)題,由于將每個(gè)算子看成一個(gè)獨(dú)立的個(gè)體,采用貪心策略為算子分配處理器,由于缺乏全局視野容易陷入局部最優(yōu)解,還可能會(huì)造成不必要的數(shù)據(jù)傳輸代價(jià).該文提出了從編譯期開始考慮算子分配問(wèn)題的全局優(yōu)化(global optimize)策略,該方法統(tǒng)籌考慮整個(gè)執(zhí)行計(jì)劃(QEP)各算子之間的依賴關(guān)系,鼓勵(lì)算子間共享數(shù)據(jù)來(lái)消除可能的數(shù)據(jù)拷貝.全局視野下考慮算子分配問(wèn)題,主要存在兩個(gè)問(wèn)題:首先,優(yōu)化要考慮的問(wèn)題空間變大了,使得算子分配的復(fù)雜度成指數(shù)增長(zhǎng);其次,物化中間結(jié)果的空間大小難以精確估計(jì),也增大了算子級(jí)聯(lián)失敗的可能.

此外,PG-Storm[81],brytlyt/BrytlytDB[82]基于開源數(shù)據(jù)庫(kù)PostgreSQL,復(fù)用了PostgreSQL 優(yōu)化器模塊,通過(guò)計(jì)算cost,在查詢執(zhí)行加護(hù)中插入適合的GPU 算子(Join、Scan、聚合等),將計(jì)算任務(wù)分配到GPU 端加速,取得了較好的效果.這種編譯期靜態(tài)分配的任務(wù)分配策略,避免了HyPE 優(yōu)化器在運(yùn)行時(shí)決策算子分配問(wèn)題的負(fù)載,可以取得確定性的性能提升.但是這種方法只能對(duì)Join 等GPU 與對(duì)應(yīng)CPU 算子性能相差懸殊的一類算子起作用,放棄了大多數(shù)可用GPU 加速查詢的機(jī)會(huì);同時(shí),由于體系結(jié)構(gòu)上的差距,無(wú)法結(jié)合列式存儲(chǔ)等OLAP 分析任務(wù)上行之有效的優(yōu)化方法使用,整體性能提升不如純粹的GDBMS 高.Ocelot[35]克服了PostgreSQL 行式處理的弊端,同時(shí)可以借助MonetDB 的優(yōu)化器進(jìn)行查詢優(yōu)化,采用規(guī)則化的決策策略,盡可能將計(jì)算任務(wù)部署到GPU 端來(lái)加速查詢.Ocelot 優(yōu)化方案存在如下弊端:首先,Ocelot 的優(yōu)化器依賴于MonetDB 查詢優(yōu)化器,并沒(méi)有考慮異構(gòu)環(huán)境下的查詢優(yōu)化問(wèn)題;其次,Ocelot 采用靜態(tài)分配算子策略,不如HyPE 運(yùn)行時(shí)動(dòng)態(tài)分配算子高效.因此,有研究[13]將Ocelot 與HyPE 結(jié)合,引入了動(dòng)態(tài)算子分配策略.此外,文獻(xiàn)[80]進(jìn)一步引入了全局優(yōu)化的策略,盡管全局優(yōu)化效果與局部?jī)?yōu)化提升有限.

4.5 小 結(jié)

傳統(tǒng)數(shù)據(jù)庫(kù)的經(jīng)驗(yàn)表明,未經(jīng)優(yōu)化的執(zhí)行計(jì)劃和最優(yōu)執(zhí)行計(jì)劃之間的性能差異是巨大的.考慮到異構(gòu)計(jì)算環(huán)境特點(diǎn)、代價(jià)模型的變化、最優(yōu)連接順序問(wèn)題、算子分配問(wèn)題、PCIe 瓶頸問(wèn)題、查詢規(guī)模估計(jì)等難題,異構(gòu)查詢優(yōu)化問(wèn)題更加復(fù)雜.未來(lái),人工智能賦能的異構(gòu)查詢優(yōu)化器將成為研究的熱點(diǎn),在GDBMS 的架構(gòu)中發(fā)揮核心關(guān)鍵作用.

5 存儲(chǔ)管理

數(shù)據(jù)庫(kù)管理系統(tǒng)的任務(wù),本質(zhì)上是在一定的存儲(chǔ)介質(zhì)上讀寫數(shù)據(jù).因此,存儲(chǔ)管理器成為其密不可分的關(guān)鍵模塊.傳統(tǒng)的DBMS 與GDBMS 在存儲(chǔ)管理器上存在以下不同.

? 第一,從功能上說(shuō),面向磁盤的數(shù)據(jù)庫(kù)主要包括內(nèi)存管理和外存管理兩部分;而對(duì)于GDBMS 來(lái)說(shuō),還增加了GPU 顯存管理的任務(wù).如何充分發(fā)揮異構(gòu)存儲(chǔ)體系的性能優(yōu)勢(shì),是GDBMS 數(shù)據(jù)管理最核心的問(wèn)題;

? 第二,壓縮數(shù)據(jù)能夠有效減少需要處理的數(shù)據(jù)總量,進(jìn)而成比例增加GDBMS 的性能.如何在GPU 異構(gòu)顯存體系下盡可能獲得更大的壓縮比,充滿了挑戰(zhàn);

? 第三,索引能夠加速以硬盤為中心的數(shù)據(jù)查詢處理,但是在GDBMS 大量物化的全量處理模型中是否還有存在的價(jià)值、如何發(fā)揮索引長(zhǎng)處加速查詢處理,也是GDBMS 存儲(chǔ)管理需要研究的重要問(wèn)題.

本節(jié)將就GDBMS 存儲(chǔ)管理面對(duì)的挑戰(zhàn)、GPU 數(shù)據(jù)壓縮技術(shù)、GPU 數(shù)據(jù)索引技術(shù)以及提升GDBMS 處理數(shù)據(jù)容量的軟硬件技術(shù)進(jìn)行深入細(xì)致的分析,希望對(duì)未來(lái)的GDBMS 研究和開發(fā)有所啟發(fā).

5.1 GDBMS數(shù)據(jù)存儲(chǔ)體系

在數(shù)據(jù)存儲(chǔ)模型上,列式存儲(chǔ)在OLAP 業(yè)務(wù)中比行式存儲(chǔ)在性能上有明顯優(yōu)勢(shì)[27,36],業(yè)已成為絕大多數(shù)GDBMS 的選擇.

? 第一,列式存儲(chǔ)更方便壓縮.屬性值之間值域有限、高相似度、等位寬等特點(diǎn)可以獲得更高效的壓縮解壓縮算法、獲得更高的壓縮比,甚至可以直接用壓縮格式進(jìn)行查詢處理.比如采用字典壓縮的方式下,完全可以在壓縮形式的數(shù)據(jù)上進(jìn)行查詢操作而無(wú)需引入解壓縮的負(fù)載;

? 第二,列式存儲(chǔ)減少了需要處理的數(shù)據(jù)容量.由于分析類查詢往往只涉及記錄中有限的屬性列,列式存儲(chǔ)可以實(shí)現(xiàn)“物理投影”,進(jìn)而減少不必要的數(shù)據(jù)獲取、處理開銷;其次,使用盡可能晚的物化操作、通過(guò)“位置”等中間信息生成最終結(jié)果,而在查詢處理過(guò)程中無(wú)需進(jìn)行多余的行式結(jié)果構(gòu)造,也對(duì)性能提升幫助很大,比如CoGaDB 使用tid 在GPU 和CPU 之間傳遞中間結(jié)果;

? 第三,列式存儲(chǔ)更適合GPU 處理.由于關(guān)系表中一個(gè)列內(nèi)的數(shù)據(jù)在數(shù)據(jù)類型上一致,因此對(duì)列中每個(gè)元素的處理存在等價(jià)性,設(shè)計(jì)向量化算法非常適合GPU 的大規(guī)模并發(fā)編程模型.

在此基礎(chǔ)上,一些針對(duì)列式存儲(chǔ)的優(yōu)化方法(比如invisible join[36])、GPU 顯存的聚合操作特性,也是行存儲(chǔ)無(wú)法比擬的.但是列式存儲(chǔ)更適合OLAP 業(yè)務(wù),對(duì)于OLTP 事務(wù)處理有天然的短板,列式存儲(chǔ)將讓GDBMS 難以適應(yīng)OLTP 業(yè)務(wù).

在數(shù)據(jù)存儲(chǔ)位置上,由于GDBMS 需要管理硬盤(包括機(jī)械鍵盤和SSD 等)、內(nèi)存(CPU 端)和GPU 顯存這3層存儲(chǔ)結(jié)構(gòu),其中,GPU 顯存包含了超過(guò)8 種不同類型的存儲(chǔ)空間——全局顯存(global)、共享顯存(shared)、常量顯存(constant)、紋理顯存(texture)以及各級(jí)緩存(cache),GDBMS 的存儲(chǔ)管理需要考慮的空間變大了.文獻(xiàn)[83]提出了一種度量因存儲(chǔ)數(shù)據(jù)位置不同而造成程序性能不同的方法,幫助程序開發(fā)人員自動(dòng)尋找最佳的數(shù)據(jù)存儲(chǔ)布局方案,但該方案并不是針對(duì)關(guān)系型數(shù)據(jù)庫(kù)的.該研究表明,GPU 指令重試、地址編碼模式、訪存指令隊(duì)列等待延遲、各級(jí)緩存失效效應(yīng)是造成GPU 顯存不同存儲(chǔ)位置性能差異的主要原因.因此,GDBMS 的存儲(chǔ)管理與傳統(tǒng)的DBMS 和內(nèi)存數(shù)據(jù)庫(kù)類似,數(shù)據(jù)需要存儲(chǔ)在大而慢的硬盤存儲(chǔ)器上,但在快而小的GPU 顯存中查詢處理.不同之處在于:數(shù)據(jù)可以在主機(jī)內(nèi)存和設(shè)備顯存上分別計(jì)算,帶來(lái)了優(yōu)化的可能.

GDBMS 普遍采用內(nèi)存駐留(memory-resident)的技術(shù),將數(shù)據(jù)盡可能放在內(nèi)存中(甚至放在GPU 顯存上)來(lái)避免磁盤IO 瓶頸.文獻(xiàn)[17]指出:GDB 系統(tǒng)對(duì)于稍大于內(nèi)存的數(shù)據(jù)進(jìn)行TPC-H 測(cè)試時(shí),相對(duì)于CPU 加速方案,性能僅提高23%;而對(duì)于全內(nèi)存駐留數(shù)據(jù),GPU 方案可提供多達(dá)27 倍的加速比.來(lái)自MapD[5]系統(tǒng)的數(shù)據(jù)表明:相對(duì)于訪問(wèn)駐留硬盤(1GB/s～2GB/s)上的數(shù)據(jù),全內(nèi)存(32GB～3TB)計(jì)算速度為 70 GB/s～120GB/s,加速比為35～120;而如果只用 GPU 顯存存放數(shù)據(jù)(容量可達(dá) 384GB),速度為 3000GB/s～5000GB/s,加速比可達(dá)1500～5000.MapD 通過(guò)將渲染引擎融入數(shù)據(jù)庫(kù)內(nèi)核,使得數(shù)據(jù)可視化的速度接近GPU 處理的極限,對(duì)于交互式商業(yè)智能圖表、空間數(shù)據(jù)分析、聚合統(tǒng)計(jì)等無(wú)需返回原始數(shù)據(jù)的應(yīng)用起到了極大的加速作用.但是對(duì)于傳統(tǒng)的ad-hoc 查詢,由于GPU 只能加速存放于內(nèi)存的數(shù)據(jù),GDBMS 的處理速度實(shí)際上還遠(yuǎn)未達(dá)到GPU 顯存的極限.一些GDBMS 直接將整個(gè)數(shù)據(jù)庫(kù)駐留在GPU 顯存中,由于GPU 片內(nèi)顯存比PCIe 總線速率高16 倍,因此可以預(yù)見,這種方法可以有效提升性能.同時(shí),這也簡(jiǎn)化了數(shù)據(jù)管理,不需要額外考慮如何保證內(nèi)存和顯存的數(shù)據(jù)一致性.但是,這極大限制了GDBMS 的數(shù)據(jù)容量,因?yàn)榧幢闶褂枚鄩K顯卡,總顯存容量跟內(nèi)存的容量相比仍然有數(shù)倍的差距.

如果只用內(nèi)存完全不用硬盤,會(huì)極大增加部署GDBMS 系統(tǒng)的成本,限制GDBMS 能夠處理的數(shù)據(jù)容量,并且內(nèi)存斷電后數(shù)據(jù)丟失的特性,也給數(shù)據(jù)安全帶來(lái)挑戰(zhàn),在與其他大數(shù)據(jù)處理系統(tǒng)競(jìng)爭(zhēng)中也將失去優(yōu)勢(shì).商業(yè)的GDBMS 普遍采用硬盤存儲(chǔ)數(shù)據(jù),在系統(tǒng)加載時(shí),將數(shù)據(jù)盡可能部署到內(nèi)存中,并利用基于代價(jià)的優(yōu)化器或啟發(fā)式規(guī)則,盡可能地選擇GPU 進(jìn)行查詢處理.PG-Storm[81]系統(tǒng)引入了SSD 數(shù)據(jù)通過(guò)PCIe 總線直接向GPU 發(fā)送查詢數(shù)據(jù)的功能,未來(lái)有望在不增加IO 瓶頸的前提下,將大容量非易失性存儲(chǔ)引入到GDBMS 體系當(dāng)中.SPIN[84]則在文件系統(tǒng)層級(jí)上通過(guò)內(nèi)存頁(yè)面緩存、GPU 數(shù)據(jù)預(yù)讀、輕量級(jí)硬盤地址轉(zhuǎn)換,解決了GPU 和SSD 硬盤之間的點(diǎn)對(duì)點(diǎn)(P2P)數(shù)據(jù)傳輸問(wèn)題.該方法建立了GPU 版的DMA 機(jī)制,無(wú)需CPU 控制,降低了系統(tǒng)的管理負(fù)載;同時(shí),不需要內(nèi)存作為“跳板”,有效減少了PCIe 總線瓶頸,對(duì)GDBMS 的發(fā)展具有重要的啟發(fā)意義.

現(xiàn)有研究型GDBMS 原型系統(tǒng),如CoGaDB,GPUQP,GPUDB,OmniDB 等都針對(duì)單顯卡系統(tǒng),鮮有多顯卡GDBMS 的相關(guān)研究,限制GDBMS 容量擴(kuò)展的一個(gè)直觀因素是顯卡的容量.但是相應(yīng)的GPU 單塊顯卡的顯存容量上的提升不像其計(jì)算能力的增長(zhǎng)迅速,比如K80 顯卡通過(guò)集成兩塊GPU 核心已經(jīng)可以達(dá)到24GB 的顯存,最新一代Nvidia 顯卡單塊容量普遍還是在12G～16G 之間,雖然最高容量已經(jīng)達(dá)到64GB,但相應(yīng)的價(jià)格也過(guò)于昂貴.商業(yè)GDBMS 在這方面走在了研究界的前面.將多塊GPU 合并處理SQL 請(qǐng)求,是擴(kuò)展數(shù)據(jù)庫(kù)處理能力、提高數(shù)據(jù)庫(kù)容量的自然解決方案.DB2 BLU[85]數(shù)據(jù)庫(kù)引入多顯卡處理查詢機(jī)制,通過(guò)統(tǒng)一管理多GPU 顯存,統(tǒng)計(jì)查詢對(duì)顯存的總需求,在運(yùn)行時(shí),根據(jù)各GPU 資源使用情況決定在哪個(gè)GPU 上執(zhí)行查詢?nèi)蝿?wù).MapD[5]通過(guò)聯(lián)合最多8 塊GPU 同時(shí)處理查詢請(qǐng)求,可以在GPU 顯存時(shí)處理1.5TB～3TB 的數(shù)據(jù),而內(nèi)存中數(shù)據(jù)更是多達(dá)15TB,以每秒2 600 億行的查詢處理速度.隨著GPU 計(jì)算能力的超摩爾定律發(fā)展,我們相信,現(xiàn)在的GBDMS 在數(shù)據(jù)處理速度上已經(jīng)遠(yuǎn)超內(nèi)存數(shù)據(jù)庫(kù).但是多GPU 系統(tǒng)中,單臺(tái)服務(wù)器PCIe 總線接口限制了可集成的GPU 數(shù)量.因此,單靠增加GPU 數(shù)來(lái)增加GDBMS 的數(shù)據(jù)容量的解決方案效果有限,需要引入分布式技術(shù),用集群來(lái)擴(kuò)充GDBMS 容量.這也是未來(lái)GDBMS 的一個(gè)重要發(fā)展方向.現(xiàn)有的GDBMS 多針對(duì)OLAP 業(yè)務(wù),數(shù)據(jù)一定時(shí)間內(nèi)保持不變,對(duì)于分布式橫向擴(kuò)展友好.比如:SQream DB[86]通過(guò)將存儲(chǔ)引擎獨(dú)立出來(lái),采用多查詢共享存儲(chǔ)的架構(gòu),在一定程度上實(shí)現(xiàn)了數(shù)據(jù)庫(kù)的橫向擴(kuò)展,提供從10TB～1PB 的OLAP 數(shù)據(jù)查詢?cè)品?wù).未來(lái),結(jié)合分布式技術(shù)的多顯卡系統(tǒng),將成為GDBMS 的發(fā)展方向.同時(shí),單卡多核GPU 架構(gòu)的scale up 擴(kuò)展方案也值得關(guān)注,文獻(xiàn)[87]提出一種評(píng)測(cè)NUMA GPU 架構(gòu)性能的GPUJoule 系統(tǒng),該系統(tǒng)可以模擬多達(dá)32 個(gè)GPU 核心的性能擴(kuò)展和能源效率指標(biāo)EDPSE(energy-delay-product scaling efficiency).研究表明,多核GPU 系統(tǒng)的設(shè)計(jì)難點(diǎn)在于GPU 的本地顯存(local memory)設(shè)計(jì)和GPU 核心間通信網(wǎng)絡(luò)的設(shè)計(jì),因?yàn)槟壳皢魏薌PU 的顯存帶寬還不足DRAM 理論上限的三分之一(300GB/S vs 900GB/S),提升空間巨大.可以預(yù)見:能夠充分發(fā)揮多核GPU 性能的GDBMS,無(wú)論采用橫向擴(kuò)展(scale out)還是縱向擴(kuò)展(scale up)的方式,都有巨大的性能潛力可以挖掘.

未來(lái),隨著GPU 顯存容量和速度的繼續(xù)提升和分布式技術(shù)的引入以及分片分區(qū)策略的使用,相信GDBMS會(huì)在數(shù)據(jù)庫(kù)容量上不斷提升,逐步拓展應(yīng)用場(chǎng)景,前景一片光明.

5.2 GPU數(shù)據(jù)壓縮

數(shù)據(jù)壓縮技術(shù)歷史悠久,早在關(guān)系代數(shù)理論創(chuàng)立之初,人們就致力于將數(shù)據(jù)壓縮用于到數(shù)據(jù)庫(kù)管理系統(tǒng)中來(lái).GDBMS 普遍采取壓縮技術(shù),以降低數(shù)據(jù)存儲(chǔ)空間,節(jié)約寶貴的內(nèi)存、顯存資源.采用壓縮技術(shù)存儲(chǔ)數(shù)據(jù),還可以降低設(shè)備與主機(jī)間必須傳輸?shù)臄?shù)據(jù)容量,緩解PCIe 總線瓶頸問(wèn)題.但是,利用壓縮技術(shù)引入了壓縮-解壓縮步驟,增加了系統(tǒng)響應(yīng)時(shí)延,在實(shí)踐中必須做出權(quán)衡.

在傳統(tǒng)的以CPU 計(jì)算為中心的內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)環(huán)境下,文獻(xiàn)[88]利用架構(gòu)方法的調(diào)查緩存和主存系統(tǒng)中的數(shù)據(jù)壓縮對(duì)近年來(lái)在緩存和內(nèi)存上應(yīng)用各類壓縮算法,達(dá)到提高性能、減少能耗的目的.該文希望能幫助理解壓縮算法的研究現(xiàn)狀,激勵(lì)研究者在設(shè)計(jì)現(xiàn)代計(jì)算系統(tǒng)時(shí)提升壓縮算法的效率、擴(kuò)大數(shù)據(jù)壓縮的應(yīng)用范圍.在內(nèi)存數(shù)據(jù)庫(kù)領(lǐng)域,HANA[15],MonetDB[38],C-store[89]往往采用字典壓縮、位圖壓縮等輕量級(jí)壓縮算法,達(dá)到在壓縮數(shù)據(jù)上直接查詢的目的.文獻(xiàn)[90]將數(shù)據(jù)壓縮集成到列式數(shù)據(jù)庫(kù)C-Store 系統(tǒng)中,使用多種(null suppression,dictionary encoding,run-length encoding,bit-vector encoding,lempel-ziv encoding)壓縮算法,并實(shí)現(xiàn)了多種壓縮數(shù)據(jù)格式之上直接運(yùn)行SQL 查詢,省去了解壓縮的過(guò)程.但是該文采用傳統(tǒng)的火山查詢模型,引起的分支惡化問(wèn)題并不適應(yīng)GPU 編程環(huán)境;其針對(duì)不同壓縮格式定制特定算子的處理模式會(huì)引起算子數(shù)量劇增的問(wèn)題,在算子匹配上也增加了優(yōu)化調(diào)度的難度.

適用于GDBMS 的壓縮算法選擇上必須遵守如下原則.

? 第一,必須是無(wú)損壓縮算法,因?yàn)閿?shù)據(jù)庫(kù)業(yè)務(wù)的要求,數(shù)據(jù)如果壓縮后有損失,那么勢(shì)必影響查詢的準(zhǔn)確性,任何以損失業(yè)務(wù)正確性來(lái)提升性能的措施都是不可取的;

? 第二,一般采用輕量、上下文相關(guān)度低的壓縮算法,這樣壓縮-解壓縮過(guò)程的負(fù)載開銷不大,不會(huì)造成嚴(yán)重的性能問(wèn)題;

? 第三,解壓縮算法應(yīng)該易于并行化,方便利用GPU 富裕的計(jì)算資源.相比于壓縮過(guò)程,解壓縮流程一般處于查詢處理的關(guān)鍵路徑上,對(duì)查詢速率的影響更加關(guān)鍵;

? 第四,多種壓縮算法可以組合使用,進(jìn)一步提高壓縮比.而如何選擇合適的組合策略,將會(huì)成為將來(lái)研究的熱點(diǎn).

在GPU 數(shù)據(jù)庫(kù)中,Kinetica 為用戶提供snappy 等傳統(tǒng)數(shù)據(jù)塊壓縮算法,在查詢執(zhí)行之前先解壓再在未壓縮數(shù)據(jù)上執(zhí)行查詢.這樣雖然可以支持全部的SQL 查詢算子,但是代價(jià)也非常巨大.文獻(xiàn)[91]分別在GDB 以及MonetDB 上組合使用9 種輕量級(jí)壓縮算法,提出部分壓縮模式,并將數(shù)據(jù)壓縮引入到代價(jià)估計(jì)模型中,通過(guò)優(yōu)化器生成考慮數(shù)據(jù)壓縮因素的異構(gòu)SQL 查詢執(zhí)行計(jì)劃.研究表明:GDBMS 通過(guò)使用數(shù)據(jù)壓縮技術(shù),可以大幅減少PCIe 總線傳輸數(shù)據(jù)量,進(jìn)而將整個(gè)查詢運(yùn)行時(shí)間提升一個(gè)數(shù)量級(jí).文獻(xiàn)[92]用輕量級(jí)壓縮算法WAH 壓縮位圖索引以支持范圍查詢,數(shù)據(jù)首先以壓縮形式發(fā)送給GPU,再在GPU 上以DecompressVector 技術(shù)解決WAH 壓縮數(shù)據(jù)無(wú)法用GPU 并行處理的問(wèn)題,實(shí)現(xiàn)了在壓縮數(shù)據(jù)上直接進(jìn)行查詢,性能較CPU 并行算法最高提升了87.7 倍.

在GPGPU 研究領(lǐng)域,一些研究通過(guò)在現(xiàn)有的異構(gòu)計(jì)算環(huán)境軟硬件棧的不同位置引入壓縮-解壓縮緩沖層的方案,對(duì)加速GDBMS 也許有借鑒價(jià)值.文獻(xiàn)[93]提出了CABA 方法,使用輔助線程族,利用GPU 的空閑計(jì)算資源對(duì)數(shù)據(jù)進(jìn)行壓縮-解壓縮操作,以消除顯存帶寬瓶頸.CABA 方法采用軟硬件結(jié)合的設(shè)計(jì)理念,在GPU 每個(gè)SM控制器中上增加了輔助線程代碼存儲(chǔ)器、控制器、數(shù)據(jù)緩沖區(qū)這3 個(gè)硬件基礎(chǔ)設(shè)施,使數(shù)據(jù)以壓縮形式存儲(chǔ)于顯存中,并在調(diào)入cache 之前進(jìn)行解壓縮.文獻(xiàn)[94]提出了Warped-Compression(WC)方法,利用同一線程族warp之內(nèi)每個(gè)線程之間的寄存器內(nèi)容相似度高的特點(diǎn),對(duì)GPU 中數(shù)量眾多的寄存器文件進(jìn)行壓縮.文獻(xiàn)[95]使用GPGPU-sim 模擬器改變GPU 顯存控制器MC,對(duì)來(lái)自PCIe 總線的數(shù)據(jù)進(jìn)行壓縮解壓縮操作,實(shí)現(xiàn)了浮點(diǎn)型數(shù)據(jù)的有損和無(wú)損壓縮算法.HippogriffDB[22]綜合運(yùn)用多種壓縮算法,用GPU 的計(jì)算能力換取高效的數(shù)據(jù)傳輸速率.為解決不同查詢適應(yīng)不用壓縮算法的問(wèn)題,HippogriffDB 采用同表多壓縮格式,并在查詢時(shí)采用自適應(yīng)壓縮的方法;為解決PCIe 傳輸瓶頸,HippogriffDB 使用SSD 到GPU 直接傳輸壓縮數(shù)據(jù)的辦法來(lái)提升整體性能.實(shí)驗(yàn)表明,HippogriffDB 可以取得比MonentDB 快100 倍、比YDB 快10 倍的加速比.

壓縮算法的引入可以有效減少數(shù)據(jù)的總?cè)莘e,同時(shí)在輕量級(jí)壓縮上可以直接查詢,消除了解壓縮負(fù)載,進(jìn)而全面提升GDBMS 的性能.在未來(lái)的研究中,適應(yīng)于GPU 處理的易并行、壓縮比更大的壓縮算法將成為研究的重點(diǎn).而在應(yīng)用領(lǐng)域,輕量級(jí)壓縮算法的使用會(huì)越來(lái)越多,并逐漸尋找大壓縮比算法的適用場(chǎng)景.

5.3 GPU索引技術(shù)

傳統(tǒng)數(shù)據(jù)庫(kù)中,使用B+樹等索引結(jié)構(gòu)減少訪問(wèn)數(shù)據(jù)時(shí)磁盤讀寫的負(fù)載.在GDBMS 中,由于索引結(jié)構(gòu)在訪存特性上的隨機(jī)性,不滿足GPU 對(duì)齊合并訪問(wèn)的特點(diǎn),傳統(tǒng)的索引結(jié)構(gòu)照搬到GPU 異構(gòu)計(jì)算環(huán)境下性能不高;甚至,由于GDBMS 全內(nèi)存存儲(chǔ)和一次一算子全物化的查詢處理方式,不使用索引一樣可以達(dá)到很高的性能.因此,在GDBMS 中,如果使用全顯存存儲(chǔ)數(shù)據(jù),索引可能是多余的模塊;但對(duì)于要直接從硬盤存取數(shù)據(jù)的GDBMS,索引可在絕大多數(shù)情況下有效消除了磁盤IO.比如:PG-Storm 由于要從磁盤讀取數(shù)據(jù),且無(wú)法改變PostgreSQL 的存儲(chǔ)引擎,因此選擇用BRIN-index 減少查詢需要傳輸?shù)紾PU 的數(shù)據(jù)量[81].

使用全內(nèi)存存儲(chǔ)的內(nèi)存數(shù)據(jù)庫(kù)中,索引查詢成為新的性能瓶頸.文獻(xiàn)[96]在內(nèi)存KV 系統(tǒng)中使用GPU 加速索引查詢來(lái)消除內(nèi)存KV 主要的性能瓶頸,提出一種駐留GPU 顯存的哈希表作為索引結(jié)構(gòu).此外,設(shè)計(jì)良好的索引結(jié)構(gòu)也對(duì)連接算子的性能產(chǎn)生巨大的影響[42,48].在算法加速層面,一些Join 算法[42,48]為了增加公平性,通過(guò)手動(dòng)添加索引的方式實(shí)現(xiàn)了GPU-Join 算子,并對(duì)比CPU 版本取得了10 倍的加速比.文獻(xiàn)[15]在單個(gè)算子粒度下考慮索引讀取數(shù)據(jù)(index scan)是否是對(duì)整個(gè)查詢有利,并提出尋找性能均衡點(diǎn)(break-even point),對(duì)于是否走索引的優(yōu)化決策起到關(guān)鍵作用.表2 中列出了現(xiàn)有對(duì)GPU 索引相關(guān)的研究工作及突出貢獻(xiàn).

Table 2 Research status of GPU index表2 GPU 索引研究現(xiàn)狀

基于樹的索引使用分層查找的策略,用盡可能訪問(wèn)少的內(nèi)部節(jié)點(diǎn)而找到真正記錄tuple 的位置信息,進(jìn)而將對(duì)整個(gè)數(shù)據(jù)空間的查找范圍縮短為最多為樹高的多個(gè)內(nèi)部節(jié)點(diǎn)的查找.一般分為創(chuàng)建索引、索引搜索、更新索引這3 個(gè)步驟.在索引查找步驟中,GPU 的實(shí)現(xiàn)方式重點(diǎn)在單個(gè)數(shù)組內(nèi)找到特定值的指向位置,可安排線程塊中每個(gè)線程記住內(nèi)部節(jié)點(diǎn)的鍵,使用map 原語(yǔ)進(jìn)行比較,將結(jié)果用reduce 原語(yǔ)統(tǒng)計(jì),執(zhí)行下一步查找.與CPU 方案針對(duì)Cache 塊進(jìn)行優(yōu)化不同,GPU 中shared memory 更大,對(duì)樹節(jié)點(diǎn)大小要求不高,因而可以在GPU 上實(shí)現(xiàn)樹高更低的索引結(jié)構(gòu),加上GPU 大規(guī)模并發(fā)計(jì)算能力的貢獻(xiàn),GPU 索引查詢效率更高.FAST[99]通過(guò)根據(jù)硬件架構(gòu)特性(頁(yè)大小、cache 塊、SIMD 指令位寬等)自調(diào)整節(jié)點(diǎn)大小,使用軟件流水線、數(shù)據(jù)預(yù)取等技術(shù)手段,在查詢計(jì)算的同時(shí)預(yù)取下一層節(jié)點(diǎn)的方式隱藏訪存延遲,并嘗試用壓縮技術(shù)提升整體性能.研究表明:在小節(jié)點(diǎn)樹上,CPU的性能更高;而對(duì)大節(jié)點(diǎn)樹上,GPU 性能更高,但是相對(duì)于GPU 的峰值計(jì)算能力,索引計(jì)算的效果不佳.HBTree[98]則通過(guò)在CPU-GPU 之間提供復(fù)雜均衡策略,利用內(nèi)存和顯存存儲(chǔ)索引樹結(jié)構(gòu),解決了索引樹體積超過(guò)GPU 顯存的問(wèn)題,取得了較好的索引查詢性能,并支持批量更新索引操作.

以上使用GPU 加速索引操作的研究取得了可喜的成果,但GDBMS 普遍將數(shù)據(jù)存儲(chǔ)在內(nèi)存中,避免了傳統(tǒng)數(shù)據(jù)庫(kù)中最影響性能的磁盤IO 瓶頸,因而索引是否是必要的模塊有待研究.另一方面,OLAP 業(yè)務(wù)涉及數(shù)據(jù)量大,在數(shù)據(jù)獲取上多采用全表掃描、全物化策略執(zhí)行查詢,這都進(jìn)一步減少了索引存在的必要性.但是對(duì)于OLTP業(yè)務(wù),單個(gè)事務(wù)的數(shù)據(jù)獲取量少,GPU 索引就能發(fā)揮應(yīng)有的作用.未來(lái),GPU 加速索引查詢的研究方向?qū)@可更新索引、加速Join 算子、高效空間數(shù)據(jù)索引這3 個(gè)方向展開.

5.4 小 結(jié)

異構(gòu)存儲(chǔ)體系下GPU 數(shù)據(jù)的存儲(chǔ)管理、壓縮和索引是GDBMS 存儲(chǔ)管理器的核心功能,一方面要高效利用“小而快”的GPU 顯存降低查詢響應(yīng)時(shí)延提高吞吐量;另一方面,又要利用SSD、硬盤存儲(chǔ)空間大、可持久存儲(chǔ)的特點(diǎn),增大GDBMS 能夠處理數(shù)據(jù)的總量和高可用性,同時(shí)還要盡可能減少PCIe 上的數(shù)據(jù)遷移.

6 總結(jié)

近10 年間,尤其是CUDAOpenCL 異構(gòu)統(tǒng)一計(jì)算語(yǔ)言的提出,使得GPU 成為數(shù)據(jù)庫(kù)可用的強(qiáng)大的可編程的通用協(xié)處理器,并涌現(xiàn)了一大批面向復(fù)雜查詢的商用GDBMS 或研究原型,這必將深刻改變高性能數(shù)據(jù)庫(kù)系統(tǒng)的格局.數(shù)據(jù)庫(kù)系統(tǒng)作為數(shù)據(jù)密集型系統(tǒng)應(yīng)用軟件,其性能的提升依賴于數(shù)據(jù)獲取能力和計(jì)算能力的分別大規(guī)模提升:前者的提升依賴于大容量?jī)?nèi)存計(jì)算、分布式技術(shù)、SSD 磁盤陣列、NVM[102]新型存儲(chǔ)介質(zhì)以及與之配套的高性能數(shù)據(jù)結(jié)構(gòu)和算法的開發(fā);后者則受到CPU 摩爾定律制約而發(fā)展緩慢.GDBMS 的興起和發(fā)展,證明了通用GPU 的大規(guī)模線程并發(fā)計(jì)算模式在關(guān)系型數(shù)據(jù)處理上是可行的和高效的,為數(shù)據(jù)庫(kù)計(jì)算能力取得突破性進(jìn)展提供了一種新的可能.

盡管如此,GPU 并不是專為關(guān)系型數(shù)據(jù)處理而開發(fā),其硬件體系結(jié)構(gòu)還有很多不適應(yīng)GDBMS 發(fā)展的地方,未來(lái)需要在如下幾個(gè)方面進(jìn)一步研究.

? 對(duì)于GDBMS 查詢編譯器,一方面,以代碼即時(shí)生成JIT 技術(shù)和LLVM 編譯技術(shù)為依托,進(jìn)一步壓縮SQL的編譯時(shí)間,是未來(lái)GDBMS 查詢編譯器的研究方向.同時(shí),如何充分利用不同架構(gòu)、不同廠商GPU 功能特性的同時(shí),保證SQL 編譯器的穩(wěn)定高效,也是研究熱點(diǎn)之一.另一方面,在“一次一算子”編譯模式下,以更多粒度批量編譯查詢請(qǐng)求,為不同規(guī)模的查詢需求編譯出規(guī)模適中的查詢計(jì)劃或多個(gè)查詢計(jì)劃的組合,避免因資源限制導(dǎo)致的查詢失敗,提高系統(tǒng)的穩(wěn)定性,是GDBMS 編譯器在數(shù)據(jù)處理模式上的新挑戰(zhàn).同時(shí),考慮數(shù)據(jù)所在位置(是否在GPU 顯存上)和系統(tǒng)運(yùn)行狀態(tài)生成“動(dòng)態(tài)”的查詢計(jì)劃,是未來(lái)的研究熱點(diǎn)之一.總之,GDBMS 查詢編譯器主要面臨壓縮異構(gòu)查詢計(jì)劃的編譯時(shí)間和根據(jù)不同數(shù)據(jù)查詢規(guī)模、存儲(chǔ)位置而生成高效查詢計(jì)劃兩方面的挑戰(zhàn);

? 在GDBMS 查詢處理器領(lǐng)域,數(shù)據(jù)庫(kù)算法的GPU 改造將成為未來(lái)主要的研究方向,尤其是以Join 為代表的復(fù)雜關(guān)系算子的GPU 高效實(shí)現(xiàn),將成為GDBMS 性能提升的關(guān)鍵.此外,通過(guò)與查詢編譯器和查詢優(yōu)化器協(xié)同,KBE 對(duì)核函數(shù)的融合與切分的智能化、動(dòng)態(tài)化乃至跨GPU 改造,將成為GDBMS 執(zhí)行引擎的研究熱點(diǎn)之一.而在功能上,GDBMS 對(duì)OLTP 業(yè)務(wù)支撐離不開對(duì)事務(wù)ACID 屬性的支持,這將成為GDBMS 亟待突破的難點(diǎn),也成為最有潛力的研究方向之一;

? GDBMS 查詢優(yōu)化器的研究,將逐漸從以算子為中心到以查詢計(jì)劃樹(QEP)為核心轉(zhuǎn)變.以算子為單位的查詢優(yōu)化在異構(gòu)查詢代價(jià)模型、算子選擇率、算子分配問(wèn)題上取得了階段性成果,尤其是以機(jī)器學(xué)習(xí)方法估計(jì)算子查詢代價(jià)的HyPE 框架的提出,給GDBMS 查詢優(yōu)化器的設(shè)計(jì)提供了范本.但算子層次的優(yōu)化缺乏全局視野,無(wú)法保證生成最優(yōu)的查詢計(jì)劃.未來(lái),以降低整個(gè)查詢計(jì)劃樹的異構(gòu)執(zhí)行代價(jià)為目標(biāo)的全局優(yōu)化方案,是 GDBMS 查詢優(yōu)化器的研究重點(diǎn).此外,多表連接的最佳順序問(wèn)題,仍是GDBMS 優(yōu)化器未解難題之一,其動(dòng)態(tài)規(guī)劃解決方案尚沒(méi)有GPU 版本的算法;

? 在GDBMS 存儲(chǔ)管理器方面,列式存儲(chǔ)、全GPU 計(jì)算、內(nèi)存數(shù)據(jù)駐留帶來(lái)的超高的計(jì)算性能仍是GDBMS 的基石,但固態(tài)硬盤SSD 的引入十分必要,在高速度和大容量之間的權(quán)衡,將是GDBMS 存儲(chǔ)引擎設(shè)計(jì)的主要問(wèn)題.未來(lái),在降低性能前提下提升存儲(chǔ)容量,將成為GDBMS 存儲(chǔ)引擎未來(lái)的研究方向,SSD 與GPU 數(shù)據(jù)直連、跨GPU 分布式存儲(chǔ)等技術(shù)非常有潛力.在數(shù)據(jù)壓縮方面,研究降低解壓縮成本為核心的輕量級(jí)GPU 數(shù)據(jù)壓縮算法,比更高壓縮比的通用GPU 壓縮算法對(duì)GDBMS 系統(tǒng)來(lái)說(shuō)更為重要.對(duì)于GPU 索引的研究,算法層面將向減少全局?jǐn)?shù)據(jù)同步點(diǎn)、面向更新的數(shù)據(jù)結(jié)構(gòu)、降低PCIe瓶頸方向努力;而在系統(tǒng)層面,將繼續(xù)探索GPU 索引技術(shù)在GDBMS 中的應(yīng)用場(chǎng)景.

可以預(yù)見:隨著GPU 性能隨摩爾定律而提升和GDBMS 四大核心模塊技術(shù)的發(fā)展,GDBMS 一定會(huì)在技術(shù)上越來(lái)越成熟、性能優(yōu)勢(shì)越來(lái)越明顯,從而在根本上改變當(dāng)下數(shù)據(jù)處理系統(tǒng)軟件的格局.