基于GPU的HPGB+-Tree索引*

劉 軍 冷芳玲 李宇軒

（1.東北大學(xué)信息化建設(shè)與網(wǎng)絡(luò)安全辦公室 沈陽(yáng) 110819）（2.東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110819）

1 引言

具有強(qiáng)大算力的圖形處理器GPU近些年的發(fā)展十分迅猛，GPU從其自身的架構(gòu)出發(fā)，不斷進(jìn)行迭代更新以達(dá)到提升性能的目的。在GPU架構(gòu)不斷演進(jìn)的過(guò)程中，NVIDIA公司所發(fā)布的每一代GPU新架構(gòu)都會(huì)添加新特性，例如高傳輸效率的零拷貝技術(shù)等。這些特性使得運(yùn)行在GPU上的程序更加易用，內(nèi)部協(xié)同處理更加高效。在GPU推出伊始，編寫(xiě)GPU程序需要紋理編碼等專(zhuān)業(yè)圖形處理領(lǐng)域的專(zhuān)業(yè)知識(shí)，因此編碼難度較高。但如今隨著Nvidia公司推出CUDA［1］通用并行計(jì)算架構(gòu)，圖形卡上的編程難度逐漸降低，相關(guān)技術(shù)逐漸成熟，GPU被廣泛應(yīng)用于人工智能、深度學(xué)習(xí)、高性能計(jì)算、大數(shù)據(jù)處理等通用計(jì)算領(lǐng)域。近年來(lái)，在基于異構(gòu)體系平臺(tái)的數(shù)據(jù)庫(kù)存儲(chǔ)與管理方向的研究越來(lái)越受各界關(guān)注，已有不少成果應(yīng)用于實(shí)際生產(chǎn)環(huán)境當(dāng)中，例如Pgstorm憑借GPU強(qiáng)大的算力協(xié)同PostgreSQL數(shù)據(jù)庫(kù)加速任務(wù)的執(zhí)行，可以獲得性能上的巨大提升。目前，GPU編程技術(shù)在數(shù)據(jù)庫(kù)領(lǐng)域的應(yīng)用還在不斷探索階段，切合GPU特性研究并實(shí)現(xiàn)的內(nèi)存索引所取得的科研成果數(shù)量遠(yuǎn)遠(yuǎn)不及傳統(tǒng)磁盤(pán)索引或基于CPU的主存索引，因此研究基于GPU的索引結(jié)構(gòu)對(duì)加速數(shù)據(jù)查詢(xún)是十分必要的。充分考慮CPU的硬件特點(diǎn)，并結(jié)合GPU強(qiáng)大的并行能力共同執(zhí)行查詢(xún)?nèi)蝿?wù)，以達(dá)到高效處理任務(wù)，降低查詢(xún)延遲的目的。本文提出并實(shí)現(xiàn)的加速數(shù)據(jù)庫(kù)查詢(xún)的系統(tǒng)核心就是一種基于CPU與GPU協(xié)同處理的B+-Tree索引。

2 相關(guān)工作

索引是加速數(shù)據(jù)庫(kù)查詢(xún)的重要策略。針對(duì)索引的優(yōu)化是加速數(shù)據(jù)查詢(xún)速度最好的方式之一。構(gòu)建基于GPU的樹(shù)形索引是目前異構(gòu)環(huán)境下加速數(shù)據(jù)庫(kù)操作的主流方法之一。Rao等實(shí)現(xiàn)了基于局部性原理和緩存特性設(shè)計(jì)的樹(shù)形索引結(jié)構(gòu)CSS-Tree［2］和CSB+-Tree［3］。Fang［4］等將圖形顯卡的計(jì)算能力同索引結(jié)構(gòu)結(jié)合在一起，實(shí)現(xiàn)了基于GPU的CSS-Tree。T-Tree［5］是一種在節(jié)點(diǎn)內(nèi)包含多個(gè)鍵的平衡二叉樹(shù)結(jié)構(gòu)，用于將索引信息和數(shù)據(jù)記錄都駐留在主存中。Liu［6］等在GPU平臺(tái)上利用N個(gè)線(xiàn)程并行化構(gòu)建N個(gè)節(jié)點(diǎn)的方式來(lái)迅速構(gòu)建起T-Tree索引結(jié)構(gòu)。R-Tree［7］作為廣泛被使用的空間索引技術(shù)，應(yīng)用GPU來(lái)深入挖掘出其在大規(guī)模的空間數(shù)據(jù)下的查詢(xún)處理潛力。You［8］等所提出的R-Tree使用基于GPU的并行查詢(xún)處理技術(shù)，實(shí)現(xiàn)了較八核CPU并行實(shí)現(xiàn)方案的十倍提速。

