深度解析 PolarDB 數(shù)據(jù)庫(kù)并行查詢(xún)技術(shù)

作者：智鄰 2021-05-13 14:34:34

云計(jì)算 隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，用戶(hù)SQL的執(zhí)行時(shí)間越來(lái)越長(zhǎng)，這不僅對(duì)數(shù)據(jù)庫(kù)的優(yōu)化能力提出更高的要求，并且對(duì)數(shù)據(jù)庫(kù)的執(zhí)行模式也提出了新的挑戰(zhàn)。本文主要介紹基于代價(jià)進(jìn)行并行優(yōu)化、并行執(zhí)行的云數(shù)據(jù)庫(kù)的并行查詢(xún)引擎的關(guān)鍵問(wèn)題和核心技術(shù)。

創(chuàng)新互聯(lián)長(zhǎng)期為上1000家客戶(hù)提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為長(zhǎng)豐企業(yè)提供專(zhuān)業(yè)的成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)，長(zhǎng)豐網(wǎng)站改版等技術(shù)服務(wù)。擁有十年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。

 [[399309]]

一、背景

隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，用戶(hù)SQL的執(zhí)行時(shí)間越來(lái)越長(zhǎng)，這不僅對(duì)數(shù)據(jù)庫(kù)的優(yōu)化能力提出更高的要求，并且對(duì)數(shù)據(jù)庫(kù)的執(zhí)行模式也提出了新的挑戰(zhàn)。隨著數(shù)據(jù)庫(kù)在云上的蓬勃發(fā)展，越來(lái)越多的傳統(tǒng)用戶(hù)遷移到云上，享受云上彈性擴(kuò)展的紅利，但是隨著業(yè)務(wù)的快速擴(kuò)張，卻發(fā)現(xiàn)即使動(dòng)態(tài)增加了很多資源，但SQL的執(zhí)行時(shí)間還是越來(lái)越慢，并沒(méi)有隨著資源的投入達(dá)到預(yù)期的效果。顯而易見(jiàn)，雖然新增了很多資源，但這些資源并沒(méi)用被充分利用，很多傳統(tǒng)的商業(yè)數(shù)據(jù)庫(kù)，如Oracle、SQL Server等都提供對(duì)并行查詢(xún)引擎的支持，以充分利用系統(tǒng)資源，達(dá)到加速SQL執(zhí)行的效果。

本文主要介紹基于代價(jià)進(jìn)行并行優(yōu)化、并行執(zhí)行的云數(shù)據(jù)庫(kù)的并行查詢(xún)引擎的關(guān)鍵問(wèn)題和核心技術(shù)。

二、如何將查詢(xún)并行起來(lái)

對(duì)于一個(gè)類(lèi)OLAP的查詢(xún)，顯而易見(jiàn)的是它通常是對(duì)大批量數(shù)據(jù)的查詢(xún)，數(shù)據(jù)量大意味著數(shù)據(jù)遠(yuǎn)大于數(shù)據(jù)庫(kù)的內(nèi)存容量，大部分?jǐn)?shù)據(jù)可能無(wú)法緩存到數(shù)據(jù)庫(kù)的緩沖區(qū)中，而必須在查詢(xún)執(zhí)行時(shí)才動(dòng)態(tài)加載到緩沖區(qū)中，這樣就會(huì)造成大量IO操作，而IO操作又是最耗時(shí)的，因此首先要考慮的就是如何能加速I(mǎi)O操作。

由于硬件的限制，每次IO的耗時(shí)基本是固定的，雖然還有順序IO和隨機(jī)IO的區(qū)別，但在SSD已經(jīng)盛行的今天，兩者的差異也在逐漸接近。那么還有沒(méi)有其它方式可以加速I(mǎi)O呢? 顯然并行IO是一個(gè)簡(jiǎn)單易行的方法，如果多個(gè)線程可以同時(shí)發(fā)起IO，每個(gè)線程只讀取部分?jǐn)?shù)據(jù)，這樣就可以快速的將數(shù)據(jù)讀到數(shù)據(jù)庫(kù)的緩沖區(qū)中。

并行讀取數(shù)據(jù)的示意如上圖所示，每個(gè)worker代表一個(gè)線程，如果數(shù)據(jù)已經(jīng)有partition分區(qū)，可以每個(gè)線程讀取一個(gè)partition；也可以將全部數(shù)據(jù)按固定大小進(jìn)行分片，比如按一個(gè)數(shù)據(jù)頁(yè)面大小，然后每個(gè)線程以Round-robin模式輪詢(xún)讀取一個(gè)分片。

