本文轉(zhuǎn)載自：Greenplum社區(qū)

首先我們先來了解一下什么是執(zhí)行器。簡單來講，執(zhí)行器是處理一個由執(zhí)行計劃節(jié)點組成的樹，并返回查詢結(jié)果。那么什么是執(zhí)行計劃節(jié)點呢？從本質(zhì)上講，一個執(zhí)行計劃節(jié)點，實際上就是一個數(shù)據(jù)處理節(jié)點。從下圖可看到，在數(shù)據(jù)輸入后，執(zhí)行節(jié)點會對數(shù)據(jù)進行數(shù)據(jù)處理，然后返回數(shù)據(jù)作為輸出。這些執(zhí)行節(jié)點會被組織成樹的形式。

?

下圖是一個SELECT查詢的執(zhí)行計劃樹。通過優(yōu)化器優(yōu)化后，就會生成這樣的樹狀結(jié)構(gòu)，我們可以看到里面有四個執(zhí)行節(jié)點，包括HashJoin節(jié)點，Hash節(jié)點，順序掃描節(jié)點，所有的節(jié)點通過樹的方式組織在一起，來表示各節(jié)點之間的數(shù)據(jù)流動或者順序關(guān)系。 每一個計劃節(jié)點包含足夠多的元數(shù)據(jù)信息提供給執(zhí)行器。

?

圖中的Seq Scan被稱為原發(fā)性的掃描節(jié)點，原發(fā)性的掃描節(jié)點是指，節(jié)點本身可以自己產(chǎn)生數(shù)據(jù)，而不依賴于其他節(jié)點；反之，非原發(fā)性掃描節(jié)點是需要子節(jié)點來為其提供數(shù)據(jù)，圖中的Hash Join和Hash就是非原發(fā)性掃描節(jié)點。了解了原發(fā)性掃描節(jié)點和非原發(fā)性掃描節(jié)點的不同，就可以更好的理解后面的執(zhí)行模型。

?

那么執(zhí)行器是怎么執(zhí)行生成的執(zhí)行計劃樹呢？就需要利用執(zhí)行模型了。面對這樣的執(zhí)行計劃樹時，處理方式其實很多，我們會根據(jù)包括每一個節(jié)點內(nèi)的數(shù)據(jù)輸入是怎么樣的規(guī)定，輸出有什么樣的特點等不同的信息，會選擇不同的執(zhí)行模型。

現(xiàn)在我們來介紹一下幾種常見的執(zhí)行模型。

執(zhí)行模型

第一種是迭代模型，也被稱為流式模型，或者是抽拉式模型。它的定義非常簡單，每一個執(zhí)行節(jié)點本質(zhì)上就是一個next函數(shù)，我們會從一個樹節(jié)點的根節(jié)點一直往下執(zhí)行這個next 函數(shù)。next 函數(shù)的實現(xiàn)會遵循這樣的特點：

• 從輸出角度看，next 函數(shù)的每一次調(diào)用，執(zhí)行節(jié)點返回一個tuple，沒有更多tuple的時候返回一個NULL。
• 從輸入的角度看，執(zhí)行節(jié)點實現(xiàn)一個循環(huán)，每次調(diào)用子執(zhí)行節(jié)點的next函數(shù)來獲取它們的輸出，并處理它們直到能返回一個tuple或者NULL。
• 執(zhí)行控制流方向是自上往下，不斷抽拉的方式，由上層節(jié)點直接驅(qū)動下層節(jié)點來進行數(shù)據(jù)的驅(qū)動。而從數(shù)據(jù)流的角度來看，還是由上層節(jié)點往下層節(jié)點傳輸來完成。

這種執(zhí)行模型的有點在于規(guī)則簡單，易懂，資源使用少，通用性好，大部分的執(zhí)行計劃節(jié)點一般都可以用這種模式來實現(xiàn)。缺點也很顯而易見，由于每次迭代只返回一個tuple，迭代次數(shù)多，代碼局部性較差，同時對CPU cacheline也不是很友好。

?

向量化模型