Daga等［9］介紹了一種利用異構(gòu)計(jì)算平臺(tái)APU加速B+-Tree搜索的技術(shù)。Fix［10］等提出了一種在GPU中以線(xiàn)程塊為單位編織查詢(xún)?nèi)蝿?wù)的算法。針對(duì)將數(shù)據(jù)庫(kù)應(yīng)用移植到GPU上的問(wèn)題，Kaczmarski［11］等基于數(shù)據(jù)庫(kù)中的B+-Tree索引結(jié)構(gòu)和數(shù)據(jù)頁(yè)的管理策略提出了一種用二維數(shù)組來(lái)表示B+-Tree的索引結(jié)構(gòu)。Kaczmarski［12］等相繼又提出了可以高效創(chuàng)建GPU上的B+-Tree索引算法。Huang［13］等介紹了一種在GPU上的批處理構(gòu)建和插入算法CUBPT。隨著并發(fā)查詢(xún)量和數(shù)據(jù)規(guī)模的增加，Yan［14］等提出了一種面向查詢(xún)吞吐量的新型B+-Tree索引Harmonia，可以激發(fā)GPU上低延遲的高速緩存的性能。Ashkiani［15］等提供了一種與B-Tree具有相同操作特性的動(dòng)態(tài)GPU日志結(jié)構(gòu)合并樹(shù)LSM，在GPU平臺(tái)上通過(guò)減少或消除線(xiàn)程訪(fǎng)問(wèn)節(jié)點(diǎn)時(shí)的競(jìng)爭(zhēng)實(shí)現(xiàn)了一種可變鍵值存儲(chǔ)［16］的B-Tree。綜合現(xiàn)有索引研究成果的優(yōu)缺點(diǎn)，更好地聯(lián)合使用CPU和GPU的內(nèi)存資源與并行計(jì)算能力，構(gòu)建面向查找密集型場(chǎng)景的B+-Tree索引，是本文所實(shí)現(xiàn)的基于GPU加速的數(shù)據(jù)庫(kù)查詢(xún)系統(tǒng)的研究重點(diǎn)。

3 面向GPU的HPGB+-Tree索引

由于CPU與GPU硬件構(gòu)造不同導(dǎo)致存在較大的差異性，基于CPU的B+-Tree索引結(jié)構(gòu)和查詢(xún)方式并不適用于GPU。例如，孩子節(jié)點(diǎn)的尋址采用二分法確定目標(biāo)鍵的定位方式等在GPU上均表現(xiàn)不佳。因此對(duì)B+-Tree索引結(jié)構(gòu)重構(gòu)使其適應(yīng)GPU的硬件特性是當(dāng)前研究的重點(diǎn)之一。隨著索引大小的增長(zhǎng)，CPU的性能受到內(nèi)存帶寬的限制［17］，而GPU的內(nèi)存架構(gòu)足夠高效，所以其內(nèi)存帶寬足夠高。但是GPU中可用的內(nèi)存空間與CPU可用的主機(jī)內(nèi)存相比十分有限。因此在數(shù)據(jù)量較大的情況下，B+-Tree索引在GPU上的擴(kuò)展能力會(huì)受到限制，所以如何結(jié)合CPU與GPU的內(nèi)存特性構(gòu)建基于GPU的B+-Tree索引結(jié)構(gòu)是值得研究的問(wèn)題。