這里需要注意的是，按已有partition分配給不同worker可能會(huì)導(dǎo)致每個(gè)worker處理的數(shù)據(jù)不均勻，而按Round-robin模式進(jìn)行輪詢(xún)，如果分片設(shè)置的比較小，相對(duì)來(lái)說(shuō)就比較容易做到每個(gè)worker處理的數(shù)據(jù)比較均勻。

如果只是將數(shù)據(jù)讀取到緩沖區(qū)中，而不是立即進(jìn)行后續(xù)處理，那么這些數(shù)據(jù)就會(huì)因緩沖區(qū)爆滿(mǎn)導(dǎo)致數(shù)據(jù)被換出，從而失去加速I(mǎi)O的意義。因此，在并行讀取數(shù)據(jù)的同時(shí)，必須同時(shí)并行的處理這些數(shù)據(jù)，這是并行查詢(xún)加速的基礎(chǔ)。

傳統(tǒng)的優(yōu)化器只能生成串行的執(zhí)行計(jì)劃，為了實(shí)現(xiàn)并行讀取數(shù)據(jù)，同時(shí)并行處理數(shù)據(jù)，首先必須對(duì)現(xiàn)有的優(yōu)化器進(jìn)行改造，讓優(yōu)化器可以生成我們需要的并行計(jì)劃。比如選擇哪個(gè)表或哪些表可以并行讀取，并且通過(guò)并行讀取會(huì)帶來(lái)足夠的收益；或者哪些操作可以并行執(zhí)行，并且可以帶來(lái)足夠的收益。

并不是說(shuō)并行化改造一定會(huì)有收益，比如對(duì)一個(gè)數(shù)據(jù)量很小的表，可能只是幾行，如果也對(duì)它進(jìn)行并行讀取的話，并行執(zhí)行所需要的多線程構(gòu)建再加上線程間的數(shù)據(jù)同步等所需要的代價(jià)可能遠(yuǎn)大于所得到的收益，總體來(lái)說(shuō)，并行執(zhí)行會(huì)需要更多的資源和時(shí)間，這就得不償失了。因此查詢(xún)計(jì)劃的并行化必須是基于代價(jià)的，否則可能會(huì)導(dǎo)致更嚴(yán)重的性能退化問(wèn)題。

三、如何選擇并行掃描的表

選擇并行掃描的表是生成并行計(jì)劃的重要基礎(chǔ)，通過(guò)基于并行掃描代價(jià)的計(jì)算和比較，選擇可以并行掃描的表作為候選，是并行執(zhí)行計(jì)劃迭代的第一步?；谛碌牟⑿写鷥r(jià)，也許會(huì)有更優(yōu)的JOIN順序選擇，尤其是當(dāng)參與JOIN的表的數(shù)量比較多時(shí)，這需要更多額外的迭代空間，為防止優(yōu)化過(guò)程消耗太多的時(shí)間，保持原有計(jì)劃的JOIN順序是一個(gè)不錯(cuò)的選擇。另外，對(duì)于參與JOIN的每張表，因?yàn)楸淼脑L問(wèn)方法不同，比如全表掃描、Ref索引掃描，Range索引掃描等，這些都會(huì)影響到最終并行掃描的代價(jià)。

通常我們選擇最大的那張表作為并行表，這樣并行掃描的收益最大，當(dāng)然也可以選擇多個(gè)表同時(shí)做并行掃描，后面會(huì)繼續(xù)討論更復(fù)雜的情況。

下面以查詢(xún)年度消費(fèi)TOP 10的用戶(hù)為例：

SELECT c.c_name, sum(o.o_totalprice) as s FROM customer c, orders o WHERE c.c_custkey = o.o_custkey AND o_orderdate >= '1996-01-01' AND o_orderdate <= '1996-12-31' GROUP BY c.c_name ORDER BY s DESC LIMIT 10;

其中orders表為訂單表，數(shù)據(jù)很多，這類(lèi)表也被稱(chēng)之為事實(shí)表，customer表為客戶(hù)表，數(shù)據(jù)相對(duì)較少，這類(lèi)表也被稱(chēng)之為維度表。那么此SQL的并行執(zhí)行計(jì)劃如下圖所示：

從計(jì)劃中可以看出orders表會(huì)做并行掃描，由32個(gè)workers線程來(lái)執(zhí)行，每個(gè)worker只掃描orders表的一部分?jǐn)?shù)據(jù)分片，然后與customer表按o_custkey做index lookup進(jìn)行JOIN，JOIN的結(jié)果發(fā)送到一個(gè)collector組件，然后由collector組件繼續(xù)做后續(xù)的GROUP BY、ORDER BY及LIMIT操作。

四、選擇多表并行的JOIN

