文章目錄

• 一、背景
• 二、GPU 數(shù)據(jù)庫分類與層次
• • 1.商用型C-GDBMS 中分為3類
  • 2.研究型R-GDBMS
• 三、查詢編譯器
• • 1.GDBMS編譯模型
  • 2.GPU數(shù)據(jù)處理模型
• 四、查詢處理器
• • 1.GPU關(guān)系代數(shù)和并發(fā)原語
  • 2.復(fù)雜關(guān)系算子
  • 3.空間數(shù)據(jù)查詢
  • 4.KBE查詢執(zhí)行引擎
  • 5.GPU事務(wù)處理
• 五、查詢優(yōu)化器
• • 1.代價模型
  • • 1.GDBMS 代價模型之難
    • 2.算子代價估計的方法
    • 3.算子的選擇率估計
  • 2.查詢重寫
  • 3.異構(gòu)計算任務(wù)隊列
  • 4.真實GDBMS系統(tǒng)中的優(yōu)化器
• 六、存儲管理
• • 1.GDBMS數(shù)據(jù)存儲體系
  • 2.GPU數(shù)據(jù)壓縮
  • 3.GPU索引技術(shù)

一、背景

1.GPU性能極高

• GPU 與 CPU 具有不同的體系結(jié)構(gòu)和處理模式,將更多的片上空間用于計算單元,控制單元和緩存單元相對很少,使得單塊 GPU 上擁有數(shù)千個并發(fā)計算核心。因此,在同樣的主頻下,GPU 能夠取得更高的并發(fā)計算能力,也使 GPU 具有滿足大數(shù)據(jù)處理需求的巨大潛能。

• 在時空數(shù)據(jù) OLAP 分析任務(wù)和結(jié)果的可視化展示方面,幾十個 GPU 的 GPU 數(shù)據(jù)庫可以取得近千臺普通 CPU 服務(wù)的數(shù)據(jù)庫處理能力,而其響應(yīng)時間甚至更短。

2.GPU數(shù)據(jù)庫功能上日趨完善

• 基于商務(wù)智能 BI 的可視化交互式圖表查詢界面支持標(biāo)準(zhǔn) SQL 查詢語言，往往只要幾分鐘就可以完成以往數(shù)天乃至一周的工作。

• 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)準(zhǔn),使數(shù)據(jù)科學(xué)家可以停留在 GPU 上的同時探索數(shù)據(jù),訓(xùn)練機(jī)器學(xué)習(xí)算法并構(gòu)建人工智能應(yīng)用程序。

GPU數(shù)據(jù)庫領(lǐng)域的核心研究內(nèi)容：

• 查詢編譯器(query compilation)：將用戶的 SQL 語言描述的查詢需求轉(zhuǎn)化為 CPU- GPU 異構(gòu)計算環(huán)境下的查詢計劃;

• 查詢處理器(query processing)：應(yīng)用 GPU 并行計算技術(shù)實現(xiàn)關(guān)系型數(shù)據(jù)處理的各種算子,挖掘 GPU 峰值計算能力;

• 查詢優(yōu)化器(query optimizer)：用機(jī)器學(xué)習(xí)乃至人工智能技術(shù),結(jié)合 CPU-GPU 異構(gòu)計算環(huán)境和查詢計劃特點(diǎn)以及數(shù)據(jù)分布特征,生成最優(yōu)(次優(yōu))的異構(gòu)查詢計劃;

• 存儲管理器(memory management)：需要在異構(gòu)數(shù)據(jù)存儲管理、數(shù)據(jù)存儲格式、數(shù)據(jù)壓縮、數(shù)據(jù)訪問等問題上做出決策

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

GDBMS(GPU database management system or GPU accelerated database management system，使用 GPU 進(jìn)行或加速數(shù)據(jù)增刪改查的數(shù)據(jù)庫管理系統(tǒng))。

分為研究型R-GDBMS: for research和商用型C-GDBMS: for commercial

1.商用型C-GDBMS 中分為3類

