近日，PostgreSQL中國技術大會在杭州拉開帷幕。作為 PostgreSQL技術領域的年度盛會， PostgreSQL中國技術大會已經連續12年，為所有熱愛資料庫技術的小夥伴們提供了一個開放合作、共享互助的平台。而本屆大會，圍繞著安全可靠、突破、進化等主題，召集眾多業內大咖和技術高手在這裡進行技術切磋與思想碰撞。
作為國內雲上數據和數據計算領域的 Day-1 准獨角獸，拓數派技術專家郭峰受邀出席本次大會發表主題演講。
在演講中，郭峰介紹了 PieCloudDB Database 打造的全新優化器——「達奇」。「達奇」名稱起源於一款深受年輕人喜愛的遊戲：《荒野大鏢客》。遊戲中一位名為「達奇」的NPC人物的口頭禪正是「I have a plan」，和優化器的主要作用「不謀而合」。
優化器是資料庫系統中的一個重要組件，它「負責」對用戶的查詢請求進行解析、優化和執行計劃的生成，使得查詢結果能夠以最快速度和最高效率得到返回。優化器通過生成最優的查詢執行計劃，來達到優化查詢性能的目的。而執行計劃的好壞往往會造成成百上千的性能差異。PieCloudDB 打造的優化器「達奇」實現了大量的優化特性，作為資料庫系統的「智囊團」，助PieCloudDB 提升性能。
和 PostgreSQL類似，PieCloudDB 查詢優化的處理過程一般被分為四個階段：預處理階段，掃描/連接優化階段，掃描/連接之外的優化階段，後處理階段。「達奇」在這四個處理階段均做了大量優化。
在預處理階段，優化器「達奇」會通過邏輯上的等價變化，將查詢樹轉換為更加簡單高效的等式。由於還未獲得一些統計信息來幫助計算代價信息，本階段一般會通過一些被證明的規則來進行分發約束條件，簡化表達式和連接樹消除無用連接等操作。
- 把 IN, EXISTS 等類型的子查詢轉換為半連接
PieCloudDB 會基於子查詢所在的位置和作用的不同，將子查詢分為子連接（SubLink）和子查詢（SubQuery）。子連接由於出現在WHERE/ON 等約束條件中，常伴隨著ANY/ALL/EXISTS等謂語動詞。如果執行器按照子連接的方式處理，會對查詢效率造成影響。且由於會產生子計劃（SubPlan），優化空間有限。因此，在查詢優化的預處理階段， PieCloudDB 會儘可能地把子連接轉為semi-join或anti-join，從而具有更大的優化空間。
以下面一段的 SQL查詢為 例：
SELECT …
FROM foo
WHERE EXISTS (SELECT 1
FROM bar
WHERE foo.a = bar.c);其中 EXISTS 里是一個子查詢，PieCloudDB 會在預處理階段將其變成一個Semi-Join：
SELECT ...
FROM foo
*SEMI JOIN* bar
ON foo.a = bar.c;- 提升子查詢
出現在 FROM 關鍵字後的子句是子查詢語句。如果不進行提升優化，在對這類子查詢做執行時，會先做一個單獨的計劃，生成一個Sub-query scan，再與 Parent Query 做連接，常常無法找到最優解，造成較大的查詢代價。
以下面的例子為例，如果不做任何提升優化，會將 bar 和 baz 先做 JOIN 連接，由於沒有連接條件，會直接將 bar 和 baz 做笛卡爾乘積，再和外面的 foo 做 JOIN 連接：
SELECT *
FROM foo
JOIN (SELECT bar.c
FROM bar
JOIN baz
ON TRUE) AS sub
ON foo.a = sub.c;而做完提升後，bar 和 baz 就在同一層面上，可以先生成 foo 和 bar的join，再與baz做join連接，從而實現了代價更小：
SELECT *
FROM foo
JOIN (bar JOIN baz
ON TRUE)
ON foo.a = bar.c;- 把外連接轉換為內連接/反連接
外連接對謂詞下推以及連接順序搜索等都會有很多限制，因此「達奇」在預處理階段會儘可能將外連接轉換為內連接（Inner Join）或反連接（Anti Join）。
在下面的 SQL 語句中，LEFT JOIN 的結果會產生一些以 NULL 結尾的 tuple，而 WHERE 條件中的等號為嚴格約束條件，意味著輸入如果為NULL，輸出也必須是NULL或FALSE。如果 bar上的 column 為NULL值，則 bar.d = 42 的過濾結果為FALSE。也就是說，LEFT JOIN 產生的以 NULL 填充的 tuple 會被 WHERE 條件過濾掉，此時，LEFT JOIN 就從語義上變為了INNER JOIN。
SELECT ...
FROM foo
LEFT JOIN bar
ON (...)
WHERE bar.d = 42;在這樣的情況下，PieCloudDB 「達奇」優化器自動識別此類查詢，並利用這樣的優化機會，將外連接轉為內連接。
SELECT ...
FROM foo
INNER JOIN bar
ON (...)
WHERE bar.d = 42;對於某些情況下的外連接，PieCloudDB 優化器會在預處理階段將外連接轉換為反連接。以下面的SQL語句為例
SELECT *
FROM foo
LEFT JOIN bar
ON foo.a = bar.c
WHERE bar.c IS NULL;同前例，LEFT JOIN 也會產生很多以NULL填充的tuple的結果集，此時 WHERE 條件限定只取 bar.c 為NULL 的結果，此時的語義上 LEFT JOIN 就是一個反連接。PieCloudDB 會在預處理階段自動檢測到這種優化機會，並會將外連接轉為內連接：
SELECT *
FROM foo
*ANTI JOIN* bar
ON foo.a = bar.c;除了這些優化，在預處理階段，優化器「達奇」還實現了多個優化，包括：
- 分發約束條件
- 構建等價類
- 收集外連接信息
- 消除無用連接
- 簡化表達式
等…
掃描/連接優化階段可謂是優化器處理過程中最複雜的階段。在這一階段，優化器「達奇」會以代價驅動，處理查詢語句中的 FROM 和 WHERE 部分，同時會考慮到 ORDER BY 的信息。
在這一階段，優化器「達奇」的處理主要可以分為兩步。首先會為基表生成掃描路徑，並計算掃描路徑的代價和結果集大小，從而獲得後面連接操作的代價。第二個步驟中，「達奇」會搜索整個連接順序空間，為連接操作生成最優的連接路徑。這一步驟的複雜度非常高（n！級別），PieCloudDB 採用了動態規劃和遺傳算法兩個算法來進行處理，並根據 GUC 值進行算法選擇。如果查詢語句中涉及外連接，考慮到外連接對連接順序的限制，無法像內連接那樣隨意切換連接順序，會加大這一步驟的複雜度。
相對於第二階段，這一階段雖然處理的事情很多，但複雜度相對較低。在這一階段，「達奇」會先處理Group By、聚集、窗口函數、DISTINCT，再對集合操作進行處理，最後再處理 ORDER BY。以上的每一步操作都會產生一個或多個路徑，「達奇」會對這些路徑根據代價大小進行篩選，並為篩選出的路徑添加 LockRows，Limit，ModifyTable。
經過前面三個階段，「達奇」已經生成了一個大概的查詢計劃。在後處理階段，「達奇」會把選出的最優路徑轉換為查詢計劃，並對最優計劃進行一些調整。
除了上述的優化特性，針對用戶對於雲上數據查詢性能需求，PieCloudDB 優化器「達奇」對複雜查詢場景做了大量的優化和改進，實現了眾多高階的分布式與雲原生特性。
在以上優化特性的基礎上，「達奇」優化器拓展了眾多針對分布式的優化特性。首先「達奇」引入了 Motion 的概念，使數據可以在不同的執行節點（Executor）之間移動。利用 Motion，「達奇」可以產生分布式的查詢計劃。這些查詢計劃會被分為更小的單元，並被分發到不同的執行節點中並行執行。有了並行執行，很多複雜查詢都能進行進一步的優化，例如對於聚集操作，利用分布式的優勢，在執行節點之間可以通過多階段聚集來提升性能。
以這段查詢為例來講解一下多階段聚集，針對這段SQL查詢，「達奇」會生成這樣的查詢計劃：
由於存在一個去重的操作，「達奇」會進行三個階段的聚集，在第一個階段，PieCloudDB 會在每個執行節點上，以 a，b 為 group key 先做一個局部的聚集，這裡就完成了一個局部去重的操作。接著，利用 Motion 做一次 Reshuffle 的操作，此時再進行一次聚集操作，完成全局去重。最後再根據 group key 完成最後的聚集操作，得到查詢結果。
由於PieCloudDB的存儲引擎「簡墨」採用的是對象存儲的設計，結合這一設計，PieCloudDB 優化器「達奇」實現了更多高階的優化，包括聚集下推、Block Skipping、預計算等。這裡將對聚集下推進行介紹，關於「達奇」的其他雲原生特性，歡迎關注即將陸續推出的其他內容。
PieCloudDB 實現了聚集下推（Aggregate Pushdown），可以在查詢執行計劃中有效地減少數據的傳輸和處理，提高查詢效率。在分析型場景中，SUM、AVG、MAX、MIN等聚集操作是常見的操作，可以用來對資料庫表中的數據進行聚合計算。大部分數據倉庫在處理聚集操作時，通常需要先完成對表的掃描和連接操作，之後再計算聚合函數。在數據量非常大的 情況下，這樣的查詢性能會比較低。
而 PieCloudDB 優化器「達奇」實現的聚集下推優化策略，通過把聚集操作下推到連接操作之前去執行，可以極大地減少連接操作需要處理的數據量，經測試，在某些情況下，性能會得到成百甚至上千倍的提升。
以下面的 SQL 查詢為例，這段查詢需要對 t1 表和 t2 表進行連接操作，在此基礎上，根據 t1.a 做分組，來獲得 t2.c 的平均值。在不進行聚集下推優化的情況下，會先完成 t1 和 t2 的連接操作，再按 t1.a的分組進行聚集操作。此時，如果 t1 和 t2 表都很大的話，進行連接操作的代價很高，會對性能產生一定影響。而在進行聚集下推的優化下，會在連接之前先做聚集操作，此時如果 t2.b非常有聚集性，數據量會減小很多，此時再進行連接操作，性能會大幅提高。
查詢優化器是資料庫系統最重要、也是最複雜的組件之一。PieCloudDB作為一款雲原生虛擬數倉，將不斷對優化器「達奇」進行打磨，在確保資料庫系統的高效和穩定運行的前提下，不斷驅動性能的提升。
3月14日，基於新一代雲原生數倉虛擬化打造的PieCloudDB「雲上雲」版已正式發布，歡迎大家免費試用。