如何使用PolarDB-X向量化引擎

這篇文章將為大家詳細(xì)講解有關(guān)如何使用PolarDB-X向量化引擎，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

介紹

PolarDB-X是阿里巴巴自研的云原生分布式數(shù)據(jù)庫(kù)，采用了計(jì)算-存儲(chǔ)分離的架構(gòu)，其中計(jì)算節(jié)點(diǎn)承擔(dān)著大量的表達(dá)式計(jì)算任務(wù)。這些表達(dá)式計(jì)算涉及到SQL執(zhí)行的各個(gè)環(huán)節(jié)，對(duì)性能有著重要的影響。為此PolarDB-X引入向量化執(zhí)行引擎，為表達(dá)式計(jì)算帶來(lái)了幾十倍的性能提升。

傳統(tǒng)數(shù)據(jù)庫(kù)執(zhí)行器的缺陷

現(xiàn)代數(shù)據(jù)庫(kù)系統(tǒng)的執(zhí)行引擎，大多采用一次計(jì)算一行數(shù)據(jù)（Tuple-at-a-time）的處理方式，并且需要在運(yùn)行時(shí)對(duì)數(shù)據(jù)類(lèi)型進(jìn)行解析和判斷，來(lái)適應(yīng)復(fù)雜的表達(dá)式結(jié)構(gòu)。我們稱(chēng)之為“標(biāo)量（scalar）表達(dá)式”。這種方式雖然易于實(shí)現(xiàn)、結(jié)構(gòu)清晰，但是當(dāng)需要處理的數(shù)據(jù)量增大時(shí)，它具有顯著的缺陷：

為了適應(yīng)復(fù)雜的表達(dá)式結(jié)構(gòu)，計(jì)算一條表達(dá)式往往需要引入大量的指令；對(duì)于行式執(zhí)行來(lái)說(shuō)，處理單條數(shù)據(jù)需要算子樹(shù)重新進(jìn)行指令解釋?zhuān)╥nstruction interpretation），從而帶來(lái)了大量的指令解釋開(kāi)銷(xiāo)。據(jù)論文《MonetDB/X100: Hyper-Pipelining Query Execution》統(tǒng)計(jì)，在MySQL執(zhí)行TPC-H測(cè)試集的 Query1 時(shí)，指令解釋就耗費(fèi)了90%的執(zhí)行時(shí)間。

此外，在最初的Volcano結(jié)構(gòu)設(shè)計(jì)中，算子內(nèi)部邏輯并沒(méi)有避免分支預(yù)測(cè)（branch prediction）。錯(cuò)誤的分支預(yù)測(cè)需要CPU終止當(dāng)前的流水線(xiàn)，將ELSE語(yǔ)句中的指令重新載入，我們將這一過(guò)程稱(chēng)為pipeline flush或pipeline break。頻繁的分支預(yù)測(cè)錯(cuò)誤會(huì)嚴(yán)重影響數(shù)據(jù)庫(kù)的執(zhí)行性能。

向量化執(zhí)行系統(tǒng)

數(shù)據(jù)庫(kù)向量化執(zhí)行系統(tǒng)最早由論文《MonetDB/X100: Hyper-Pipelining Query Execution》提出，它有以下幾個(gè)要點(diǎn)：

1. 采用vector-at-a-time的執(zhí)行模式，即以向量（vector）為數(shù)據(jù)組織單位。

2. 使用向量化原語(yǔ)（vectorization primitives）來(lái)作為向量化算子的基本單位，從而構(gòu)建整個(gè)向量化執(zhí)行系統(tǒng)。原語(yǔ)中避免產(chǎn)生分支預(yù)測(cè)。

3. 使用code generation（代碼生成）技術(shù)來(lái)解決靜態(tài)類(lèi)型帶來(lái)的code explosion（代碼爆炸）問(wèn)題。

向量化引擎為PolarDB-X的表達(dá)式計(jì)算帶來(lái)了顯著的性能提升。在下圖中，橫軸為向量大小，縱軸為吞吐量，不同標(biāo)量表達(dá)式和向量化表達(dá)式的性能測(cè)試對(duì)比結(jié)果如下：