本文所提出的HPGB+-Tree索引結(jié)構(gòu)是基于傳統(tǒng)的B+-Tree索引結(jié)構(gòu)進(jìn)行重構(gòu)和設(shè)計(jì)的。B+-Tree索引最早被提出用于磁盤(pán)索引［18］，核心結(jié)構(gòu)是平衡多路排序樹(shù)。B+-Tree只在葉子節(jié)點(diǎn)中存儲(chǔ)實(shí)際數(shù)據(jù)，內(nèi)部節(jié)點(diǎn)就有足夠的空間去容納更多的鍵值。B+-Tree不同于二叉樹(shù)，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的盤(pán)塊所容納的鍵值數(shù)量遠(yuǎn)超二叉樹(shù)，所以B+-Tree的高度就會(huì)遠(yuǎn)低于二叉樹(shù)，因此B+-Tree的搜索操作只需要很少的磁盤(pán)I/O次數(shù)就可以定位到含有目標(biāo)鍵的葉頁(yè)。無(wú)論是內(nèi)部節(jié)點(diǎn)還是葉子節(jié)點(diǎn)都通過(guò)二分搜索查找目標(biāo)鍵值。在B+-Tree的索引結(jié)構(gòu)中，含有m棵子樹(shù)的節(jié)點(diǎn)最多含有m個(gè)候選鍵。在葉子節(jié)點(diǎn)中存儲(chǔ)的候選鍵是有序的，并且葉子節(jié)點(diǎn)間通過(guò)指針鏈接。因此，B+-Tree很好地支持了高效的范圍查詢(xún)。B+-Tree另外一個(gè)特性是在執(zhí)行不同的查詢(xún)?nèi)蝿?wù)時(shí)，B+-Tree總會(huì)遍歷相同長(zhǎng)度的路徑，這就使查詢(xún)?nèi)蝿?wù)的負(fù)載較為均衡，查詢(xún)效率較為穩(wěn)定。目前B+-Tree索引已被廣泛應(yīng)用在數(shù)據(jù)庫(kù)當(dāng)中，如關(guān)系型數(shù)據(jù)庫(kù)MySQL等。如圖1所示，是一棵傳統(tǒng)的B+-Tree示意圖。

圖1 傳統(tǒng)B+-Tree

HPGB+-Tree的索引結(jié)構(gòu)是由傳統(tǒng)B+-Tree轉(zhuǎn)換而來(lái)，存在于主機(jī)端的傳統(tǒng)B+-Tree有三種重要的用途：1）用于計(jì)算HPGB+-Tree索引相關(guān)的元數(shù)據(jù)信息，如新索引在內(nèi)存中所需空間大小等。2）作為原始材料構(gòu)建HPGB+-Tree索引結(jié)構(gòu)并初始化索引數(shù)據(jù)。3）HPGB+-Tree索引是面向查詢(xún)密集型的索引結(jié)構(gòu)，因此數(shù)據(jù)插入采取從主機(jī)端的B+-Tree以批量、異步的方式進(jìn)行，再同步至GPU。

在對(duì)HPGB+-Tree索引樹(shù)的節(jié)點(diǎn)Knode進(jìn)行設(shè)計(jì)時(shí)，選擇用結(jié)構(gòu)體數(shù)組的方式組織關(guān)鍵字和分支信息，而不是用數(shù)組結(jié)構(gòu)體。這是因?yàn)椴⑿杏?jì)算架構(gòu)CUDA在操作細(xì)粒度數(shù)組如結(jié)構(gòu)體數(shù)組（SoA），即結(jié)構(gòu)體中的元素是數(shù)組時(shí)是很友好的。但是在操作粗粒度數(shù)組如數(shù)組結(jié)構(gòu)體（AoS），即數(shù)組中的元素是結(jié)構(gòu)體時(shí)，在性能測(cè)試中表現(xiàn)為訪(fǎng)存利用率較低。

結(jié)構(gòu)體在內(nèi)存中是一片連續(xù)的內(nèi)存空間，應(yīng)用SoA的方式可以帶來(lái)內(nèi)存讀寫(xiě)性能的巨大提升。對(duì)全局內(nèi)存帶寬的充分利用，是提高內(nèi)核函數(shù)效率和減少帶寬浪費(fèi)的重要手段。在樹(shù)的搜索過(guò)程中，每次會(huì)從內(nèi)存里讀取一個(gè)節(jié)點(diǎn)進(jìn)行判斷。由此可知，采用SoA的方式構(gòu)建樹(shù)的節(jié)點(diǎn)，可以更好地利用內(nèi)存資源，同時(shí)更方便實(shí)現(xiàn)對(duì)齊與合并訪(fǎng)問(wèn)內(nèi)存，將節(jié)點(diǎn)所在的內(nèi)存塊加載進(jìn)緩存中，優(yōu)化訪(fǎng)存速度。

