本文轉(zhuǎn)載自微信公眾號「阿里技術(shù)」，作者遙凌。轉(zhuǎn)載本文請聯(lián)系阿里技術(shù)公眾號。

本文會深入介紹PolarDB MySQL在并行查詢這一企業(yè)級查詢加速特性上做的技術(shù)探索、形態(tài)演進(jìn)和相關(guān)組件的實(shí)現(xiàn)原理，所涉及功能隨PolarDB MySQL 8.0.2版本上線。

一 背景

1 PolarDB

云的興起為古老而頑固的數(shù)據(jù)庫市場帶來了新的發(fā)展機(jī)遇，據(jù)Gartner預(yù)測，到 2022 年，所有數(shù)據(jù)庫中將有 75% 部署或遷移到云平臺，云原生數(shù)據(jù)庫的誕生為各個(gè)數(shù)據(jù)庫廠商、云服務(wù)供應(yīng)商提供了彎道超車的絕好機(jī)遇，看一下AWS在Re:invent 2020發(fā)布的Babelfish，就能嗅到它在數(shù)據(jù)庫市場的野心有多大。

AWS在2017年發(fā)表的關(guān)于Aurora的這篇paper[1]，引領(lǐng)了云原生關(guān)系型數(shù)據(jù)庫的發(fā)展趨勢，而作為國內(nèi)最早布局云計(jì)算的廠商，阿里云也在2018年推出了自己的云原生關(guān)系數(shù)據(jù)庫PolarDB，和Aurora的理念一致，PolarDB深度融合了云上基礎(chǔ)設(shè)施，目標(biāo)是在為客戶提供云上特有的擴(kuò)展性、彈性、高可用性的同時(shí)，能夠具備更低的響應(yīng)延遲和更高的并發(fā)吞吐，其基本架構(gòu)如下：

底層的分布式共享存儲突破了單機(jī)存儲容量的限制，而且可以隨用戶的數(shù)據(jù)量增長自動(dòng)彈性擴(kuò)容，計(jì)算層則是一寫多讀的典型拓?fù)?，利用RDMA提供的高速遠(yuǎn)程訪問能力來抵消計(jì)算存儲分離帶來的額外網(wǎng)絡(luò)開銷。

2 挑戰(zhàn)

從上圖可以看到，存儲層將允許遠(yuǎn)大于單機(jī)的數(shù)據(jù)容量(目前是128T)，甚至線上會出現(xiàn)一些用戶，單表容量達(dá)到xx T的級別，這在基于MySQL主從復(fù)制的傳統(tǒng)部署中是難以想象的。同時(shí)大量用戶會有對業(yè)務(wù)數(shù)據(jù)的實(shí)時(shí)分析訴求，如統(tǒng)計(jì)、報(bào)表等，但大家對MySQL的直觀印象就是：小事務(wù)處理快，并發(fā)能力強(qiáng)，分析能力弱，對于這些實(shí)時(shí)性分析查詢，該如何應(yīng)對呢?

3 方案

首先要說的是，隨著互聯(lián)網(wǎng)的發(fā)展，數(shù)據(jù)量的爆炸，一定的數(shù)據(jù)分析能力、異構(gòu)數(shù)據(jù)的處理能力開始成為事務(wù)型數(shù)據(jù)庫的標(biāo)配，MySQL社區(qū)在8.0版本中也對自身的查詢處理能力做了補(bǔ)強(qiáng)，包括對子查詢的transformation、hash join、window function支持等，同時(shí)PolarDB MySQL優(yōu)化器團(tuán)隊(duì)也做了大量工作來提升對復(fù)雜查詢的處理能力，如統(tǒng)計(jì)信息增強(qiáng)、子查詢更多樣的transformation、query cache等。

并行查詢(Parallel Query)是PolarDB MySQL在推出伊始就配備的查詢加速功能，本質(zhì)上它解決的就是一個(gè)最核心的問題：MySQL的查詢執(zhí)行是單線程的，無法充分利用現(xiàn)代多核大內(nèi)存的硬件資源。通過多線程并行執(zhí)行來降低包括IO以及CPU計(jì)算在內(nèi)的處理時(shí)間，來實(shí)現(xiàn)響應(yīng)時(shí)間的大幅下降。畢竟，對于用戶來說，一條查詢?nèi)绻梢?分鐘用10個(gè)核完成，總比10分鐘用1個(gè)核完成更有意義。此外所有成熟的商業(yè)型數(shù)據(jù)庫也都具備并行查詢的能力。