將一張表做并行掃描之后，就會(huì)想為什么只能選擇一張表？如果SQL中有2張或更多的FACT表，能不能可以將FACT表都做并行掃描呢？答案是當(dāng)然可以。以下面SQL為例：

SELECT o.o_custkey, sum(l.l_extendedprice) as s FROM orders o, lineitem l WHERE o.o_custkey = l.l_orderkey GROUP BY o.o_custkey ORDER BY s LIMIT 10;

其中orders表和lineitem表都是數(shù)據(jù)量很大的事實(shí)表，此SQL的并行執(zhí)行計(jì)劃如下圖所示：

從計(jì)劃中可以看到orders表和lineitem表都會(huì)做并行掃描，都由32個(gè)workers線程來(lái)執(zhí)行。那么多個(gè)表的并行是如何實(shí)現(xiàn)的呢？我們以2個(gè)表為例，當(dāng)2個(gè)表執(zhí)行JOIN時(shí)，通常的JOIN方式有Nested Loop JOIN、HASH JOIN等，對(duì)于不同的JOIN方式，為保證結(jié)果的正確性，必須選擇合理的表掃描方式。

以HASH JOIN為例，對(duì)于串行執(zhí)行的HASH JOIN來(lái)說(shuō)，首先選擇一個(gè)表創(chuàng)建HASH表稱(chēng)之為Build表，然后讀取另一個(gè)Probe表，計(jì)算HASH，并在Build表中進(jìn)行HASH匹配，若匹配成功，輸出結(jié)果，否則繼續(xù)讀取。如果改為并行HASH JOIN，并行優(yōu)化器會(huì)對(duì)串行執(zhí)行的HASH JOIN進(jìn)行并行化改造，使之成為并行HASH JOIN，并行化改造的方案可以有以下兩種解決方案。

方案一是將2個(gè)表都按HASH key進(jìn)行分區(qū)，相同HASH值的數(shù)據(jù)處于同一個(gè)分區(qū)內(nèi)，由同一個(gè)線程執(zhí)行HASH JOIN。方案二是創(chuàng)建一個(gè)共享的Build表，由所有執(zhí)行HASH JOIN的線程共享，然后每個(gè)線程并行讀取屬于自己線程的另外一個(gè)表的分片，再執(zhí)行HASH JOIN。最終選擇哪種方案，通過(guò)代價(jià)估算來(lái)決定。

圖2 并行HASH JOIN示意圖

對(duì)于方案一，需要讀取表中的所有數(shù)據(jù)，根據(jù)選中的HASH key，對(duì)數(shù)據(jù)進(jìn)行分區(qū)，并將數(shù)據(jù)發(fā)送到不同的處理線程中，這需要額外增加一個(gè)Repartition算子，負(fù)責(zé)根據(jù)分區(qū)規(guī)則將數(shù)據(jù)發(fā)送到不同的處理線程。對(duì)于方案二，需要并行創(chuàng)建共享的HASH build表，當(dāng)build表創(chuàng)建成功后，每個(gè)線程讀取Probe表的一個(gè)分片，分別執(zhí)行HASH JOIN，這里的分片并不需要按照HASH key進(jìn)行分片，每個(gè)線程分別讀取互不相交的分片即可。

五、分析統(tǒng)計(jì)的復(fù)雜算子的并行

對(duì)于一個(gè)分析統(tǒng)計(jì)的需求，GROUP BY操作是繞不開(kāi)的操作，尤其對(duì)大量的JOIN結(jié)果再做GROUP BY操作，是整個(gè)SQL中最費(fèi)時(shí)的一個(gè)過(guò)程，因此GROUP BY的并行也是并行查詢(xún)引擎必須優(yōu)先解決的問(wèn)題。

以年度消費(fèi)TOP10客戶(hù)的SQL為例，對(duì)GROUP BY并行化后的并行執(zhí)行計(jì)劃如下圖所示：

與之前的執(zhí)行計(jì)劃相比，新的執(zhí)行計(jì)劃中多了一個(gè)collector組件，總共有2個(gè)collector組件。首先我們看第二行的collector組件，它的extra信息中有2條"Using temporary; Using filesort"，這表示它是對(duì)從workers接收到的數(shù)據(jù)執(zhí)行GROUP BY，然后再按ORDER排序，因?yàn)橹挥械谝粋€(gè)collector組件在用戶(hù)的session中，所以這個(gè)collector也是在worker中并行執(zhí)行，也就是說(shuō)并行的做Group by和Order by以及Limit；然后看第一行的collector組件，它的extra信息中只有一條"Merge sort"，表示session線程對(duì)從workers接收到的數(shù)據(jù)執(zhí)行一次merge sort，然后將結(jié)果返回給用戶(hù)。這里可能就有人會(huì)提出疑問(wèn)，為什么session線程只做merge sort就可以完成GROUP BY操作呢？另外LIMIT在哪里呢？