索引樹(shù)的每個(gè)節(jié)點(diǎn)都是由結(jié)構(gòu)體數(shù)組Knode表示，如圖2所示。每個(gè)Knode包含三部分：候選鍵數(shù)組、子位置數(shù)組以及節(jié)點(diǎn)相關(guān)元信息。

圖2 HPGB+-Tree索引節(jié)點(diǎn)結(jié)構(gòu)

在候選鍵數(shù)組Keys中，連續(xù)存放著節(jié)點(diǎn)內(nèi)待比較的關(guān)鍵字，用于在查找目標(biāo)鍵時(shí)確定一條準(zhǔn)確的路徑。在子位置數(shù)組Indices中，存儲(chǔ)的是當(dāng)前節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)的地址。每一個(gè)元素相當(dāng)于傳統(tǒng)B+-Tree內(nèi)部節(jié)點(diǎn)的指針域中存放的其孩子節(jié)點(diǎn)的指針。節(jié)點(diǎn)相關(guān)元信息包括用于標(biāo)識(shí)節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)的標(biāo)記符isLeaf，用于標(biāo)識(shí)構(gòu)建進(jìn)度的標(biāo)記Location，以及用于標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)中候選鍵個(gè)數(shù)的標(biāo)記numsOfkey。這種節(jié)點(diǎn)設(shè)計(jì)的好處在于不僅可以高效率的訪(fǎng)存，還能夠迅速定位搜索路徑上孩子節(jié)點(diǎn)的位置加速查詢(xún)?nèi)蝿?wù)的執(zhí)行。

為使GPU的并行計(jì)算能力物盡其用，同時(shí)考慮到GPU上的內(nèi)存容量有限，而CPU上并沒(méi)有這方面的瓶頸。因此本文聯(lián)合使用主機(jī)內(nèi)存與設(shè)備內(nèi)存，將索引結(jié)構(gòu)分散在兩硬件平臺(tái)之中。具體來(lái)講，HPGB+-Tree索引整體分為兩部分，一部分存在于主機(jī)內(nèi)存中，包括索引樹(shù)Knodes以及實(shí)際數(shù)據(jù)Records。另一部分存在于GPU的設(shè)備內(nèi)存中，這部分是位于主存內(nèi)索引樹(shù)Knodes的拷貝鏡像，這是由于Records中的元素存儲(chǔ)的是實(shí)際數(shù)據(jù)，所占空間較索引樹(shù)Knodes要大得多，不僅占用顯存珍貴的內(nèi)存資源，而且向顯存的數(shù)據(jù)傳輸也十分耗時(shí)。在第一部分中，Knodes的類(lèi)型是以AoS方式組織而成的數(shù)組結(jié)構(gòu)體，Knodes將遍歷傳統(tǒng)B+-Tree節(jié)點(diǎn)轉(zhuǎn)換而來(lái)的結(jié)構(gòu)體Knode作為數(shù)組元素。Records是將每條實(shí)際數(shù)據(jù)Record作為數(shù)組元素，將數(shù)據(jù)記錄按順序存儲(chǔ)在內(nèi)存當(dāng)中，支持以O(shè)（1）的時(shí)間復(fù)雜度Records中獲取到記錄。值得一提的是，Record依據(jù)使用場(chǎng)景的不同，既可以是一個(gè)具體的值或一條數(shù)據(jù)記錄的主鍵，也可以是一條具有多個(gè)數(shù)值字段的記錄。

在第二部分中，存在于GPU上的索引樹(shù)是主存里Knodes的一個(gè)拷貝，也是憑借GPU高性能并行計(jì)算的優(yōu)勢(shì)來(lái)執(zhí)行查詢(xún)?nèi)蝿?wù)的主要操作對(duì)象，具體的拷貝過(guò)程是將Knodes從主機(jī)內(nèi)存?zhèn)鬏數(shù)皆O(shè)備內(nèi)存中開(kāi)辟的緩沖區(qū)內(nèi)。HPGB+-Tree索引會(huì)長(zhǎng)久地駐留在設(shè)備內(nèi)存中，被多個(gè)查詢(xún)?nèi)蝿?wù)共享。另外，在加載或構(gòu)建多個(gè)HPGB+-Tree索引時(shí)，多個(gè)緩沖區(qū)會(huì)在邏輯上組成索引池，而具體的信息維護(hù)工作由CPU負(fù)責(zé)。如圖3所示，是在異構(gòu)環(huán)境下HPGB+-Tree索引結(jié)構(gòu)的示意圖。在主存中的HPGB+-Tree索引構(gòu)建算法偽代碼如表1所示。