二 并行查詢介紹

1 特性

并行查詢可以說是PolarDB MySQL在計(jì)算層最為重要復(fù)雜度也最高的功能組件，隨著PolarDB的推出已經(jīng)線上穩(wěn)定運(yùn)行多年，而且一直在持續(xù)演進(jìn)，它具備如下幾個(gè)特性：

• 完全基于MySQL codebase，原生的MySQL 100%兼容，這里包括

• 語法兼容
• 類型兼容
• 行為兼容

• 0 附加成本，隨產(chǎn)品發(fā)布就攜帶的功能

• 無需額外存儲資源
• 無需額外計(jì)算節(jié)點(diǎn)

• 0 維護(hù)成本，使用和普通查詢沒有任何差別，只是響應(yīng)變快了

• 隨集群部署，開箱即用
• 對業(yè)務(wù)無侵入
• 單一配置參數(shù)(并行度)

• 實(shí)時(shí)性分析，PolarDB原生的一部分，受惠于REDO物理復(fù)制的低延遲

• 統(tǒng)一底層事務(wù)型數(shù)據(jù)
• 提交即可見

• 極致性能，隨著PQ的不斷完善，對于分析型算子、復(fù)雜查詢結(jié)構(gòu)的支持能力不斷提升

• 全算子并行
• 高效流水線
• 復(fù)雜SQL結(jié)構(gòu)支持

• 穩(wěn)定可靠，作為企業(yè)級特性，這個(gè)毋庸置疑

• 擴(kuò)展MySQL測試體系
• 線上多年積累
• 完備診斷體系

上面這些聽起來像是廣告宣傳詞，但也確實(shí)是并行查詢的核心競爭力。

2 演進(jìn)

并行查詢的功能是持續(xù)積累起來的，從最初的PQ1.0到PQ2.0，目前進(jìn)入了跨節(jié)點(diǎn)并行的研發(fā)階段并且很快會上線發(fā)布，這里我們先不介紹跨節(jié)點(diǎn)并行能力，只關(guān)注已上線的情況。

PQ1.0

最早發(fā)布的并行查詢能力，其基本的思路是計(jì)算的下推，將盡可能多的計(jì)算分發(fā)到多個(gè)worker上并行完成，這樣像IO這樣的重操作就可以同時(shí)進(jìn)行，但和一般的share-nothing分布式數(shù)據(jù)庫不同，由于底層共享存儲，PolarDB并行中對于數(shù)據(jù)的分片是邏輯而非物理的，每個(gè)worker都可以看到全量的表數(shù)據(jù)，關(guān)于邏輯分片后面執(zhí)行器部分會介紹。

并行拆分的計(jì)劃形態(tài)典型如下：

可以看到有這么幾個(gè)特點(diǎn)：

• 執(zhí)行模式是簡單的scatter-gather，也就是只有一個(gè)plan slice，多個(gè)worker完成相同的功能，匯總到leader
• 盡可能的下推算子到worker上
• leader負(fù)責(zé)完成無法下推的計(jì)算

這個(gè)方案能夠解決很多線上的慢查詢問題，得到很好的加速效果，不過也存在著一定的局限性

• 計(jì)劃形態(tài)是單一的，導(dǎo)致算子的并行方式單一，比如group by + aggregation，只能通過二階段的聚集來完成：worker先做partial aggregation，leader上做final aggregation
• 一旦leader上完成聚集操作，后續(xù)如果有distinct / window function / order by等，都只能在leader上完成，形成單點(diǎn)瓶頸
• 如果存在數(shù)據(jù)傾斜，會使部分worker沒有工作可做，導(dǎo)致并行擴(kuò)展性差
• 此外實(shí)現(xiàn)上還有一些待完善的地方，例如少量算子不支持并行、一些復(fù)雜的查詢嵌套結(jié)構(gòu)不支持并行

總得來說，PQ1.0的并行形態(tài)和PostgreSQL社區(qū)的方案比較像，還有改進(jìn)空間，畢竟所有商業(yè)數(shù)據(jù)庫的并行形態(tài)都要更靈活復(fù)雜。

PQ2.0