第二種模型就是向量化模型，和迭代模型有一些相似之處，比如每一個執(zhí)行節(jié)點實現(xiàn)一個next函數(shù)，但也有其不同之處。每一次迭代，執(zhí)行節(jié)點返回一組tuple而非一個tuple，從而減少迭代次數(shù)，可以利用新的硬件特性如SIMD來加快一組tuple的處理。同時一組tuple在不同的節(jié)點之間傳輸，對列存也更加友好。

執(zhí)行節(jié)點實現(xiàn)一個循環(huán)，每次調(diào)用子執(zhí)行節(jié)點的next函數(shù)來獲取它們的輸出，并能夠批量的處理數(shù)據(jù)。執(zhí)行控制流方向自上而下，采用pull的方式。

?

Push執(zhí)行模型

第三種模型是目前比較熱門的模型——PUSH執(zhí)行模型。每一個執(zhí)行節(jié)點定義兩個函數(shù)

• Produce函數(shù)

Produce函數(shù)：看起來像是一個執(zhí)行節(jié)點tuple的生產(chǎn)函數(shù)，其實不然，對于非自主生產(chǎn)的執(zhí)行節(jié)點，produce函數(shù)更像一個控制函數(shù)，它不做過多的生產(chǎn)的工作，想反它會立即調(diào)用子節(jié)點的produce函數(shù)。具有自主生產(chǎn)的執(zhí)行節(jié)點（一般為葉子節(jié)點），其produce函數(shù)名副其實的生產(chǎn)tuple，并驅(qū)動父節(jié)點的consume函數(shù)提取數(shù)據(jù)。

• Consume函數(shù)

Consume函數(shù)：被下層節(jié)點驅(qū)動調(diào)用，接收子節(jié)點數(shù)據(jù)，進行各種運算，并驅(qū)動其父節(jié)點的consume函數(shù)。

現(xiàn)在我們通過一個例子來看一下，下圖中有三個節(jié)點，一個掃描節(jié)點，一個投影節(jié)點，一個Join 節(jié)點。每個節(jié)點都生成了兩個函數(shù)，一個生產(chǎn)函數(shù)，一個消費函數(shù)。整個PUSH模型是怎么做的呢？圖中的紅框標(biāo)注的為原發(fā)性的掃描節(jié)點，藍框標(biāo)注的是非原發(fā)性的掃描節(jié)點。非原發(fā)性的掃描節(jié)點中的生產(chǎn)函數(shù)并不做真正的生產(chǎn)工作，而更多是承擔(dān)了控制工作，會調(diào)用它的子節(jié)點的生產(chǎn)函數(shù)。因此投影節(jié)點和Join節(jié)點會調(diào)用scan的生產(chǎn)函數(shù)。由于Scan是原發(fā)性的，因此會在生產(chǎn)并得到數(shù)據(jù)后，開始驅(qū)動數(shù)據(jù)的消耗。

?

PUSH模型是由下層的節(jié)點驅(qū)動上層的節(jié)點來完成的。數(shù)據(jù)流向也是自下而上的。下層驅(qū)動模型可以相對容易的轉(zhuǎn)換成由數(shù)據(jù)驅(qū)動的代碼。好處就是，上層的操作就會變成本節(jié)點的算子，增加代碼的局部性。此外，這樣的代碼可以更方便進一步轉(zhuǎn)換為一個純計算代碼，例如使用LLVM優(yōu)化等。個人認為這種模型通用性不強，只能做一些局部的優(yōu)化。

Greenplum使用的是迭代模型，但我們正在積極探索向量化模型和PUSH模型。Greenplum正在開發(fā)相應(yīng)的功能，并提交到PG社區(qū)，基本思路是利用custom scan 的可定制特性，實現(xiàn)向量化版本的AGG節(jié)點，SORT節(jié)點，并替換原有查詢執(zhí)行樹中的相應(yīng)節(jié)點。大家對這一塊感興趣也歡迎去相應(yīng)的郵件列表查看。

?

而Greenplum執(zhí)行器面臨了更大的挑戰(zhàn)，首先Greenplum是MPP架構(gòu)，意味著大規(guī)模的并行計算，每個執(zhí)行節(jié)點就需要更多的處理過程。同一個執(zhí)行節(jié)點就會變成多個處理過程，而數(shù)據(jù)也會被拆分。執(zhí)行節(jié)點之間進行輸入和輸出的過程中，需要不同的計算單元進行交換。