case表達(dá)式性能測(cè)試對(duì)比結(jié)果如下：

整體流程

PolarDB-X中，向量化表達(dá)式的執(zhí)行分為以下幾個(gè)階段：

1. 用戶(hù)SQL經(jīng)解析后，在validator中進(jìn)行校驗(yàn)，推導(dǎo)和修正表達(dá)式的類(lèi)型信息；這一階段為向量化運(yùn)算提供正確的、靜態(tài)的類(lèi)型信息；

2. 在優(yōu)化器形成執(zhí)行計(jì)劃之后，需要對(duì)表達(dá)式樹(shù)進(jìn)行表達(dá)式綁定，實(shí)例化對(duì)應(yīng)的向量化原語(yǔ)，同時(shí)分配好向量下標(biāo)，供運(yùn)行時(shí)內(nèi)存分配；

3. 執(zhí)行階段，依據(jù)Volcano式的結(jié)構(gòu)，自頂向下的觸發(fā)執(zhí)行向量化原語(yǔ)，并將向量作為運(yùn)行時(shí)數(shù)據(jù)結(jié)構(gòu)。

運(yùn)行時(shí)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)

在PolarDB-X向量化執(zhí)行系統(tǒng)中，采用以下的數(shù)據(jù)結(jié)構(gòu)來(lái)存放數(shù)據(jù)：

向量化表達(dá)式執(zhí)行時(shí)，所有的數(shù)據(jù)都會(huì)存放在batch這一數(shù)據(jù)結(jié)構(gòu)中。batch由許多向量（vector）和一個(gè)selection數(shù)組而組成。其中，向量vector包括一個(gè)存儲(chǔ)特定類(lèi)型的數(shù)值列表（values）和一個(gè)標(biāo)識(shí)null值位置的null數(shù)組組成，它們?cè)趦?nèi)存中都是連續(xù)存儲(chǔ)的。null數(shù)組中的bit位以0和1來(lái)區(qū)分?jǐn)?shù)值列表中的某個(gè)位置是否為空值。

我們可以用vector(type, index)來(lái)標(biāo)識(shí)batch中一個(gè)向量。每個(gè)向量有其特定的下標(biāo)位置(index)，來(lái)表示向量在batch中的順序；類(lèi)型信息（type）來(lái)指定向量的類(lèi)型。在進(jìn)行向量化表達(dá)式求值之前，我們需要遍歷整個(gè)表達(dá)式樹(shù)，根據(jù)每個(gè)表達(dá)式的操作數(shù)和返回值來(lái)分配好下標(biāo)位置，最后根據(jù)下標(biāo)位置統(tǒng)一為向量分配內(nèi)存。

延遲物化

selection數(shù)組的設(shè)計(jì)體現(xiàn)了延遲物化的思想，參考論文《Materialization Strategies in a Column-Oriented DBMS》。所謂延遲物化，就是盡可能地將物化（matrialization）這一過(guò)程后推，減少內(nèi)存訪(fǎng)問(wèn)帶來(lái)的開(kāi)銷(xiāo)。在執(zhí)行表達(dá)式計(jì)算時(shí)，往往會(huì)先經(jīng)過(guò)Filter表達(dá)式過(guò)濾一部分?jǐn)?shù)據(jù)，再對(duì)過(guò)濾后的數(shù)據(jù)執(zhí)行求值處理；每次過(guò)濾都會(huì)影響到batch中所有的向量。以上圖中的batch為例，如果我們針對(duì)第0個(gè)向量設(shè)置 vector(int, 0) != 1這一過(guò)濾條件，假設(shè)vector(int, 0)中有90%的數(shù)據(jù)滿(mǎn)足該過(guò)濾條件（選擇率selectivity = 0.9），那么我們需要將batch中所有向量90%的數(shù)據(jù)重新物化到另一塊內(nèi)存中。而如果我們只記錄滿(mǎn)足該過(guò)濾條件的位置，存入selection數(shù)組，我們就可以避免這一物化過(guò)程。相應(yīng)的，以后每次向量化求值過(guò)程中，都需要參考此selection數(shù)組。

向量化原語(yǔ)

