幾十張表關聯？小 Case！

作者介紹

qiannzhang（張倩），騰訊雲數據庫專家工程師，具備多年數據庫內核研發經驗，在大數據分析領域深耕多年。加入騰訊後，主要負責 CDW PG 數據庫 SQL 引擎相關特性的研發工作。

背景介紹

CDW PG 是騰訊自主研發的新一代分佈式數據庫，採用無共享的 MPP 集羣架構，具備業界領先的數據分析查詢處理能力，適用於 PB 級海量數據的 OLAP 應用場景。

在 OLAP 場景中，多表連接查詢是最主要的查詢類型之一。CDW PG 支持多種連接類型，包括 left join、right join、inner join 和 full join 等。對於 left join 和 right join 來說，表的連接順序是固定的，所以可選擇的路徑相對較少。但對於 inner join 來說，表的連接順序可以互換，不同的連接順序可能產生巨大的性能差異。

那麼，當連接查詢中表的數量不斷增加的時候，CDW PG 的優化器是如何找到一個最優的連接順序路徑，從而生成一個高效的查詢計劃呢?

搜尋最優解

在數據庫中，表的掃描路徑有順序掃描、索引掃描和位圖掃描等幾種掃描方法。如果表上建有多個索引，還可能產生多個不同的索引掃描。優化器面臨的第一個問題是，如何在所有的可能中選擇一個比較好的掃描路徑。

對於涉及單表的查詢，通常情況下我們只需要選擇代價較小的那一個掃描路徑即可。但在多表連接的情況下，除了確定每個表的掃描路徑，還需要確定使用的連接算法和連接順序。CDW PG 中支持三種表連接算法，分別是 Hashjoin、Mergejoin 和 Nestloop。

通常情況下，表的掃描路徑、連接算法和連接順序三者之間還存在互相影響。以三表連接 A join B join C on a1=b1 and b1=c1 爲例，假設表 C 在列 c1 上建有索引，那麼我們可能會得到下面幾種計劃（實際中遠不止下述幾種可能）：

顯然，這是一個搜索所有路徑尋求最優解的過程。在數據庫優化器中，路徑搜索算法通常有三種：自底向上、自頂向下和隨機方法。根據連接表數量的不同，CDW PG 的優化器中使用了自底向上的動態規劃和隨機的遺傳算法兩種方法。

動態規劃搜尋全局最優解

在動態規劃算法中，首先需要通過重複使用子問題的解，減少計算量、降低問題複雜度；還有就是能夠通過子問題的最優解構造出最終問題的最優解，即問題的解需要具有最優子結構性質。

具體到當前的表連接問題上，優化器採用自底向上的方法，首先從單表開始，每個表支持的每一種掃描路徑作爲第一層子問題的解。然後，從每兩表連接開始考慮，計算出每兩表連接的代價，作爲第二層子問題的解。

第一層子問題和第二層子問題如下圖所示，當前僅簡化展示支持單種掃描路徑和單種 join 類型的情況：

兩表的連接結果可以認爲是一個新表，此時利用第一層和第二層子問題的解，繼續進行連接，得到第三層子問題的解，如下圖所示：

在實際的查詢計劃生成過程中，並不是所有的表之間都可以做連接，所以動態規劃算法的路徑搜索複雜度是基本可控的。例如三表連接 A join B join C on a1=b1 and a2=c1，其中表 B 和表 C 之間沒有連接關係，在第二層子問題中將只有 AB、BA、AC、和 CA 四種可能的連接路徑。

但是，如果表的數量過多，動態規劃算法仍然存在搜索空間過大的問題，此時 CDW PG 優化器會採用遺傳算法，獲得一個局部最優解，從而達到一個性價比較優的結果。

遺傳算法搜尋局部最優解

一般來說，遺傳算法的實現包括以下幾個步驟：

具體到當前的表連接問題上，優化器將參與連接的表作爲基因、不同的連接路徑作爲染色體、連接路徑的總代價作爲適應度。在每次迭代中，通過對隨機選取的染色體進行交叉操作，產生新的連接路徑，並通過適應度計算，淘汰不良的染色體，經過 N 輪之後獲取一個局部最優的連接路徑。