首先回答第2個(gè)問(wèn)題，因?yàn)閑xplain計(jì)劃顯示的問(wèn)題，在常規(guī)模式下不顯示LIMIT操作，但在Tree模式下會(huì)顯示LIMIT操作。如下所示：

從Tree型計(jì)劃樹(shù)上可以清楚的看到LIMIT操作有2處，一處在計(jì)劃的頂端，也就是在session上，做完limit后將數(shù)據(jù)返回給用戶(hù)；另外一處在計(jì)劃樹(shù)的中間位置，它其實(shí)是在worker線程的執(zhí)行計(jì)劃上，在每個(gè)worker線程中在排序完成后也會(huì)做一次limit，這樣就可以極大減少worker返回給session線程的數(shù)據(jù)量，從而提升整體性能。

下面來(lái)回答第一個(gè)問(wèn)題，為什么GROUP BY只需要在worker線程上執(zhí)行一次就可以保證結(jié)果的正確性。通常來(lái)說(shuō)，每個(gè)worker只有所有數(shù)據(jù)的一個(gè)分片，只在一個(gè)數(shù)據(jù)分片上做GROUP BY是有極大的風(fēng)險(xiǎn)得到錯(cuò)誤的GROUP BY結(jié)果的，因?yàn)橥籊ROUP分組的數(shù)據(jù)可能不只是在本W(wǎng)ORKER的數(shù)據(jù)分片上，也可能在其它WORKER的數(shù)據(jù)分片中，被其它WORKER所持有。但是如果我們可以保證同一GROUP分組的數(shù)據(jù)一定位于同一個(gè)數(shù)據(jù)分片，并且這個(gè)數(shù)據(jù)分片只被一個(gè)WORKER線程所持有，那么就可以保證GROUP BY結(jié)果的正確性。通過(guò)Tree型執(zhí)行計(jì)劃可以看到，在并行JOIN之后，將JOIN的結(jié)果按GROUP分組的KEY值: c.c_name進(jìn)行Repartition操作，將相同分組的數(shù)據(jù)分發(fā)到相同的WORKER，從而保證每個(gè)WORKER擁有的數(shù)據(jù)分片互不交叉，保證GROUP BY結(jié)果的正確性。

因?yàn)槊總€(gè)WORKER的GROUP BY操作已經(jīng)是最終結(jié)果，所以還可以將ORDER BY和LIMIT也下推到WORKER來(lái)執(zhí)行，進(jìn)一步提升了并行執(zhí)行的效率。

六、并行查詢(xún)引擎對(duì)TPCH的線性加速

附圖是一個(gè)并行查詢(xún)引擎對(duì)TPCH的加速效果，TPC-H中100%的SQL可以被加速，70%的SQL加速比超過(guò)8倍，總和加速近13倍，Q6和Q12加速甚至超過(guò)32倍。

七、總結(jié)

數(shù)據(jù)庫(kù)是應(yīng)用系統(tǒng)的核心，而優(yōu)化器是數(shù)據(jù)庫(kù)的核心，優(yōu)化器的好壞幾乎可以決定一個(gè)數(shù)據(jù)庫(kù)產(chǎn)品的成敗。開(kāi)發(fā)一個(gè)全新的優(yōu)化器，對(duì)任何團(tuán)隊(duì)都是一個(gè)巨大的挑戰(zhàn)，技術(shù)的復(fù)雜度暫且不提，就是想做到產(chǎn)品的足夠穩(wěn)定就是一個(gè)非常難以克服的困難。因此即使傳統(tǒng)商業(yè)數(shù)據(jù)庫(kù)，也是在現(xiàn)有優(yōu)化器的基礎(chǔ)上不斷改進(jìn)，逐漸增加對(duì)并行的支持，最終成為一個(gè)成熟的并行優(yōu)化器。對(duì)PolarDB也是如此，在設(shè)計(jì)和開(kāi)發(fā)并行查詢(xún)引擎時(shí)，我們充分利用現(xiàn)有優(yōu)化器的技術(shù)積累和實(shí)現(xiàn)基礎(chǔ)，不斷改進(jìn)，不斷打磨，最終形成了一個(gè)持續(xù)迭代的技術(shù)方案，以保證新的優(yōu)化器的穩(wěn)定運(yùn)行和技術(shù)革新。

 

網(wǎng)頁(yè)標(biāo)題：深度解析PolarDB數(shù)據(jù)庫(kù)并行查詢(xún)技術(shù)
本文來(lái)源：http://m.5511xx.com/article/djjodop.html