PQ2.0彌補(bǔ)了上面說到的那些局限性，從執(zhí)行模式上對齊了Oracle/SQL Server，實(shí)現(xiàn)了更加強(qiáng)大的多階段并行。

計(jì)劃形態(tài)典型如下：

第一眼看到的變化是這里存在多個(gè)worker group，PQ2.0的執(zhí)行計(jì)劃是多階段的，計(jì)劃會被拆分為若干片段(plan slice)，每個(gè)slice由一組worker并行完成，在slice之間通過exchange數(shù)據(jù)通道傳遞中間結(jié)果，并觸發(fā)后續(xù)slice的流水線執(zhí)行。其中一些補(bǔ)強(qiáng)的點(diǎn)包括：

• 全新的Cost-based并行優(yōu)化器，基于統(tǒng)計(jì)信息和代價(jià)決定最優(yōu)計(jì)劃形態(tài)
• 全算子的并行支持，包括上面提到的復(fù)雜的多層嵌套結(jié)構(gòu)，也可以做到完全的并行
• 引入exchange算子，也就是支持shuffle/broadcast這樣的數(shù)據(jù)分發(fā)操作
• 引入一定自適應(yīng)能力，即使并行優(yōu)化完成了，也可以根據(jù)資源負(fù)載情況做動(dòng)態(tài)調(diào)整，如回退串行或降低并行度

這些改變意味著什么呢?我們來看一個(gè)簡單且實(shí)際的例子：

SELECT t1.a, sum(t2.b)
FROM
t1 JOIN t2 ON t1.a = t2.a
JOIN t3 ON t2.c = t3.c
GROUP BY t1.a
ORDER BY t1.a
LIMIT 10;

對上面的簡單查詢，在經(jīng)過優(yōu)化后，PQ1.0會生成圖中的執(zhí)行計(jì)劃。

• 在join的表集合中，尋找一個(gè)可以做邏輯分片的表做拆分，如果3個(gè)表都不足以拆分足夠多的分片，那就選最多的那個(gè)，比如這里選擇了t2，它可能拆出12個(gè)分片，但仍然無法滿足并行度16的要求，導(dǎo)致有4個(gè)worker讀不到數(shù)據(jù)而idle。
• 聚集操作先在worker上做局部聚集，leader上做匯總聚集，如果各個(gè)worker上分組的聚攏不佳，導(dǎo)致leader仍然會收到來自下面的大量分組，leader上就會仍然有很重的聚集計(jì)算，leader算的慢了，會來不及收worker數(shù)據(jù)，從而反壓worker的執(zhí)行速度，導(dǎo)致查詢整體變慢。

而PQ2.0的執(zhí)行計(jì)劃如下

• 雖然仍然只能在t2上做數(shù)據(jù)分片，但12個(gè)worker只需要完成t1 join t2這個(gè)操作，在join完成后一般數(shù)據(jù)量會膨脹，通過Shuffle(Repartition)將更多的中間結(jié)果分發(fā)到后續(xù)的slice中，從而以更高的并行度完成與t3的join
• 各worker完成局部聚集后，如果分組仍很多，可以基于group by key做一次Shuffle來將數(shù)據(jù)打散到下一層slice，下一組worker會并行完成較重的聚集操作，以及隨后的order by局部排序，最終leader只需要做一次merge sort的匯總

這樣就解決了單點(diǎn)瓶頸和數(shù)據(jù)量不足導(dǎo)致的擴(kuò)展性問題，實(shí)現(xiàn)線性加速。

為什么線性擴(kuò)展如此重要?

從上圖可以看到，隨著并行度的增長，E2E的響應(yīng)時(shí)間是線性下降的，這對于客戶有兩個(gè)重要作用：

• 隨著業(yè)務(wù)增長數(shù)據(jù)不斷膨脹，通過相應(yīng)提高并行度來使用匹配的計(jì)算資源，來持續(xù)得到穩(wěn)定可預(yù)期的查詢性能
• 始終快速的分析時(shí)間可以驅(qū)動(dòng)快速的業(yè)務(wù)決策，使企業(yè)在快速變化的市場環(huán)境中保持競爭力

完美的線性加速就是，Parallel RT = Serial RT / CPU cores，當(dāng)然這并不現(xiàn)實(shí)

3 架構(gòu)