向量化原語(yǔ)是向量化執(zhí)行系統(tǒng)中的執(zhí)行單位，它最大程度限制了執(zhí)行期間的自由度。原語(yǔ)不用關(guān)注上下文信息，也不用在運(yùn)行時(shí)進(jìn)行類(lèi)型解析和函數(shù)調(diào)用，只需要關(guān)注傳入的向量即可。它是類(lèi)型特定（Type-Specific）的，即一類(lèi)原語(yǔ)只能處理特定類(lèi)型。

向量化原語(yǔ)的主體是Tight-Loop的代碼結(jié)構(gòu)。在一個(gè)循環(huán)體內(nèi)部，只需要進(jìn)行取值和運(yùn)算即可，沒(méi)有任何的分支運(yùn)算和函數(shù)調(diào)用。一個(gè)簡(jiǎn)單的向量化原語(yǔ)結(jié)構(gòu)如下所示：

map_plus_double_col_double_col(int n,double*__restrict__ res,double*__restrict__ vector1, double*__restrict__ vector2,int*__restrict__ selection)
{  if (selection) {for(int j=0;j<n; j++) {int i = selection[j];
            res[i] = vector1[i] + vector2[i];
        } 
  } else {for(int i=0;i<n; i++)
          res[i] = vector1[i] + vector2[i];
  }   
}

注：*左右滑動(dòng)閱覽

其運(yùn)算過(guò)程利用了selection數(shù)組，逐步對(duì)向量進(jìn)行取值、運(yùn)算和存值，如下圖所示：

向量化原語(yǔ)帶來(lái)了以下優(yōu)點(diǎn)：

1. Type-Specific以及Tight-Loop的結(jié)構(gòu)，大大減少了指令解釋的開(kāi)銷(xiāo)；

2. 避免分支預(yù)測(cè)失敗和虛函數(shù)調(diào)用對(duì)CPU流水線(xiàn)的干擾，同時(shí)也能有利于 loop pipeline 優(yōu)化【論文引用】

3. 從向量中存取數(shù)據(jù)，有利于觸發(fā)cache prefetch，減少cache miss帶來(lái)的開(kāi)銷(xiāo)。

我們?yōu)楦鞣N標(biāo)量化表達(dá)式提供相應(yīng)的原語(yǔ)實(shí)現(xiàn)，從而完成從標(biāo)量到向量化的轉(zhuǎn)變。例如將加法運(yùn)算 plus(Object, Object) 針對(duì)不同操作數(shù)類(lèi)型生成原語(yǔ)，包括plus(double，double)，plus(long, long)等。

短路求值

在向量化原語(yǔ)的基礎(chǔ)上，我們可以進(jìn)一步對(duì)分支運(yùn)算（也稱(chēng)為控制流運(yùn)算 Control-Flow）進(jìn)行短路求值（short-circuit calculation）優(yōu)化，提升表達(dá)式計(jì)算的性能。

例如，case 表達(dá)式由n個(gè)when表達(dá)式、n-1個(gè)then表達(dá)式、1個(gè)else表達(dá)式構(gòu)成。對(duì)于表達(dá)式

select case when a > 1 then a * 2 when b > 1 then b * 2else a * b

具有以下樹(shù)形結(jié)構(gòu)：

由于標(biāo)量化表達(dá)式按照volcano結(jié)構(gòu)編排，并提供了統(tǒng)一的next()的接口，case表達(dá)式必須執(zhí)行完所有的子表達(dá)式a>1，a*2，b>1，b*2和a*b之后，將全部結(jié)果匯總到一起，最后做case語(yǔ)義處理。這種執(zhí)行方式不能根據(jù)when表達(dá)式的處理結(jié)果及時(shí)終止計(jì)算過(guò)程，而是對(duì)全部子表達(dá)式無(wú)差別執(zhí)行。

引入向量化執(zhí)行器以后，我們可以設(shè)計(jì)短路求值來(lái)優(yōu)化此問(wèn)題，每一個(gè)子表達(dá)式需要被提供合適的selection數(shù)組，從而正確選擇列中合適的位置來(lái)進(jìn)行向量運(yùn)算。

關(guān)于如何使用PolarDB-X向量化引擎就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。