• 第 1 類是支持 GPU 計算的傳統(tǒng)數(shù)據(jù)庫.
  這類 GDBMS 在已有傳統(tǒng)數(shù)據(jù)庫基礎(chǔ)之上,將特定算子部署到GPU 上用以加速的查詢處理,包括以 PostgreSQL 為基礎(chǔ)的 PG-Storm 系統(tǒng)和 DB2 的擴(kuò)展模塊 DB2 BLU.

• 這類數(shù)據(jù)庫與現(xiàn)有數(shù)據(jù)庫集成度高、周邊工具完善、且具有一定的與 OLTP 系統(tǒng)集成的能力;

第 2 類是非內(nèi)存型 GDBMS,

• 使用 GPU 完成全部或者大部分?jǐn)?shù)據(jù)庫關(guān)系運(yù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

以一臺普通服務(wù)器配備多個 GPU 顯卡就能取得分布式大數(shù)據(jù)系統(tǒng)一個集群的處理能力.超大吞吐量、超低時延以及更低的成本,讓 GDBMS 在 OLAP 業(yè)務(wù)上優(yōu)勢明顯

2.研究型R-GDBMS

研究原型 GDBMS 將重點(diǎn)放在了全 GPU 計算上，DB的數(shù)據(jù)數(shù)據(jù)可以在 GPU 顯存上存儲的情況下,GPU 加速所能獲得的最高性能.根據(jù)支持顯卡廠商,可分為專用 GDBMS （因為使用 CUDA 而只能在
Nvidia 顯卡上運(yùn)行）和通用 GDBMS（后者使用 OpenCL,在 Nvidia 卡和 AMD 卡上都可以運(yùn)行）。

三、查詢編譯器

? 首先,查詢編譯器需要利用 CUDA\OpenCL 編譯工具生成 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é)合起來
（1）向量化，原指將多個關(guān)系型數(shù)據(jù)以向量形式作為一個 SIMD(single instruction multiple data)指令的多個操作數(shù)來處理的方法,可以有效提高查詢處理吞吐量.
（2）在 GPU 中,向量化思想可以用 GPU的單指令多線程(single instruction multiple thread,簡稱 SIMT)進(jìn)一步加大數(shù)據(jù)處理的吞吐量;
（3）“一次一算子”與“一次一數(shù)據(jù)”是數(shù)據(jù)處理的兩種模式:
前者就是先將所有數(shù)據(jù)同時完成第 1 個算子的處理,并保存中間結(jié)果,作為下一個算子的輸入數(shù)據(jù),直至全部處理完;
而后者是指先讓一條數(shù)據(jù)經(jīng)過所有算子計算得出結(jié)果,再計算下一條數(shù)據(jù)的策略,是基于 CPU 計算常采用的策略;
（4）批量執(zhí)行就是盡可能一批處理更多的數(shù)據(jù),通過提高單次處理數(shù)據(jù)的數(shù)量,彌補(bǔ)處理頻次不高的缺點(diǎn);

GDBMS 借鑒了 CPU 計算中的向量化、 “一次一算子”、批量執(zhí)行這 3 種策略,并使之適應(yīng) GPU 大規(guī)模并發(fā)計算的特點(diǎn)

1.GDBMS編譯模型

DBMS 大多采用解釋型的 SQL 前端

• 通過語法解析、語義解析模塊將查詢query解析為，可為查詢執(zhí)行引擎使用的內(nèi)部任務(wù)表示，即邏輯執(zhí)行樹

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

• 基于底層虛擬機(jī)(LLVM)編譯器框架來即時編譯 SQL 代碼（預(yù)編譯并發(fā)原語），是目前 GDBMS 系統(tǒng)編譯器實現(xiàn)的主流方法。
  （1）該方法使用基于 LLVM[32]的 nvcc 編譯器，將關(guān)系算子分為更小的原語 primitives，并把原語預(yù)編譯為架構(gòu)無關(guān)匯編代碼 PTX，在運(yùn)行時，由編譯器只需完成 SQL 語言到算子的編譯工作；
  （2）查詢執(zhí)行器在優(yōu)化器指導(dǎo)之下完成算子到并發(fā)原語的映射。