在 CDW PG 中，用戶可以通過設置 GUC 參數 enable_geqo 選擇是否開啓使用遺傳算法，並可以通過設置 GUC 參數 geqo_threshold，選擇在連接表的數量大於等於該閾值時使用遺傳算法。

例如，當設置 enable_geqo=true 並且 geqo_threshold=12 時，表示當連接表的數量不小於 12 時，優化器將使用遺傳算法生成連接路徑，否則將使用動態規劃算法生成連接路徑。

連接中的數據重分佈

CDW PG 採用的是 MPP 架構，其中的數據表支持兩種類型的數據分佈，Shard 分佈和 Replication 分佈。Shard 分佈是指表中的數據按某一列或某幾列的值，經過函數計算後選擇不同的存儲節點，其特點是分佈鍵值相同的數據必然存儲在同一個節點上，所有節點存儲的數據總和爲一份全量的表數據；Replication 分佈是指表在所有存儲節點上都存儲着一份全量的表數據。

在 CDW PG 中，不同分佈類型的表在連接選擇時，除了掃描路徑、連接類型和連接順序外，還需要根據分佈鍵和連接鍵的匹配情況，選擇對應的數據重分佈路徑，以保證連接結果正確性。

表 Replication 分佈

當連接兩側的表中，有一側表是 Replication 分佈時，不管另一側表的分佈鍵和連接鍵是否匹配，當前不需要進行數據重分佈就可以進行連接操作。

例如 A join B on a1=b1，假設 A 表按 a2 列 Shard 分佈，B 表是 Replication 分佈，此時允許直接進行連接操作，其連接結果是按 A 表的 a2 列 Shard 分佈，可繼續參與後續的連接路徑計算。

連接條件匹配表 Shard 分佈

當連接兩側的表均爲 Shard 分佈，並且分佈鍵和連接鍵是匹配的情況下，由於 Shard 分佈可以保證對應列值相同的數據存儲在同一節點上，當前仍然不需要進行數據重分佈操作，可直接進行連接。

例如 A join B on a1=b1，假設 A 表按 a1 列 Shard 分佈，B 表按 b1 列 Shard 分佈，此時允許直接進行連接操作，其連接結果是按 A 表 a1 列（等價於 B 表 b1 列）Shard 分佈，可繼續參與後續的連接路徑計算。

連接條件不匹配表 Shard 分佈

當連接兩側的表均爲 Shard 分佈，但是分佈鍵和連接鍵不匹配的情況下，需要視情況對其中一側或兩側的表進行數據重分佈，將連接鍵值相同的數據重分佈到同一節點上，以保證連接結果的正確性。

例如 A join B on a1=b1，假設 A 表按 a2 列 Shard 分佈，B 表按 b1 列 Shard 分佈，此時需要將 A 表按 a1 列進行數據重分佈後，再與 B 表連接，其連接結果按 A 表 a1 列（等價於 B 表 b1 列）Shard 分佈，如下圖所示。

同樣的查詢，假設 A 表按 a2 列 Shard 分佈，B 表按 b2 列 Shard 分佈，則需要將 A 表按 a1 列、B 表按 b1 列分別進行數據重分佈後，再執行連接操作，其連接結果分佈方式同上，如下圖所示。

在分佈鍵和連接鍵不匹配的情況下，我們還可以選擇將其中一側的表進行 Replication 分佈後，再執行連接操作，此時連接結果可能具有不同的分佈方式。

例如，對上述 Plan 2，還可以對錶 A 進行 Replication 分佈，再執行連接操作，其連接結果按 B 表 b2 列 Shard 分佈；或者對錶 B 進行 Replication 分佈，再執行連接操作，其連接結果按 A 表 a2 列 Shard 分佈，兩種計劃分別如下圖所示。

優化器具體選擇哪種數據重分佈路徑，同樣是在上述搜尋最優解的算法框架內，按照代價進行選擇，此時連接結果的分佈方式也有一定影響。

數據分佈選擇的一些建議

顯然，在 MPP 架構中，數據表分佈方式的不同，將直接影響連接查詢的性能。通常情況下，我們建議將類似維度表的數據表建成 Replication 分佈，事實表按常用的連接鍵進行 Shard 分佈，能夠不同程度地提升連接查詢性能。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/SLbTRVW2g9u8olFhyjCnTQ

猜你喜歡