圖3 HPGB+-Tree索引結(jié)構(gòu)

表1 主機(jī)到設(shè)備數(shù)據(jù)傳輸測(cè)試實(shí)驗(yàn)結(jié)果

HPGB+-Tree索引構(gòu)建算法如下所示。

TRANSFORM_HPGB（root）

1）function TRANSFORM_HPGB（root）

2）Krecords←mallocCpuLeaves（）

3）Knodes←mallocCpuNodes（）

4）queue←enqueue（root）

5）while queue！=null do

6）curNode←dequeue（）

7）initKey（curNode）

8）if node！=leaf then

9） init_indice（curNode）

10） while index

11） next←curNode［index］

12） initIndice（next）

13） queue←enqueue（next）

14） end while

15）end if

16）if curNode==leaf then

17） while index

18） initRecord（curNode）

19） end while

20）end if

21）end while

22）end function

4 實(shí)驗(yàn)分析與性能測(cè)試

為了驗(yàn)證HPGB+-Tree索引為數(shù)據(jù)庫(kù)查詢(xún)系統(tǒng)帶來(lái)的查詢(xún)性能的提升，本節(jié)將對(duì)基于混合架構(gòu)的索引算法HPGB+-Tree進(jìn)行實(shí)驗(yàn)測(cè)試。為驗(yàn)證索引在混合架構(gòu)下相比于單一架構(gòu)的優(yōu)勢(shì)，本文選擇Aviram［19］提出的基于CPU的高查詢(xún)性能的無(wú)鎖B+-Tree索 引，F(xiàn)ix等 提 出 的GPU B+-Tree索 引Braided B+-Tree和前期研究成果即其優(yōu)化版本Optimized Braided B+-Tree來(lái)進(jìn)行索引性能的對(duì)比實(shí)驗(yàn)。本節(jié)將從實(shí)驗(yàn)環(huán)境，實(shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)方式以及實(shí)驗(yàn)結(jié)果與分析來(lái)組織內(nèi)容。主要對(duì)HPGB+-Tree索引算法進(jìn)行三個(gè)方面的實(shí)驗(yàn)測(cè)試：1）數(shù)據(jù)傳輸實(shí)驗(yàn)測(cè)試。2）HPGB+-Tree索引的相關(guān)參數(shù)實(shí)驗(yàn)測(cè)試。3）基于最佳參數(shù)配置的HPGB+-Tree索引等值查詢(xún)與范圍查詢(xún)的性能表現(xiàn)實(shí)驗(yàn)測(cè)試。

4.1 實(shí)驗(yàn)環(huán)境

硬件配置：顯卡GPU為NVIDIA 1660Ti，處理器為CPUIntel i7 9700，內(nèi)存16GB，磁盤(pán)512GB SSD；軟件配置：操作系統(tǒng)為Ubuntu 18.04，CUDA運(yùn)行環(huán)境為CUDA 9.0，開(kāi)發(fā)IDE為Vscode，CUDA代碼編譯器為NVCC，C編譯器為gcc 4.8，C++編譯器為g++4.8，構(gòu)建工具為Make。

4.2 實(shí)驗(yàn)數(shù)據(jù)和方式

本文進(jìn)行的實(shí)驗(yàn)采用的數(shù)據(jù)是隨機(jī)生成的數(shù)據(jù)記錄，記錄形式為一張?jiān)陉P(guān)系型數(shù)據(jù)庫(kù)中具有多個(gè)字段的行記錄組成的一張二維表。生成的數(shù)據(jù)記錄中的每個(gè)字段均為四字節(jié)的整型數(shù)值，該二維表內(nèi)數(shù)據(jù)記錄的行數(shù)范圍為十萬(wàn)量級(jí)到千萬(wàn)量級(jí)。

本文選擇任務(wù)的執(zhí)行時(shí)間作為評(píng)價(jià)指標(biāo)來(lái)衡量本系統(tǒng)內(nèi)部實(shí)現(xiàn)的HPGB+-Tree索引核心算法的性能。