• 虛擬機(jī)模式
  優(yōu)點(diǎn)：將 SQL 編譯為操作碼(opcode)作為中間表示,將整個 DB 系統(tǒng)視為一個虛擬機(jī),Opcode 操作碼對應(yīng)的算子被預(yù)編譯為cudabin 可執(zhí)行代碼,直接發(fā)送到 GPU 端執(zhí)行（CUDA 編譯器由google提出）。
  缺點(diǎn)：虛擬機(jī)模式放棄了SQL 優(yōu)化的機(jī)會,無法提供查詢重寫、基于代價的優(yōu)化;
• 適配器模式
  GPUDB 編譯器直接使用代碼生成模塊,將 SQL 直接編譯為 CUDA 或 OpenCL 驅(qū)動能執(zhí)行的代碼，以算子為單位進(jìn)行即時編譯，適配器模式在運(yùn)行時的編譯負(fù)載會比較高。

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

,從數(shù)據(jù)處理模型來看,可分為 3 種:

• 迭代模式(iteration)
  改進(jìn)版的火山模型，如增加每次迭代的數(shù)據(jù)量、使用 SIMD 指令一次處理多個數(shù)據(jù)、推拉結(jié)合的數(shù)據(jù)獲取方式等

• 批量模式(batching)
  將每個查詢編譯為可執(zhí)行代碼，采用完全物化的方式處理所有數(shù)據(jù)。
  但在實現(xiàn) ad-hoc 查詢上,面臨靈活度不夠、物化存儲空間要求過高的問題。

• 二者的混合
  比如微批量化查詢處理.該類方案使用不同的粒度作為數(shù)據(jù)處理的單元,仍然在邏輯上組織成樹型結(jié)構(gòu),讓數(shù)據(jù)自底向上流動完成查詢操作,兼具迭代模型的靈活性和批處理的高吞吐量的優(yōu)點(diǎn)

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

• 首先,迭代模式并不適合 GDBMS,因為火山模型賴以存在的虛函數(shù)機(jī)制因為 GPU 缺乏對應(yīng)的復(fù)雜邏輯控制模塊,在 GPU 上不可實現(xiàn)或者引起嚴(yán)重的線程分支惡化問題。
  GPU應(yīng)采取的操作是：
  將列數(shù)據(jù)細(xì)粒度分配給 GPU 線程,并用循環(huán)展開的方式,可有效減少控制指令總量,有效降低分支惡化的風(fēng)險

• 列式處理更適合 GDBMS
  一次一列來處理數(shù)據(jù)時,由于每列數(shù)據(jù)類型一致,可以用向量化方式處理,避免了分支判斷劣化性能問題；
  GDBMS 系統(tǒng)普遍采用列式處理模型[30],比如 Ocelot[13],CoGaDB[10]等

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

• 為了降低物化代價，通過適當(dāng)分區(qū)切分?jǐn)?shù)據(jù)，采用數(shù)據(jù)流水化處理(pipelining data processing),有效提高數(shù)據(jù)處理并行度

四、查詢處理器

GDBMS 查詢處理引擎，接受處理查詢編譯器輸出的查詢計劃樹 QEP(query execution plan)并執(zhí)行查詢返回結(jié)果。

GDBMS 查詢處理引擎面對的核心問題是：

• 功能上，如何利用 GPU 實現(xiàn)關(guān)系代數(shù)運(yùn)算,即實現(xiàn)選擇、投影、連接、聚合基本的關(guān)系算子,同時還需要實現(xiàn)的空間數(shù)據(jù)(geo-spatial data)處理、 OLAP 聚合查詢等功能復(fù)雜的算子
• 在執(zhí)行模式上，GPU 上執(zhí)行的代碼被稱為 kernel 核函數(shù)，以核函數(shù)為基礎(chǔ)的查詢處理技術(shù)(KBE)是GDBMS 查詢處理引擎的必然選擇
  （1）如何在 GPU 高并發(fā)SIMT 模式下以何種粒度切分關(guān)系查詢樹來最大化查詢處理性能，是 GDBMS 面臨的性能挑戰(zhàn)
  （2）GDBMS采用的策略：
  在邏輯查詢樹級別，用 KBE 融合或切分的策略，提升 GPU 的資源利用率和查詢并發(fā)度;
  在算子級別，則采用了設(shè)計專門針對 GPU 優(yōu)化的算子的方法，即數(shù)據(jù)并發(fā)原語的方法

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