并行查詢組件的整體架構(gòu)如下

核心部分包括在3層中，從上到下依次是：

Cost-based Parallel Optimizer，嵌入在MySQL的優(yōu)化器框架中，完成并行優(yōu)化部分

Parallel Plan Generator，根據(jù)抽象的并行計(jì)劃描述，生成可供worker執(zhí)行的物理執(zhí)行計(jì)劃

Parallel Executor，并行執(zhí)行器組件，包括一些算子內(nèi)并行功能和數(shù)據(jù)分發(fā)功能等

具體每個(gè)組件的實(shí)現(xiàn)會在后面詳細(xì)介紹

4 性能

由于是個(gè)人文章這里隱去了具體執(zhí)行時(shí)間(可以網(wǎng)上搜索下)，主要看下PQ2.0的查詢加速能力，這里并行度是32(可能有同學(xué)會奇怪為什么Q6/Q12的加速比超過了32，后面會具體講到)

總的數(shù)字是：100%的SQL可以被加速，總和加速比是18.8倍。

5 使用方式

從易用性的角度，用戶開啟并行查詢只需要設(shè)置一個(gè)參數(shù)：

set max_parallel_degree = xxx;

如果想查看并行執(zhí)行計(jì)劃，只需要和普通查詢一樣，執(zhí)行EXPLAIN / EXPLAIN FORMAT=TREE 即可。

Explain 做了必要的增強(qiáng)來顯示并行相關(guān)的information，包括代價(jià)、并行模式、分發(fā)方式等。

三 并行查詢實(shí)現(xiàn)

上面是一些總體性的內(nèi)容，沒有什么技術(shù)細(xì)節(jié)，后面的章節(jié)會依次dive到每個(gè)模塊中介紹下。

1 并行優(yōu)化器

在PQ2.0中，由于計(jì)劃形態(tài)會變得更加多樣，如果拆分計(jì)劃只是依靠簡單規(guī)則和簡單統(tǒng)計(jì)是很難得到最優(yōu)解的，因此我們重新實(shí)現(xiàn)了一套完全基于cost的并行優(yōu)化器。

基本的流程是在MySQL串行優(yōu)化后，進(jìn)一步做并行拆分，這里可能有同學(xué)疑惑為什么不像Oracle或Greenplum那樣搞成一體化的，也就是在優(yōu)化流程中統(tǒng)一考慮串/并行的執(zhí)行策略。原因在于，MySQL的優(yōu)化流程中，各個(gè)子步驟之間沒有清晰的邊界，而且深度遞歸的join ordering算法以及嵌入其中的semi-join優(yōu)化策略選擇等，都使得代碼邏輯與結(jié)構(gòu)更加復(fù)雜，很難在不大量侵入原生代碼的前提下實(shí)現(xiàn)一體化優(yōu)化，而一旦對社區(qū)代碼破壞嚴(yán)重，就沒法follow社區(qū)后續(xù)的版本迭代，享受社區(qū)紅利。

因此采用了兩步走的優(yōu)化流程，這也是業(yè)界常用的手法，如Spark、CockroachDB、SQL Server PDW、Oceanbase等都采用了類似的方案。

代價(jià)模型的增強(qiáng)

既然是基于cost的優(yōu)化，在過程中就必然要能夠得到各個(gè)算子并行執(zhí)行的代價(jià)信息。為此PolarDB也做了大量統(tǒng)計(jì)信息增強(qiáng)的工作：

• 統(tǒng)計(jì)信息自動(dòng)更新
• 串行優(yōu)化流程中做針對并行執(zhí)行的補(bǔ)強(qiáng)，例如修正table掃描方式等，這也是上面性能數(shù)據(jù)中Q6/Q12會有超線性加速比的原因
• 全算子統(tǒng)計(jì)信息推導(dǎo)+代價(jià)計(jì)算，補(bǔ)充了一系列的cost formula和cardinality estimation推導(dǎo)機(jī)制

這里只能展示下統(tǒng)計(jì)信息增強(qiáng)帶來的效果，收益的不止是并行查詢，串行執(zhí)行也會提升。

自適應(yīng)執(zhí)行策略