在CUDA架構(gòu)中，主機(jī)端的內(nèi)存分為可分頁(yè)內(nèi)存與鎖頁(yè)內(nèi)存，如表1和表2所示，是由長(zhǎng)度為4字節(jié)的整型組成不同規(guī)模數(shù)據(jù)量，使用兩種不同類(lèi)型內(nèi)存進(jìn)行主存與設(shè)備內(nèi)存之間的數(shù)據(jù)傳輸測(cè)試。

表2 設(shè)備到主機(jī)數(shù)據(jù)傳輸測(cè)試實(shí)驗(yàn)結(jié)果

本部分測(cè)試不同的HPGB+-Tree索引階數(shù)對(duì)執(zhí)行查詢(xún)?nèi)蝿?wù)速度的影響，確定最大化查詢(xún)執(zhí)行效率的最佳索引階數(shù)。分別在不同數(shù)據(jù)規(guī)模下構(gòu)建32階、128階和512階的HPGB+-Tree索引，然后在系統(tǒng)默認(rèn)配置五個(gè)CUDA流的條件下，批量執(zhí)行十萬(wàn)個(gè)等值查詢(xún)?nèi)蝿?wù)。實(shí)驗(yàn)結(jié)果如圖4所示。在索引階數(shù)為32時(shí)，執(zhí)行時(shí)間消耗最小，達(dá)到執(zhí)行查詢(xún)?nèi)蝿?wù)的最佳性能。

圖4 不同索引階數(shù)的查詢(xún)效率

本文所提出的HPGB+-Tree索引繼承了B+-Tree索引的優(yōu)勢(shì)，葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)記錄是有序的，并且連續(xù)存儲(chǔ)在一塊內(nèi)存區(qū)域中。因此，HPGB+-Tree索引既支持等值查詢(xún)，又支持范圍查詢(xún)。本文選用傳統(tǒng)B+-Tree、基于GPU的Braided B+-Tree和Braided B+-Tree的優(yōu)化版本Optimized Braided B+-Tree作為實(shí)驗(yàn)對(duì)比對(duì)象，進(jìn)行等值查詢(xún)與范圍查詢(xún)的實(shí)驗(yàn)測(cè)試。

等值查詢(xún)的實(shí)驗(yàn)是在索引階數(shù)為32和等值查詢(xún)?nèi)蝿?wù)規(guī)模為一萬(wàn)的實(shí)驗(yàn)條件下，對(duì)在216~224不同規(guī)模的數(shù)據(jù)下構(gòu)建的四種索引，進(jìn)行等值查詢(xún)的對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 不同數(shù)據(jù)規(guī)模下的等值查詢(xún)

由于傳統(tǒng)坐標(biāo)系無(wú)法清晰表現(xiàn)出幾種索引的性能差距，因此繪制為同x雙y坐標(biāo)系的柱狀圖。其中傳統(tǒng)B+-Tree與Braided B+-Tree索引執(zhí)行等值查詢(xún)?nèi)蝿?wù)時(shí)間消耗較多，所以使用左側(cè)跨度較大的坐標(biāo)系，而Optimized Braided B+-Tree與HPGB+-Tree索引執(zhí)行等值查詢(xún)?nèi)蝿?wù)時(shí)間消耗較少，因此使用右側(cè)跨度較小的坐標(biāo)系。其中隨著索引數(shù)據(jù)規(guī)模的增大，CPU的執(zhí)行時(shí)間消耗也逐漸變大，并且執(zhí)行效率遠(yuǎn)遠(yuǎn)低于借助高性能硬件平臺(tái)GPU的其他索引結(jié)構(gòu)。Braided B+-Tree每次執(zhí)行任務(wù)都要將索引文件重新傳遞到設(shè)備內(nèi)存的臨時(shí)緩沖區(qū)中，因此隨數(shù)據(jù)規(guī)模增大，索引文件所占內(nèi)存也增大，由此造成的數(shù)據(jù)傳輸時(shí)延會(huì)導(dǎo)致執(zhí)行效率與內(nèi)核占用率不斷降低。在執(zhí)行等值查詢(xún)?nèi)蝿?wù)時(shí)，本文提出的HPGB+-Tree索引算法比Optimized Braided B+-Tree執(zhí)行效率高近三倍。