在 GPU 上實現(xiàn)選擇、投影、連接等基本關(guān)系代數(shù)算子,是實現(xiàn) GDBMS 數(shù)據(jù)庫的基礎(chǔ)。

• .CUDA/OpenCL 賦予了程序員使用 C\C++代碼控制 GPU 大規(guī)模并行環(huán)境的能力,簡化了GDBMS 開發(fā)的難度,促進(jìn)了GDBMS 的繁榮。
• GDBMS使用分層設(shè)計，將關(guān)系代數(shù)功能拆解為算子層(operator)和原語層(primitives)兩部分，設(shè)計了一系列的適應(yīng) GPU 計算的數(shù)據(jù)并行原語(primitives)。
  如下所示是大部分的 GPU 并發(fā)原語
  
• eg：比如:scatter 原語[43]通過分區(qū)散射操作,在每個 load-store 周期內(nèi)處理一個分區(qū)的散射操作,增加了數(shù)據(jù)訪問聚合讀寫；
  很多算子映射成原語的單個或多個組合,能夠充分利用 GPU 高并發(fā)計算能力.通過以上原語的排列組合,大部分簡單的關(guān)系代數(shù)算子可以進(jìn)行有效拆解.比如選擇算子可以用 filter 原語實現(xiàn),同時,filter 原語是由 map 原語、 prefix sum 原語和 scatter 原語實現(xiàn)的。

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

Join 算子

• :GDBMS 在處理 Join 算子上比 CPU 方案效果好得多，這是由于 Join 算子是計算制約算子(compute-bounded)決定的
• 如何進(jìn)一步優(yōu)化GPU 上 Join 算子算法以及如何調(diào)整連接順序(join-order problem)，仍是GDBMS 領(lǐng)域收益最高的研究熱點(diǎn)之一

OLAP 聚集函數(shù)算子

• 聚集函數(shù)算子是又一個計算負(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ù)，提供給用戶

3.空間數(shù)據(jù)查詢

在空間索引方面，將歷史數(shù)據(jù)構(gòu)建駐留GPU 的空間索引，能夠處理大部分時空數(shù)據(jù)查詢，是未來發(fā)展方向之一。

4.KBE查詢執(zhí)行引擎

在查詢執(zhí)行引擎實現(xiàn)方式上，由于 GDBMS 普遍采用的 CUDA\OpenCL 以核函數(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ù)的層次上進(jìn)行合并融合或細(xì)致切分兩種策略:
  （1）針對數(shù)據(jù)量大或計算復(fù)雜的任務(wù),通過將多個核函數(shù)融合(kernel fusion)到一起,共同完成查詢處理;
  （2）而對于相對簡單的任務(wù),則進(jìn)一步切分核函數(shù)(mini-kernel),做到精細(xì)化管理,以合理利用 GPU 資源

核函數(shù)融合

• 優(yōu)點(diǎn)：核函數(shù)融合技術(shù)通過增加 GPU 函數(shù)處理操作的數(shù)量來優(yōu)先使用 GPU 資源,使得同樣配置下更能發(fā)揮 GPU 高并發(fā)高速率的優(yōu)勢,同時減少核函數(shù)的數(shù)量,減低了系統(tǒng)調(diào)用和管理的開銷,非常適合 GPU 多計算少邏輯控制的硬件特性
• 缺點(diǎn)：核函數(shù)融合技術(shù)并不能增加單位數(shù)據(jù)的計算強(qiáng)度,不能從根本上提高加速比;其次,核函數(shù)融合技術(shù)增加了單個核函數(shù)處理所需要的資源,以降低 GPU 資源重復(fù)利用率為代價;
• 最后,核函數(shù)融合技術(shù)目前還不能有效地跟查詢優(yōu)化器結(jié)合起來,如何有效融入真實 GDBMS 系統(tǒng)中是個未解之題