Greenplum執(zhí)行的挑戰(zhàn)和解決方案——Motion

?

此外，Greenplum是一個Shared-Nothing的架構(gòu)，這就意味著不同的計算單元之間的輸入輸出的過程會受阻。

?

面臨這樣的挑戰(zhàn)，Greenplum的解決方案是加了一個新的名為MOTION的執(zhí)行節(jié)點，用來在不同的執(zhí)行節(jié)點之間移動數(shù)據(jù)。

?

加了Motion后，執(zhí)行計劃仍然是樹狀結(jié)構(gòu)。只是在不同的節(jié)點之間加了個Motion節(jié)點，并最終通過Motion節(jié)點，將數(shù)據(jù)進行匯總。

?

接著我們來剖析一下并行化Plan。在下面的例子中，我們有一個Master和34個Segment節(jié)點。現(xiàn)在有兩張表：單身男和單身女，數(shù)據(jù)分布在不同的SEGMENT上。如果我們要進行一個查詢，將這兩張表格中，籍貫相同的單身男和單身女進行相親匹配，我們是如何生成一個可以被并行化執(zhí)行的計劃樹呢？

為了更好的說明這個問題，我們可以在現(xiàn)實生活中進行映射，來方便大家理解。如果在現(xiàn)實生活中，我們會怎么辦？如果這些不同戶籍的單身男女在同一個省，此時處理方法就相對簡單，

• 首先把單身女找出來
• 再把單身男找出來
• 再把同戶籍的男生女生分配到相同的會場

從而較為快速的把這些單身男女進行匹配和篩選。

如果這些單身男女并不在同一個省，而是分布在全國34個省中，此時要如何處理呢？

為了做一個最優(yōu)的策略，我們會分情況來看，

• 可以由各省獨自舉辦相親會
• 針對本省的單身男女組織相親
• 將結(jié)果返回總部

對應(yīng)到Greenplum上，是這樣的

?

2. 對于單身女居住在戶籍所在地，而單身男生分散在全國各地。此時采取的策略可以是，

• 各省的分部獨自舉辦相親會:
• 將每個省的單身男青年找出來，并將他們通過火車派送回原戶籍所在地。
• 由每個省接待這些男青年，并在本省找出女單身青年，對他們進行相親配對。

如果女生數(shù)量很少，此時可以采用的策略是

• 找到本省所有適齡單身女青年，并為其買好34個省份的車票，每個省份都去一趟。
• 每個省接待這些單身女青年，并安排其與生活在本省的男青年相親，找出戶籍一致的配對。

對應(yīng)到Greenplum上，是這樣的

?

3. 如果單身男女隨機分布在全國各地，此時有兩種策略

策略1：在總部舉辦相親會，各省把單身男女通過火車派送回總部，總部接待并安排相親配對。但由于總部資源有限，一般都不會采取這種策略；

策略2：

• 各分部舉辦相親會：
• 各省找出居住在本省的適齡單身男，并按戶籍派送到相應(yīng)的省。
• 各省找出居住在本省的適齡單身女，并按戶籍派送到相應(yīng)的省。
• 各省接待全國歸來的男女，進行相親配對。

對應(yīng)到Greenplum上，就是這樣的：

?

在進行相親策劃后，我們得出了以下經(jīng)驗總結(jié)：

• 人多力量大的原則，盡量利有各省的分部
• 要首先分析當(dāng)前男女青年的地域分布
• 必要時使用交通工具來打破地域的限制

其實在Greenplum里，也采用了類似的處理方式。每一張表都會有數(shù)據(jù)分布信息，Greenplum支持三種分布策略：鍵值分布（按列分布）、隨機分布、復(fù)制分布（數(shù)據(jù)在所有的segment上都保留了一份數(shù)據(jù)）。

Greenplum內(nèi)部采用更通用的Locus信息來表示分布信息，所有的數(shù)據(jù)集合都會有數(shù)據(jù)分布狀態(tài)的。

?

