GPU 數據庫核心技術綜述?

裴 威,李戰懷,潘 巍

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

2(錦州醫科大學,遼寧 錦州 121001)

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

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

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

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

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

1 GPU 數據庫分類與層次

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

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

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

? 第2 類是非內存型GDBMS,使用GPU 完成全部或者大部分數據庫關系運算,可以分析超過10TB 的數據量,包括SQream 和BlazingDB;

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

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

Fig.1 GDBMS landscape圖1 GDBMS 系統全景圖

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

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

Fig.2 Layered architecture of GDBMS[30]圖2 GDBMS 層次架構圖[30]

2 查詢編譯器

數據庫管理系統大都使用SQL 或其他高層邏輯API,而查詢編譯器作為將SQL 轉化為數據庫內部執行邏輯并向用戶返回結果的重要組件,處在GDBMS 的前端,與查詢處理器、查詢優化器、存儲管理器深度耦合協同工作,共同為用戶提供查詢服務.

傳統數據庫中,SQL 編譯器的詞法分析、大部分編譯技術同樣適用GDBMS,所不同的是,GDBMS 需要應對的異構計算硬件環境和數據處理模式變化的雙重挑戰.

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

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

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

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

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

由于GPU 由于編程模型和計算架構與CPU 不同,GDBMS 借鑒了CPU 計算中的向量化、“一次一算子”、批量執行這3 種策略,并使之適應GPU 大規模并發計算的特點,我們將在第3.2 節詳細介紹GDBMS 編譯器的數據處理模式.

2.1 GDBMS編譯模型

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

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

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

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

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

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

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

2.2 GPU數據處理模型

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

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

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

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

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

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

3 查詢處理器

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

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

3.1 GPU關系代數和并發原語

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

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

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

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

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

3.2 復雜關系算子

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

3.2.1 Join 算子

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

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

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

3.2.2 OLAP 聚集函數算子

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

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

3.3 空間數據查詢

隨著移動互聯網、物聯網、車聯網的發展,基于位置服務越來越普及,空間數據查詢變得越來越重要.為應對大規模空間數據處理的需求,大數據處理平臺開發出了一系列產品,比如 HadoopGIS,SpatialHadoop,SpatialSpark,GeoSpark,LocationSpark 等.綜述文獻[57]調研了基于Hadoop,Spark 系列的處理空間數據的產品,系統對比了其功能性、性能指標、實現方法等方面的優缺點.但基于Hadoop 系列的時空數據分析平臺采用批處理方式進行查詢,響應時間過長.而在傳統的數據領域,各DBMS 以GIS 插件形式提供了空間數據的處理,比如PostgreSQL 的PostGIS、Oracle 的Oracle Spatial、IBM 的DB2 Spatial Extender、Informix 的Spatial DataBlade等等.PG-Storm 等系統基于PostgreSQL,對Geo 地理數據,早在1988 年,研究人員就試圖將關系代數的成功經驗引入到地理位置信息系統GIS 中去[58].同樣,傳統數據庫的GIS 插件,在處理數據量、響應時間、查詢吞吐量上都差強人意.

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

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

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

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

3.4 KBE查詢執行引擎

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

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

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

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

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

3.5 GPU事務處理

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

3.6 小 結

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

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

4 查詢優化器

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

4.1 代價模型

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

4.1.1 GDBMS 代價模型之難

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

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

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

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

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

4.1.2 算子代價估計的方法

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

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

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

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

4.1.3 算子的選擇率估計

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

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

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

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

4.2 查詢重寫

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

4.2.1 join 算子改寫

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

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

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

4.2.2 減少copy 算子

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

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

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

4.3 異構計算任務隊列

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

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

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

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

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

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

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

現有研究表明:啟發式調度策略解決算子分配問題,WTAR 策略是最優的方案.但是在更大的范圍來看,GDBMS 算子分配問題是一個多目標的優化問題,啟發式調度算子策略無法解決關聯算子切換CU 過程中引起的數據傳輸代價,還需要進一步改進以擴大優化視野.

4.4 真實GDBMS系統中的優化器

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

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

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

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

HyPE 的3 個模塊內部工作流程如圖4 所示,對于查詢計劃中的每個算子O,在算法選擇器中選出其對應的CPUGPU 算法A,經由代價估計器,以測試數據集D和算子的參數P運行機器學習算法,估計對應算法的代價,最后由異構查詢優化器按照啟發式規則選擇最終的算法和執行計算核心,并將選擇結果反饋給系統作為后續代價估計的依據.

Fig.4 HyPE architecture[12]圖4 HyPE 架構圖[12]

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

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

4.5 小 結

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

5 存儲管理

數據庫管理系統的任務,本質上是在一定的存儲介質上讀寫數據.因此,存儲管理器成為其密不可分的關鍵模塊.傳統的DBMS 與GDBMS 在存儲管理器上存在以下不同.

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

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

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

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

5.1 GDBMS數據存儲體系

在數據存儲模型上,列式存儲在OLAP 業務中比行式存儲在性能上有明顯優勢[27,36],業已成為絕大多數GDBMS 的選擇.

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

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

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

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

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

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

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

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

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

5.2 GPU數據壓縮

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

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

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

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

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

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

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

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

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

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

5.3 GPU索引技術

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

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

Table 2 Research status of GPU index表2 GPU 索引研究現狀

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

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

5.4 小 結

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

6 總結

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

盡管如此,GPU 并不是專為關系型數據處理而開發,其硬件體系結構還有很多不適應GDBMS 發展的地方,未來需要在如下幾個方面進一步研究.

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

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

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

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

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