在早期版本中，串行優(yōu)化和并行優(yōu)化，并行優(yōu)化和并行計(jì)劃生成之間存在一定的耦合性，導(dǎo)致的問題就是在開始并行優(yōu)化后會無法退化回串行，如果系統(tǒng)中這樣的查詢并發(fā)較多，會同時(shí)占用很多worker線程導(dǎo)致CPU打爆。新的并行優(yōu)化器解決了這個(gè)問題。

• 串行優(yōu)化與并行優(yōu)化解耦，并行優(yōu)化會重新構(gòu)建抽象算子樹，并以此為輸入開始enumeration
• 并行優(yōu)化與并行計(jì)劃生成解耦，優(yōu)化的結(jié)果是計(jì)劃子片段的抽象描述，作為輸出進(jìn)行plan generation

這樣就使執(zhí)行策略的靈活性成為可能，允許在資源不足情況下，要么退回串行，要么降低并行度，或者進(jìn)入調(diào)度隊(duì)列排隊(duì)等資源。

基于代價(jià)的窮盡式枚舉

這是一個(gè)比較大的話題，概略來說，并行優(yōu)化是一個(gè)自底向上，基于動(dòng)態(tài)規(guī)劃的窮盡式枚舉過程，實(shí)現(xiàn)思路參考了SQL Server PDW paper[2]，在過程中會針對每個(gè)算子，枚舉可能的并行執(zhí)行方式和數(shù)據(jù)分發(fā)方式，并基于輸出數(shù)據(jù)的phsical property(distribution + order)構(gòu)建物理等價(jià)類，從而做局部剪枝，獲取局部子問題的最優(yōu)解并向上層傳遞，最終到root operator獲取全局最優(yōu)解。

下圖是針對t1 NLJ t2這個(gè)算子，做枚舉過程的一個(gè)簡要示例：

在整體枚舉完成后，計(jì)劃空間中會產(chǎn)生一系列帶有數(shù)據(jù)分發(fā)Exchange Enforcer的物理算子樹，基于代價(jià)選擇最優(yōu)樹即可，然后以Enforcer作為子計(jì)劃的切分點(diǎn)，可以構(gòu)建出一系列的執(zhí)行計(jì)劃抽象描述，輸出到plan generator中。

2 并行計(jì)劃生成

從工程實(shí)現(xiàn)角度，并行計(jì)劃生成可以說是整個(gè)組件中復(fù)雜度最高，坑最多的部分。這里采用了physical plan clone的機(jī)制來實(shí)現(xiàn)，也就是說，根據(jù)優(yōu)化器生成的并行計(jì)劃描述，從原始串行計(jì)劃clone出各個(gè)計(jì)劃片段的物理執(zhí)行計(jì)劃。

為什么要用這種方式呢?還是和MySQL本身機(jī)制相關(guān)，MySQL的優(yōu)化和執(zhí)行是耦合在一起的，并沒有一個(gè)清晰的邊界，也就是在優(yōu)化過程中構(gòu)建了相關(guān)的執(zhí)行結(jié)構(gòu)。所以沒有辦法根據(jù)一個(gè)獨(dú)立的計(jì)劃描述，直接構(gòu)建出各個(gè)物理執(zhí)行結(jié)構(gòu)，只能從串行計(jì)劃中“clone”出來，這可以說是一切復(fù)雜度的根源。

MySQL的執(zhí)行結(jié)構(gòu)非常復(fù)雜，expression(Item)和query block(SELECT_LEX)的交叉引用，內(nèi)外層查詢的關(guān)聯(lián)(Item_ref)等等，都使得這項(xiàng)任務(wù)難度大增，但在這個(gè)不斷填坑不斷完善的過程中，團(tuán)隊(duì)也對MySQL的優(yōu)化執(zhí)行結(jié)構(gòu)有了很深入的理解，還發(fā)現(xiàn)了社區(qū)不少bug...

以上圖中簡單的查詢?yōu)槔?/p>

SELECT t1.a, sum(t2.b) sumb
FROM t1 join t2
ON t1.c = t2.c
GROUP BY t1.a
ORDER BY sumb;

雖然社區(qū)對執(zhí)行器做了基于Iterator model的重構(gòu)，但本質(zhì)上，物理執(zhí)行計(jì)劃仍然是由QEP_TAB組成的序列，其中g(shù)roup by+aggr由一個(gè)tmp table1完成，order by由tmp table2完成。

在做plan generation時(shí)，有兩個(gè)核心的操作：