核函數(shù)切分

• 核函數(shù)切分能夠以更精細(xì)的粒度管理 GPU 資源,使流水化成為可能,提高了資源利用率的同時,降低了單個核函數(shù)的運(yùn)行周期,可以進(jìn)一步提高查詢并發(fā)度。
• 但是核函數(shù)切分是以更頻繁的核函數(shù)調(diào)度為代價的,數(shù)據(jù)換入換出頻率更高,受 PCIe 總線瓶頸影響更大,如果控制不當(dāng),很可能降低系統(tǒng)整體性能

小結(jié)

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

5.GPU事務(wù)處理

如何在 GPU 上實現(xiàn)數(shù)據(jù)庫事務(wù)的并發(fā)執(zhí)行還是一個開放問題,需要在 GPU 并發(fā)控制算法、 GPU 數(shù)據(jù)高效獲取、日志和故障恢復(fù)機(jī)制、 GPU 高效鎖實現(xiàn)機(jī)制、樂觀并發(fā)控制策略等方面進(jìn)一步研究。

五、查詢優(yōu)化器

首先,如何建立 GDBMS 查詢處理的代價模型

• 是查詢優(yōu)化的核心問題;其次,在代價模型指導(dǎo)下,構(gòu)建適應(yīng) GPU 查詢處理的啟發(fā)式規(guī)則體系對查詢樹進(jìn)行等價改寫,是 GDBMS 優(yōu)化器的重要問題；

再次,GDBMS 查詢優(yōu)化問題在一定程度上可以抽象為算子在何種類型的計算核心(CPU or GPU)上進(jìn)行處理的問題

• 即算子分配問題,解決了算子分配問題,就能最大程度地發(fā)揮GDBMS 整體性能優(yōu)勢;

最后,如何在真實系統(tǒng)中設(shè)計實時高效的查詢優(yōu)化器，與數(shù)據(jù)庫系統(tǒng)的其他模塊協(xié)同工作，是制約 GDBMS 發(fā)展的關(guān)鍵問題

1.代價模型

代價是數(shù)據(jù)庫內(nèi)核對給定 SQL 任務(wù)執(zhí)行成本的估計,在傳統(tǒng)數(shù)據(jù)庫中包括 CPU 執(zhí)行代價和 IO 代價兩部分

• 是邏輯查詢計劃向物理查詢計劃轉(zhuǎn)化過程中選擇最優(yōu)物理執(zhí)行計劃的依據(jù)

下面介紹構(gòu)建 GDBMS 代價模型所面臨的挑戰(zhàn)以及兩種常用的采用代價估計方法

• 基于代碼分析的“白盒方法”
• 基于學(xué)習(xí)的“黑盒方法”，并簡要介紹算子選擇率的估計方法

1.GDBMS 代價模型之難

SQL 優(yōu)化過程可以分為邏輯優(yōu)化和物理優(yōu)化兩個階段:

• 在邏輯優(yōu)化階段
  優(yōu)化器根據(jù)關(guān)系代數(shù)等價定律、算子下推啟發(fā)式規(guī)則、子查詢重寫等規(guī)則對邏輯執(zhí)行計劃進(jìn)行改寫,以得到執(zhí)行代價更小的物理執(zhí)行計劃;
• 物理優(yōu)化階段
  需要為邏輯查詢計劃中的算子選擇特定的算法和數(shù)據(jù)訪問方法，并選擇其中代價最低的一條生成路徑作為最終的查詢計劃；

傳統(tǒng)磁盤為中心的數(shù)據(jù)庫查詢執(zhí)行代價估計

• 以磁盤 IO 和 CPU 計算的加權(quán)平均和作為最終的查詢執(zhí)行代價

分布式數(shù)據(jù)庫的代價估計

• 通信代價

內(nèi)存數(shù)據(jù)庫的代價估計

• 代價估計的重點(diǎn)是內(nèi)存訪問

造成 PCIe 總線數(shù)據(jù)傳輸開銷成為了 GDBMS 代價估計的重點(diǎn)和難點(diǎn)的原因如下：