范圍查詢(xún)實(shí)驗(yàn)是在216~224的數(shù)據(jù)規(guī)模下分別構(gòu)建階數(shù)為32的四種索引，并進(jìn)行一萬(wàn)次隨機(jī)選取區(qū)間范圍為一百的范圍查詢(xún)測(cè)試，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同數(shù)據(jù)規(guī)模下的范圍查詢(xún)

為了更好表現(xiàn)出幾種索引進(jìn)行范圍查詢(xún)的實(shí)驗(yàn)效果，坐標(biāo)系構(gòu)造方式與圖3中等值查詢(xún)實(shí)驗(yàn)所繪制的同x雙y坐標(biāo)系構(gòu)造相同。其中x軸代表各個(gè)不同的數(shù)據(jù)規(guī)模，左側(cè)跨度較大的y軸用于標(biāo)記傳統(tǒng)B+-Tree與Braided B+-Tree索引處理范圍查詢(xún)?nèi)蝿?wù)的執(zhí)行時(shí)間，右側(cè)跨度較小的y軸用于標(biāo)記Optimized Braided B+-Tree與HPGB+-Tree索 引 處理范圍查詢(xún)?nèi)蝿?wù)的執(zhí)行時(shí)間。

范圍查詢(xún)的執(zhí)行邏輯與等值查詢(xún)?nèi)蝿?wù)類(lèi)似，但是范圍查詢(xún)?nèi)蝿?wù)需要掃描篩選出符合條件的左右邊界內(nèi)所有的目標(biāo)值，導(dǎo)致CPU執(zhí)行任務(wù)的消耗時(shí)間更加長(zhǎng)，查詢(xún)效率更加低。Braided B+-Tree索引在執(zhí)行范圍查詢(xún)?nèi)蝿?wù)時(shí)仍需要重新傳輸索引結(jié)構(gòu)與數(shù)據(jù)。在數(shù)據(jù)量較小時(shí)，由于PCIe傳輸?shù)母邘拰?duì)其造成的影響不大。但隨數(shù)據(jù)量級(jí)的增大，其影響越來(lái)越明顯，表現(xiàn)為任務(wù)的執(zhí)行時(shí)間逐漸接近CPU。Optimized Braided B+-Tree索引在執(zhí)行范圍查詢(xún)?nèi)蝿?wù)時(shí)避免傳輸索引結(jié)構(gòu)和數(shù)據(jù)的代價(jià)，同時(shí)優(yōu)化了內(nèi)核程序，使其可以較為高效地獲取符合條件的目標(biāo)鍵范圍。因此執(zhí)行時(shí)間較短，查詢(xún)效率較高。

本文提出的基于HPGB+-Tree索引范圍查詢(xún)算法在數(shù)據(jù)傳輸、任務(wù)分配和內(nèi)核程序等方面都進(jìn)行了優(yōu)化，相比于Optimized Braided B+-Tree索引，其執(zhí)行效率提升近三倍。

5 結(jié)語(yǔ)

目前GPU應(yīng)用于在數(shù)據(jù)庫(kù)領(lǐng)域的研究還處于不斷探索的階段，而索引作為加速數(shù)據(jù)庫(kù)檢索數(shù)據(jù)的重要技術(shù)手段，現(xiàn)有的研究大多數(shù)為磁盤(pán)索引或主存索引且已非常成熟，因此對(duì)利用新硬件平臺(tái)GPU突破索引性能瓶頸的研究具有重要的意義。

本文提出了一種CPU與GPU協(xié)同構(gòu)建和處理的HPGB+-Tree索引算法，該算法實(shí)現(xiàn)索引結(jié)構(gòu)的并行化設(shè)計(jì)，使其更加切合GPU的硬件特性。同時(shí)將實(shí)際數(shù)據(jù)記錄存儲(chǔ)于容量較大的主存中，索引樹(shù)的節(jié)點(diǎn)拷貝到帶寬較高的顯存中，解決了CPU內(nèi)存帶寬瓶頸和GPU內(nèi)存容量受限的問(wèn)題。在未來(lái)的工作中，我們將會(huì)研究如何將以HPGB+-Tree索引技術(shù)為核心，開(kāi)發(fā)MySQL的擴(kuò)展模塊。