Greenplum通過Motion來打破物理上的隔離。包括下圖中的四種Motion。Redistribute Motion是通過鍵值把Tuple在多個節(jié)點間進行重分布。Gather/Gather Merge Motion是把不同Segment上的數(shù)據(jù)聚集到一個節(jié)點上，Gather Merge保證了一個有序的收集過程。Broadcase Motion顧名思義就是廣播，每個節(jié)點都發(fā)送一份。Explict Redistribute Motion常用于Update/Delete操作，該類操作需要在數(shù)據(jù)原來所在的節(jié)點上進行更新或刪除，保證數(shù)據(jù)分布不會出現(xiàn)不一致。gp segment id隱藏列保存了數(shù)據(jù)所在原來節(jié)點信息。

并行化Plan

?

Motion會引起數(shù)據(jù)的遷移，帶來執(zhí)行代價，所以Greenplum會對需不需要做Motion進行代價評估，評估依據(jù)主要是當(dāng)前數(shù)據(jù)集合的數(shù)據(jù)分布狀態(tài)和在當(dāng)前數(shù)據(jù)集合上將要執(zhí)行的操作。

?

現(xiàn)在我們通過一個分布式Join的例子來鞏固一下。下面是一個簡單的inner join。A、B都是按照Hash分布的鍵值表。也就是數(shù)據(jù)被分散在各個Segment上，而每個Segment上只有部分數(shù)據(jù)。要做到A inner join B的完整數(shù)據(jù)集，就需要把B表全部復(fù)制到所有的segment上，和A的部分數(shù)據(jù)Join。得到的Plan就如下圖所示。前面我們提到，在Join完成后，也會有個數(shù)據(jù)分布。本例中，在Join完成后，還是會通過Hash分布。接著，由于QD會直接和Client進行交互，因此需要把所有的數(shù)據(jù)Gather到QD上，再由QD發(fā)送給Client。而其中的優(yōu)化過程，會在本《深入淺出Greenplum內(nèi)核》系列直播后續(xù)的課程中細講，請大家關(guān)注。

?

如果A是一個鍵值表，B是一個復(fù)制表。前面的Broadcast就不需要做了，可以直接進行Join。每個并行處理單元處理下圖中的計劃樹，再Gather到QD即可。

?

如果A是鍵值表，而B是general的數(shù)據(jù)分布。B會在每個segment上都能產(chǎn)生1-10的數(shù)據(jù)，就能滿足Join的需求。

?

如果A不變，而B是一個子查詢，是SingleQE的數(shù)據(jù)分布，即在一個segment上提供這樣的數(shù)據(jù)。其中一種策略就是，把分布各個Segment上的A的數(shù)據(jù)都Gather到一個Segment上執(zhí)行。此時Join后的數(shù)據(jù)模型就會變成SingleQE的數(shù)據(jù)分布。

?

如果在Inner Join時加個條件，就可以將Broadcast Motion換成Redistribute Motion。讓c2這一列按照c1這個Hash重新分布到其他segment上，從而減少數(shù)據(jù)的移動。

?

我們再來看一個要AGG操作的例子，在下面的例子中，對A進行AGG操作，計算c1的count值。此時，我們只需要在每個Segment上做AGG，再Gather到QD即可。

?

如果A表是按照C2做分布的（非兩階段），則前面的策略便不可用了。此時，我們可以將A可以按照C1做Redistrbute Motion，在前面提到的操作即可。

?

Dispatcher

講完分布式Plan的產(chǎn)生，我們再來看一下Greenplum中為了支持分布式plan而設(shè)計的模塊。第一個就是Dispatcher。

上面提到的相親的策略，

• 各省的分部獨自舉辦相親會。
• 首先每個省的單身男青年找出來，并將他們通過火車派送回原戶籍所在地。
• 然后每個省接待這些男青年，并在本省找出女單身青年，對他們進行相親配對。

?

對應(yīng)到Greenplum上，有了分布式plan，一堆計算資源是如何分配調(diào)度和執(zhí)行起來的呢？

?

Dispatcher首先要做的就是分配QE資源。從plan的角度來看，會將計劃做成SliceTable，SliceTable中會告知Slice2從34個segment來分配資源，而Slice3只需要Segment2來提供資源即可。

?