• 在 GDBMS 中,必須根據(jù) tuple 計算的位置(在 CUP 中還是在 GPU 中)來分別計算其代價.在 GPU 中,計算的代價由于其速率更高所以必須乘以一個經(jīng)驗系數(shù)(比如 0.1);
• GDBMS 中存儲層次體系更加復(fù)雜——既包括傳統(tǒng)的緩存-內(nèi)存-硬盤三級存儲管理,又包括主機(jī)內(nèi)存與 GPU 設(shè)備內(nèi)存的異構(gòu)存儲體系管理,這決定了 GDBMS 必須設(shè)計獨(dú)有的、能夠充分反映 GDBMS 存儲特性的訪存代價估計函數(shù)。
• GDBMS 的性能瓶頸在于主機(jī)內(nèi)存與 GPU 顯存之間的數(shù)據(jù)拷貝，可以類比于分布式數(shù)據(jù)庫中的網(wǎng)絡(luò)通信開銷,這也是在代價估計中必須考慮的最重要的因素.
• 其次，在多 GPU 環(huán)境的系統(tǒng)中，由于多 GPU 往往共享 PCIe 總線，因此多 GPU 下性能并不呈現(xiàn)簡單的線性增長，而且與之相關(guān)的管理成本和決策空間也相應(yīng)變大。

2.算子代價估計的方法

基于代碼分析的方法認(rèn)為,查詢的執(zhí)行取決于生成指令的代碼，因此可以通過靜態(tài)的代碼分析方法將 GPU 上執(zhí)行的關(guān)系代數(shù)算子的執(zhí)行代價精確估計,包括傳輸代價、計算代價、傳回代價及內(nèi)存訪問代價。

• 這種方法依賴于對每個算子的精確估計
• 缺點(diǎn)：
  由于采用了靜態(tài)的“白盒”分析的方法,只能針對算子級別進(jìn)行分析,沒有考慮多查詢并發(fā)情況下算子之間的相互影響以及系統(tǒng)運(yùn)行時
  的負(fù)載情況，不可避免地將在運(yùn)行時發(fā)生錯誤；
  而且隨著系統(tǒng)的進(jìn)化,任何代碼上的微小改動都將對代價估計產(chǎn)生影響，對代價估計模塊的維護(hù)成本也隨之增高，在擴(kuò)展性和可維護(hù)性上面臨巨大挑戰(zhàn)

基于學(xué)習(xí)的方法將算子視作黑盒通過機(jī)器學(xué)習(xí)的方法,經(jīng)過觀測算子的過往行為,估計該算子的執(zhí)行代價，并在運(yùn)行時利用反饋機(jī)制修正算子代價.

• 這種方法在一定程度上避免了靜態(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é)點(diǎn)分布式的應(yīng)用場景,低估了 PCIe 總線瓶頸的影響.

3.算子的選擇率估計

對于一個特定的關(guān)系算子來說,基數(shù)估計(cardinality estimation)就是對算子運(yùn)行前后數(shù)據(jù)的變化量評估的技術(shù)。

• 選擇率是指滿足算子條件的數(shù)據(jù)數(shù)量與數(shù)據(jù)總量之間的比值。
  算子選擇率的精確估計對中間結(jié)果大小估計、算子代價估計、最優(yōu) join 順序等都有重要影響，不但直接決定了優(yōu)化器的準(zhǔn)確性，甚至對 GPU 內(nèi)存管理產(chǎn)生直接影響
• 目前最好的解決方案是基于抽樣的柱狀圖方法，即等寬或等值地抽取數(shù)據(jù)，事先建立多區(qū)間的統(tǒng)計條形圖，查詢時，結(jié)合查詢條件及柱狀圖信息估計算子的選擇率

2.查詢重寫

查詢重寫是指優(yōu)化器對邏輯查詢樹等價變形，以達(dá)到提高查詢效率的目的。

• 目前的研究主要致力于改進(jìn) Join 算子的性能和合理消減 copy 算子來控制數(shù)據(jù) PCIe 總線傳輸總量上。

