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

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

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

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

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

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

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

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

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

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

商用GDBMS 中,進一步可以分為3 類.

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

? 第2 類是非內(nèi)存型GDBMS,使用GPU 完成全部或者大部分數(shù)據(jù)庫關(guān)系運算,可以分析超過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.

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

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

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

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

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

2 查詢編譯器

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

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

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

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

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

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

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

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

2.1 GDBMS編譯模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 查詢處理器

GDBMS 查詢處理引擎接受處理查詢編譯器輸出的查詢計劃樹QEP(query execution plan)并執(zhí)行查詢返回結(jié)果,是利用GPU-CPU 異構(gòu)計算處理用戶查詢請求的核心模塊.從功能角度來看,GDBMS 查詢處理引擎面對的核心問題就是如何利用GPU 實現(xiàn)關(guān)系代數(shù)運算,即實現(xiàn)選擇、投影、連接、聚合基本的關(guān)系算子,同時還需要實現(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)系查詢樹來最大化查詢處理性能,是GDBMS 面臨的性能挑戰(zhàn).

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

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

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

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

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

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

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

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

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

3.2.1 Join 算子

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

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

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

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

聚集函數(shù)算子是又一個計算負載很高(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ù),提供給用戶強大的分類匯總復(fù)雜信息的能力.借助GPU 高并發(fā)高性能計算能力加速聚集函數(shù)算子,可以有效提升GDBMS競爭力.

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 GPU事務(wù)處理

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

3.6 小 結(jié)

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

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

4 查詢優(yōu)化器

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

4.1 代價模型

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

4.1.1 GDBMS 代價模型之難

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

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

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

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

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

4.1.2 算子代價估計的方法

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

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

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

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

4.1.3 算子的選擇率估計

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

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

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

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

4.2 查詢重寫

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

4.2.1 join 算子改寫

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

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

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

4.2.2 減少copy 算子

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5 小 結(jié)

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

5 存儲管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

? 第四,多種壓縮算法可以組合使用,進一步提高壓縮比.而如何選擇合適的組合策略,將會成為將來研究的熱點.

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

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

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

5.3 GPU索引技術(shù)

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

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

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

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

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

5.4 小 結(jié)

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

6 總結(jié)

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

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

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

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

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

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

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