• clone

根據(jù)串行physical plan和子slice的描述，將相對應(yīng)的結(jié)構(gòu)clone到各個(gè)worker線程中，如上圖右下部分，將在worker上執(zhí)行的t1 join t2和下推的聚集操作clone了下來。

• refix

原始的串行計(jì)劃需要轉(zhuǎn)換為leader計(jì)劃，因此要替掉不必要的執(zhí)行結(jié)構(gòu)并調(diào)整一些引用關(guān)系，如上圖右上部分，由于t1 join t2和部分聚集操作已經(jīng)下推，leader上需要去掉不必要的結(jié)構(gòu)，并替換為從一個(gè)collector table中讀取worker傳遞上來的數(shù)據(jù)，同時(shí)需要將后續(xù)步驟中引用的t1/t2表的結(jié)構(gòu)轉(zhuǎn)為引用collector表的對應(yīng)結(jié)構(gòu)。

這里只是舉了最為簡單的例子，還沒有涉及子查詢和多階段plan，實(shí)際的工程實(shí)現(xiàn)成本要高很多。

3 并行執(zhí)行器

PQ實(shí)現(xiàn)了一系列算子內(nèi)并行的機(jī)制，如對表的邏輯分區(qū)和并行掃描，parallel hash join等，來使并行執(zhí)行成為可能或進(jìn)一步提升性能，還有多樣化的子查詢處理機(jī)制等，這里選一些具有代表性的來介紹。

parallel scan

PolarDB是共享存儲的，所有數(shù)據(jù)對所有節(jié)點(diǎn)均可見，這和sharding的分布式系統(tǒng)有所不同，不同worker處理哪一部分?jǐn)?shù)據(jù)無法預(yù)先確定，因此采用了邏輯分區(qū)的方案：

在btree這個(gè)level，會將數(shù)據(jù)切分成很多小分片，不同worker負(fù)責(zé)不同分片來觸發(fā)并行執(zhí)行，這里有一些優(yōu)化點(diǎn)：

盡量做細(xì)粒度的切分，使分片數(shù) >> worker數(shù)，然后worker之間通過round robin的方式去“搶”分片來執(zhí)行，這樣自然做到了能者多勞，避免由于數(shù)據(jù)分布skew導(dǎo)致的負(fù)載不均衡問題，這是shared storage系統(tǒng)的一個(gè)天然優(yōu)勢。

切分時(shí)可以不用dive到葉子節(jié)點(diǎn)，也就是以page作為最小分區(qū)單位，來加速初始分區(qū)速度。

parallel hash join

hash join是社區(qū)8.0為加速分析型查詢所引入的功能，并隨著版本演進(jìn)對semi hash/anti hash/left hash join均做了支持，PolarDB也引入了這些patch來實(shí)現(xiàn)完整的hash join功能，并實(shí)現(xiàn)了多種并行執(zhí)行策略。

parallel hash join在build/probe兩個(gè)階段均做了并行支持

build階段，多個(gè)worker向同一個(gè)共享的lock-free hash table中插入數(shù)據(jù)。

probe階段，多個(gè)worker并行到hash table做搜索。

兩個(gè)階段沒有重疊，這樣就實(shí)現(xiàn)了全階段的并行，但parallel hash join也有自身的問題，例如共享hash table過大導(dǎo)致spill to disk問題，并行插入雖然無鎖，但仍有“同步”原語帶來的cache invalidation。

partition hash join

partition hash join則可以避免以上問題，但代價(jià)則是引入數(shù)據(jù)shuffle的開銷：

如圖所示，查詢的執(zhí)行過程分為了3個(gè)階段

• build/probe兩側(cè)都根據(jù)join key做shuffle，將數(shù)據(jù)分發(fā)到目標(biāo)partition;
• 在每個(gè)partition內(nèi)，build側(cè)各自構(gòu)建小hash table;
• 在每個(gè)partition內(nèi)，probe側(cè)各自查找對應(yīng)的hash table;

這樣就在各個(gè)partition內(nèi)，完成了co-located join，每個(gè)hash table都更小來避免落盤，此外也沒有了build中的并發(fā)問題。

以上兩個(gè)方案哪個(gè)更優(yōu)?由并行優(yōu)化器基于Cost決定。

子查詢并行 - pushdown exec