• join算子改寫
  文獻(xiàn)針對 SSBM 測試提出了 invisible join 技術(shù),對星型模式下的事實表與多個維表外鍵連接(star join)進(jìn)行優(yōu)化。
  該技術(shù)通過將 JOIN 重寫為事實表上的多個 Select 操作,并用布爾代數(shù)將多個選擇的結(jié)果合并,以減少后續(xù) JOIN 階段的整體數(shù)據(jù)量。

• 減少 copy 算子
  對于查詢優(yōu)化,可以通過查詢重寫技術(shù)減少 copy 算子的數(shù)量為目標(biāo),來減少在 PCIe 上來回反復(fù)傳輸?shù)臄?shù)據(jù)量，從而提升性能

• 表連接的順序是查詢性能優(yōu)化的關(guān)鍵.在現(xiàn)有的 GDBMS 中,各系統(tǒng)放棄了連接順序的優(yōu)化,采用確定性的查詢計劃構(gòu)建方法，目前,多表連接順序判定仍然是數(shù)據(jù)庫優(yōu)化領(lǐng)域開放問題之一,還沒有一個可以利用GPU 加速該問題求解的成熟方案

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

GDBMS 與傳統(tǒng) CPU 數(shù)據(jù)庫的不同之處在于,可以利用 CPU-GPU 異構(gòu)計算平臺并行處理數(shù)據(jù)

• 為保證多個計算設(shè)備(CPU 和 GPU)處于“繁忙”狀態(tài)，保證系統(tǒng)整體性能，給每個計算核心維護(hù)一個工作隊列，根據(jù)啟發(fā)式規(guī)則，將查詢計劃樹中相互獨(dú)立的算子分配給工作隊列并發(fā)執(zhí)行

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

HyPE 優(yōu)化器框架采用可移植分層設(shè)計,在很好地解決了查詢性能預(yù)測(query performance prediction)和算子分配問題

• 該系統(tǒng)采用基于學(xué)習(xí)的方法,由 3 個部分組成:代價估計器(cost estimator,簡稱 STEMOD)、算法選擇器(device-algorithm selector,簡稱 ALRIC)、異構(gòu)查詢優(yōu)化器(hybrid query optimizer,簡稱 HOPE）
  
  ? 首先,在 HyPE 中,假設(shè)算子跟其處理的數(shù)據(jù)是一個整體 OP(A,D)，OP 表示算子、 A 表示使用的算法、 D表示處理的數(shù)據(jù)。
  則物理執(zhí)行計劃可視為一個算子的流處理器；
  對于邏輯執(zhí)行樹進(jìn)行拓?fù)渑判騺硇蛄谢阕?#xff0c;消除算子間的數(shù)據(jù)依賴，保證每個算子執(zhí)行時其子算子均已執(zhí)行完畢；
  ? 其次,算子流中的算子依次經(jīng)過優(yōu)化器 HyPE 中,經(jīng)由代價估計器(cost estimator,簡稱 STEMOD)，算法選擇器(device-algorithm selector,簡稱 ALRIC)、異構(gòu)查詢優(yōu)化器(hybrid query optimizer,簡稱HOPE)[70]，為特定算子選擇合適的實現(xiàn)算法，并根據(jù)啟發(fā)規(guī)則為算子分配合適的處理器

HyPE 的 3 個模塊內(nèi)部工作流程如圖 4 所示

• 對于查詢計劃中的每個算子 O，在算法選擇器中選出其對應(yīng)的CPU\GPU 算法 A，經(jīng)由代價估計器，以測試數(shù)據(jù)集 D 和算子的參數(shù) P 運(yùn)行機(jī)器學(xué)習(xí)算法，估計對應(yīng)算法的代價，最后由異構(gòu)查詢優(yōu)化器按照啟發(fā)式規(guī)則選擇最終的算法和執(zhí)行計算核心，并將選擇結(jié)果反饋給系統(tǒng)作為后續(xù)
• 盡管 HyPE 優(yōu)化器基于機(jī)器學(xué)習(xí)的方法估計算子執(zhí)行代價，并組合多種啟發(fā)式規(guī)則選擇算子的物理實現(xiàn)算法，但是將查詢優(yōu)化問題等價為在運(yùn)行時處理算子分配問題的優(yōu)化策略對 GDBMS 來說未必是最有效的
  