Dispatcher從SliceTable中得到信息后，會去分配資源。它會向CdbComponentDatabases這個component來申請資源，并將得到的資源回寫到SliceTable中。原本，SliceTable中只包括了需要在哪幾個Segment上起QE資源的較模糊的指令，但在分配完后，每個SliceTable就會得到QE資源具體的節(jié)點信息，包括地址和端口等。

?

Dispatcher分配QE資源通過調(diào)用allocateGang()函數(shù)完成。GANG大小的分配非常靈活，最小可以只分配一個QE資源，而一般為segment的個數(shù)，甚至可以支持大于segment的個數(shù)的QE資源，即每個segment可以為一個gang分配多于一個的QE資源。此外QE資源閑置后，并不會被馬上回收，而是可以被后續(xù)的查詢重用，減少了重復(fù)分配QE帶來的開銷。

?

Dispatcher第二個功能是分發(fā)任務(wù)。CdbDispatchPlan可以分發(fā)并行性化plan的任務(wù)，SliceTable也會連同這個分布式plan一起發(fā)給QE。這樣的話所有的QE通過SliceTable可以找到自己預(yù)先被分配屬于哪個Gang，以及它的父節(jié)點的Gang是哪些以便于建立節(jié)點間通信。通過Parent Gang具體的QE描述符，我們就可以知道要把數(shù)據(jù)傳送到哪個端口。也可以分發(fā)純文本的、兩階段提交、查詢樹的任務(wù)。

?

Dispatcher的第三個功能就是協(xié)調(diào)功能，通過
cdbdisp_checkDispatchResult函數(shù)來控制QE的狀態(tài)。有下面四種等待模式。

?

下圖就是一個典型的Dispatcher程序。Greenplum內(nèi)的代碼基本都會遵循這樣的邏輯：分配上下文-分配資源-發(fā)送任務(wù)-等待發(fā)送的完成-等待QE的狀態(tài)-銷毀上下文。

?

Interconnect

第二個模塊就是Interconnect。Greenplum是通過網(wǎng)絡(luò)在QE之間移動數(shù)據(jù)，這個網(wǎng)絡(luò)模塊就是Interconnect。在Motion節(jié)點被初始化時，發(fā)送端和接收端就會建立Interconnect網(wǎng)絡(luò)連接。在Motion節(jié)點執(zhí)行時，就會通過Interconnect來發(fā)送數(shù)據(jù)。

?

下圖是Interconnect的分層介紹。從應(yīng)用層來說，主要任務(wù)是發(fā)送數(shù)據(jù)。Interconnect會對Tuple進行包裝，將其包裝成一個個Chunk。有些Tuple很大，就會進行切割，將其切成多個Chunk。Chunk通過數(shù)據(jù)包發(fā)送給receiver端。應(yīng)用層還有一些數(shù)據(jù)流控制的包，包括EOS包，STOP包等。所有的包都會通過系統(tǒng)傳輸層中的UDPIFC和TCP IC進行傳輸。

?

UDPIFC是Greenplum自己實現(xiàn)的一種RUDP(Reliable User Datagram Protocol）協(xié)議。基于UDP協(xié)議開發(fā)的，為了支持傳輸可靠性，實現(xiàn)了重傳，亂序處理，重傳處理，不匹配處理，流量控制等功能。GPDB當(dāng)初引入UDPIFC主要為了解決復(fù)雜OLAP查詢在大集群中使用連接數(shù)過多的問題。UDPIFC實際上是一種線程模型。

?

后續(xù)，我們也可能會增加一些新的Interconnect類型,包括QUIC協(xié)議，Proxy協(xié)議等，歡迎大家的關(guān)注。

?

關(guān)于Hashjoin的內(nèi)容，由于時間原因，本次分享就不做詳細的講解，如果大家對這一塊感興趣，可以反饋給我們社區(qū)，我們可以在后面添加專門的講解。大家可以參考一下之前Greenplum中文社區(qū)公眾號發(fā)布的關(guān)于Hashjoin的文章來了解相關(guān)內(nèi)容。

總結(jié)

以上是生活随笔為你收集整理的揭秘！Greenplum并行执行引擎到底是如何工作的？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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