這里子查詢是表達(dá)式中的一部分，可以存在于select list / where / having等子句中。對于相關(guān)子查詢，唯一的并行方式是隨外層依賴的數(shù)據(jù)(表)下推到worker中，在每個(gè)worker內(nèi)完整執(zhí)行，但由于外層并行了，每個(gè)worker中子查詢執(zhí)行次數(shù)還是可以等比例減少。

例如如下查詢：

SELECT c1 FROM t1
WHERE EXISTS (
  SELECT c1 FROM t2 WHERE t2.a = t1.a     <= EXISTS subquery
  )
ORDER BY c1
LIMIT 10;

EXISTS子查詢完整的clone到各個(gè)worker中，隨著WHERE條件的evaluation反復(fù)觸發(fā)執(zhí)行。

子查詢并行 - pushdown shared

這種并行方式的子查詢可以是表達(dá)式的一部分，也可以是派生表(derived table)。

概略的來說，這種并行方式適用于非相關(guān)子查詢，因此可以提前并行物化掉，形成一個(gè)臨時(shí)結(jié)果表，后續(xù)外層在并行中，各worker引用該子查詢時(shí)可以直接從表中并行讀取結(jié)果數(shù)據(jù)。

例如如下查詢

SELECT c1 FROM t1
WHERE t1.c2 IN (
  SELECT c2 FROM t2 WHERE t2.c1 < 15      <= IN subquery
  )
ORDER BY c1
LIMIT 10;

另外線上用戶的報(bào)表類查詢中，一種非常常見的Query模式就是derived table的多層嵌套，對于這類SQL，pushdown shared策略可以很好的提升并行執(zhí)行的性能，例如如下示例：

上圖中每個(gè)顏色的方塊，代表了一層query block，這里就構(gòu)成了多層derived table的嵌套邏輯，有些層中通過UNION ALL做了匯總，有些層則是多個(gè)表(包括derived table)的join，對于這樣的查詢，MySQL會對每個(gè)derived table做必要的物化，在外層形成一個(gè)臨時(shí)結(jié)果表參與后續(xù)計(jì)算，而PQ2.0對這種常見的查詢模式做了更普遍的支持，現(xiàn)在每一層查詢的執(zhí)行都是并行完成的，力爭達(dá)到線性的加速效果。

Exchanges

要生成高效靈活的執(zhí)行計(jì)劃，數(shù)據(jù)分發(fā)組件是必不可少的，目前PolarDB支持了Shuffle/Broadcast/Gather三種分發(fā)方式，實(shí)現(xiàn)上利用lock-free shared ring buffer，做到流水線模式的高效數(shù)據(jù)傳輸。

下圖展示了Shuffle(Repartition)的基本形態(tài)

到這里，并行查詢的線上版本功能及實(shí)現(xiàn)已經(jīng)大體介紹完了。

作為一款成熟的企業(yè)級功能特性，團(tuán)隊(duì)還實(shí)現(xiàn)了一整套完善的輔助工具集，來配合提升產(chǎn)品的易用性，實(shí)現(xiàn)功能的可監(jiān)控、可干預(yù)、可反饋，但這里篇幅已經(jīng)很大了，就先不介紹了。

四 未來規(guī)劃

這里說是未來規(guī)劃并不確切因?yàn)閳F(tuán)隊(duì)已經(jīng)在跨節(jié)點(diǎn)并行上做了大量的工作并進(jìn)入了開發(fā)周期的尾端，跨節(jié)點(diǎn)的并行會把針對海量數(shù)據(jù)的復(fù)雜查詢能力提升到另一個(gè)水平：

• 打通節(jié)點(diǎn)間計(jì)算資源，實(shí)現(xiàn)更高的計(jì)算并行度
• 突破單節(jié)點(diǎn)在IO / CPU上的瓶頸，充分利用分布式存儲的高吞吐能力
• 結(jié)合全局節(jié)點(diǎn)管理與資源視圖，平衡調(diào)度全局計(jì)算資源，實(shí)現(xiàn)負(fù)載均衡的同時(shí)保證查詢性能
• 結(jié)合全局一致性視圖，保證對事務(wù)性數(shù)據(jù)的正確讀取

[1]https://www.allthingsdistributed.com/files/p1041-verbitski.pdf

[2]https://www.scinapse.io/papers/2160963784#fullText