PG-Storm，brytlyt/BrytlytDB基于開源數(shù)據(jù)庫 PostgreSQL，復(fù)用了 PostgreSQL 優(yōu)化器模塊。

• 通過計算 cost,在查詢執(zhí)行加護(hù)中插入適合的 GPU 算子(Join、 Scan、聚合等),將計算任務(wù)分配到 GPU 端加速,取得了較好的效果。
  這種編譯期靜態(tài)分配的任務(wù)分配策略，避免了 HyPE 優(yōu)化器在運(yùn)行時決策算子分配問題的負(fù)載，可以取得確定性的性能提升

六、存儲管理

傳統(tǒng)的 DBMS 與 GDBMS 在存儲管理器上存在以下不同.

• 第一，從功能上說,面向磁盤的數(shù)據(jù)庫主要包括內(nèi)存管理和外存管理兩部分;而對于 GDBMS 來說,還增加了 GPU 顯存管理的任務(wù).如何充分發(fā)揮異構(gòu)存儲體系的性能優(yōu)勢,是 GDBMS 數(shù)據(jù)管理最核心的問題;
• 第二，壓縮數(shù)據(jù)能夠有效減少需要處理的數(shù)據(jù)總量，進(jìn)而成比例增加 GDBMS 的性能。
  如何在 GPU 異構(gòu)顯存體系下盡可能獲得更大的壓縮比,充滿了挑戰(zhàn);
• 第三，索引能夠加速以硬盤為中心的數(shù)據(jù)查詢處理，但是在 GDBMS 大量物化的全量處理模型中是否還有存在的價值、如何發(fā)揮索引長處加速查詢處理，也是 GDBMS 存儲管理需要研究的重要問題.

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

GDBMS 普遍采用內(nèi)存駐留(memory-resident)的技術(shù),將數(shù)據(jù)盡可能放在內(nèi)存中(甚至放在 GPU 顯存上)來避免磁盤 IO 瓶頸。

列式存儲在 OLAP 業(yè)務(wù)中比行式存儲在性能上有明顯優(yōu)勢。

2.GPU數(shù)據(jù)壓縮

用輕量級壓縮算法 WAH 壓縮位圖索引以支持范圍查詢,數(shù)據(jù)首先以壓縮形式發(fā)送給 GPU,再在 GPU 上以 DecompressVector 技術(shù)解決 WAH 壓縮數(shù)據(jù)無法用 GPU 并行處理的問題,實現(xiàn)了在壓縮數(shù)據(jù)上直接進(jìn)行查詢,性能較 CPU 并行算法最高提升了 87.7 倍

3.GPU索引技術(shù)

傳統(tǒng)數(shù)據(jù)庫中,使用 B+樹等索引結(jié)構(gòu)減少訪問數(shù)據(jù)時磁盤讀寫的負(fù)載.在 GDBMS 中,由于索引結(jié)構(gòu)在訪存特性上的隨機(jī)性,不滿足 GPU 對齊合并訪問的特點(diǎn)，傳統(tǒng)的索引結(jié)構(gòu)照搬到 GPU 異構(gòu)計算環(huán)境下性能不高;

甚至由于 GDBMS 全內(nèi)存存儲和一次一算子全物化的查詢處理方式,不使用索引一樣可以達(dá)到很高的性能。

因此,在 GDBMS 中,如果使用全顯存存儲數(shù)據(jù),索引可能是多余的模塊;

但對于要直接從硬盤存取數(shù)據(jù)的 GDBMS,索引可在絕大多數(shù)情況下有效消除了磁盤 IO.

• 比如:PG-Storm 由于要從磁盤讀取數(shù)據(jù)，且無法改變 PostgreSQL 的存儲引擎，因此選擇用 BRIN-index 減少查詢需要傳輸?shù)?GPU 的數(shù)據(jù)量

總結(jié)

以上是生活随笔為你收集整理的《GPU 数据库核心技术综述》论文学习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。