SQL 查詢優化原理與 Volcano Optimizer 介紹

本文轉載自：https://io-meter.com/2018/11/01/sql-query-optimization-volcano/?from=timeline&isappinstalled=0

隨著大數據相關技術的發展，SQL 作為一種成熟的查詢語言又逐漸回到人們視野的中心來，被稱為 NewSQL 的新型關係型數據庫更是蓬勃發展。 作為一種聲明式編程語言，將 SQL 轉化為可以高效執行的任務對於 OLAP 任務來說是至關重要的。 本文將嘗試對相關的技術原理進行一次總結。

本文將重點著眼於對 Volcano(Cascades) Optimizer的詳細介紹上，這是因為 Volcano 模型不但十分流行， 更是被 Apache Calcite 這一優秀的開源框架所做到了。 我們因此可以通過直接閱讀 Calcite 的源碼來了解算法執行的內部細節。

盡管 Apache Calcite 這一項目並不是經常出現在人們眼前，但卻是 Apache 數據平台技術棧當中及其有價值的組件。 它提供了一套 SQL 的解析與執行接口，包含了 SQL 查詢和執行相關的一系列任務的執行代碼。 使用者只需要將自己的數據模型 Plugin 到 Calcite 當中，就可以得到 SQL 查詢的能力。 包括 Apache Storm, Apache Flink, Apache Kylin 和 Apache Drill 等項目都使用它完成 SQL 解析或執行的操作。

遺憾的是，除了相關論文之外，其文檔等對於內部細節的介紹都不夠充分。 本文作為對其部分代碼細節進行閱讀之後的淺顯總結，同時也希望能為各位讀者使用 Calcite 有所幫助。

另外值得注意的是，本文使用 Volcano Optimizer 代指 Volcano 和 Cascades 兩種算法， 一個是因為二者是一脈相承的關係，很多基本思想是一樣的，另外一點是很多有關 Volcano 優化器的相關信息其實是由 Cascades 相關的 Paper 總結和介紹的。

SQL 查詢優化的目的

SQL 查詢優化在 OLAP 應用當中至關重要的主要原因在於 SQL 是一種聲明式(Declarative)的編程語言， 相比一般的編程語言描述的是程序執行的過程，這類編程語言則是描述問題或者需要的結果本身。 具體的執行步驟則交由程序自己決定。

從使用的角度，SQL 作為一種可以被非相關技術人員快速入手的編程語言， 其主要優點就在於即使用戶因並不了解數據庫內部的做到細節而寫出來十分糟糕的查詢語句， 只要表達的意思準確清楚，數據庫就可以在一定程度上將其轉化為合理的執行方案高效的返回結果， 極大的降低了使用門檻。因此一個好的查詢優化器，也是關係型數據庫重要的賣點之一。

從技術的角度來說，通過對用戶輸入的查詢進行優化，做到更優的執行步驟規劃 數據庫可以做到更快的執行和更少的 IO 消耗。從而節約資源提高性能。

SQL 查詢優化的基本原理

SQL 作為一項圖靈獎級別的發明，其重要意義不單單是發明了一種可以用作數據查詢的語言， 更重要的一點是發明了關係代數(Relation Algebra)這一工具， 使得計算機理解和處理查詢的語義更加方便。SQL 查詢語句的優化也是基於關係代數這一模型。

所謂關係代數，是 SQL 從語句到執行計劃的一種中間表示。首先它不是單純的抽象語法樹(AST)， 而是一種經過進一步處理得到的中間表示(可以類比一般編程語言的 IR)。SQL 優化的本質是對關係代數的優化。

關於關係代數的具體內容這里不再贅述，我們直接來看一個例子。假設我們有如下的 SQL:

上述 SQL 假定我們有兩個數據表pv和user，前者記錄了用戶的 Pageview 訪問， 後者是用戶信息表。這兩張表可以使用siteId和userId(user.id)連立合併起來， 這樣我們就既可以查到用戶的 PV 信息，又可以將 PV 信息對應到用戶資料。

將上述 SQL 表示成關係代數，可能是如下形式:

可以看到，上述關係代數將 SQL 表示成樹形的結構，樹形結構的葉子結點是 SCAN 算子， 負責從儲存設備將表中的信息讀出。之後兩個表的數據被輸送到 JOIN 算子中做到合併計算。 JOIN 得到的數據又被輸入一個 FILTER 算子中執行 WHERE 語句的條件(即過濾操作)。 最後的頂層算子是 PROJECT 算子，這個算子可以將輸入數據當中的指定列取出，也可以對這些列進行重命名。

顯然，關係代數本身就一定程度上體現了 SQL 查詢的計算方案。 一般來說，實際的數據庫做到還存在邏輯代數處理階段和物理做到處理階段， 這兩個階段使用的算子不同。數據流動也存在 Pull 模式和 Push 模式兩種。 在這里我們先略去對這些信息的討論，單純研究如何通過關係代數優化執行方案。

觀察上述關係代數的表示，我們發現最終的結果只需要使用到pv.siteId、pv.userIduser.id和user.nickname四列數據。即使我們的表有幾十列其他的數據，也對最終的結果沒有影響。 將這些表的其他列讀取出來向上傳輸和計算是一種浪費。如果我們的表支持高效地只讀取需要的列， 那麼從一開始就這麼做會大大提高性能。下圖描述了這種變換:

通過只讀取特定列來減少 IO 損耗、增加執行性能的技巧正是現今流行的列式儲存的優點。

繼續觀察我們的關係代數樹，可以發現對於pv表有一個條件過濾操作。 假設我們的pv表在siteId這一列創建了索引，或者這個表在就是按照這一列的值分散儲存的。 在這種情況下，顯然我們可以做到在 SCAN 的時候直接找到對應 siteId所在的區域， 只讀取符合匹配條件的數據出來。避免讀取不相關siteId的數據可以極大地減少 IO 和提高性能。

上圖描繪了這種變換。實際上，這種變換被稱為謂詞下推(Predicate Pushdown)， 是普遍應用在各種文件儲存格式(ORC、Parquet)和各種 SQL 數據引擎(Hive、Kylin) 上的常見的查詢優化方式。

通過上面的幾步，我們成功將最初的關係代數模型化簡成為一種更為簡單高效， 實際效果卻完全一樣的關係代數。最後的結果是一種相比之前更優的執行方案， 因此也就做到了我們進行查詢優化的目的。

總結使用關係代數進行查詢優化的要點:

1、SQL 查詢可以表示成關係代數

2、關係代數作為一種樹形的結構，實質上也可以表示查詢的物理做到方案流程

3、關係代數可以進行局部的等價變換，變換前後返回的結果不變但執行的成本不同

4、通過尋找執行成本最低的關係代數表示，我們就可以將一個 SQL 查詢優化成更為高效的方案

此外，很重要的一點是: 做到關係代數的化簡和優化，依賴於數據系統的物理性質，如

1、儲存設備的特性(順序讀性能如何？隨機讀性能如何？吞吐量如何)

2、儲存內容的格式和排列(列式儲存？行式儲存？是否以某列進行分片？)

3、包含的元數據和預計算結果(是否存在索引？是否存在物化視圖？)

4、聚合和計算單元的特性(單線程？並發計算？分布式計算？特殊加速硬件？)

綜上所述，對 SQL 查詢進行優化，既要在原先邏輯算子的基礎上進行變換， 又要考慮物理做到的特性，這就是為什麼很多查詢系統存在邏輯方案和物理方案的區別的原因。 在優化時，往往存在一個從邏輯方案到物理方案進行轉變的階段。

事實上，從邏輯方案到物理方案的變換也可以劃歸為一種關係代數的優化問題。 本質上仍然是按照一定的規則將原模型當中的局部等價地轉換成一種可以物理執行的模型或算子。 一個最簡單的例子就是 JOIN 方案的選擇：

如上圖所示，JOIN 算子只描述了兩個表需要進行 JOIN 的邏輯，但是並沒有指定 JOIN 的做到方案。 右邊的 HASH JOIN 和 SORT JOIN 代表著 JOIN 操作的兩種不同的做到方案。 兩種方案在不同的場景下各有優劣，需要根據實際輸入數據的特點進行選擇。 然而盡管是從邏輯算子到物理算子的變換，其基本原理仍然是根據一定的規則進行代換而已， 與邏輯算子之間的代換並無本質差別。

另一種具有代表性的優化方案是 SORT LIMIT 的做到方案。假設一個查詢會將數據進行排序， 然後 LIMIT 取最高的幾個值。當取得的值比較少的時候，顯然可以採取一定的措施避免對全部數據進行排序 (使用堆緩沖等)。鑒於排序是一種耗費很多的操作，對其進行優化很有價值。下圖展示了一種優化方法:

上述優化證明了進行關係代數的變換時，往往不一定是一對一的關係。很多情況下可以將多個算子合併成一個算子。 實際上將一個算子進行拆分形成多個算子的場景也是有的。

SQL 查詢優化的基礎算法基於規則的優化算法

前面的例子探索了 SQL 語句進行優化的過程。 將這一過程形式化的總結出來就得到了基於規則的優化方法。

基於規則的優化方法的要點在於結構匹配和替換。 應用規則的算法一般需要先在關係代數結構上匹配一部分局部的結構， 再根據結構的特點進行變換乃至替換操作。

值得注意的是，由於變換規則要保持關係代數語義不變的大前提沒有改變， 因此被匹配的部分即使內部結構完全被替換，其跟外部的接口也要保持一致性：

1、向上輸出的數據內容和類型不變

2、下層接受輸入的數量和類型不變

基於成本的優化算法

基於規則的優化算法在實際使用中仍然面對很多問題:

1、變換規則的選擇問題：哪些規則應該被應用？以什麼順序被使用？

2、變換效果評價的問題：經過變換的查詢性能是否會變好？多種可能的方案哪個更優？

對於上述問題，不同的算法給出了不同的答案。最樸素的方法是人工定義一些規則的優先級， 每次按照固定的優先級選擇規則進行變換直到最後得到結果。這種方法往往無法得到最優的方法， 靈活性也比較差。

現階段主流的方法都是基於成本(Cost)估算的方法。也就是說，給定某一關係代數代表的執行方案， 將會對這一方案的執行成本進行估算，最終選擇估算成本最低的方案。

盡管被稱為基於成本的方法，這類算法仍然往往要結合規則進行方案的探索。也就是說， 基於成本的方法其實是通過不斷的應用規則進行變換得到新的執行方案， 然後對比方案的成本優劣進行最終選擇。

上圖展示了這一過程。其中，每一次關係代數的變換都是由於應用了不同的規則， 應用了某一規則之後還可以接下來應用其他規則，直到所有變化都被窮盡了為止。 對於每一種方案我們都可以計算得到一個可能的成本，如果可以計算出所有可能的變化， 我們就可以得到最優的方案。

顯然，要不重復地遍歷所有不同的關係代數表示本身就是一項相對棘手的算法問題， 即使做到了這樣枚舉的功能，其巨大的搜尋空間也消耗很多計算力——查詢優化本身是為了提高查詢性能， 如果優化算法本身的性能堪憂，則執行這一步驟的意義就消失了。

接下來就討論一種可以較好地解決上述問題的系統: Volcano Optimizer。

Volcano Optimizer

Volcano Optimizer 是一種基於成本的優化算法，其目的是基於一些假設和工程算法的做到， 在獲得成本較優的執行方案的同時，可以通過剪枝和緩存中間結果(動態規劃)的方法降低計算消耗。 這一章在介紹 Volcano Optimizer 的同時也將會引入很多對 Calcite 當中概念的討論。

成本最優假設

成本最優假設是理解 Volcano Optimizer 做到的要點之一。這一假設認為， 在最優的方案當中，取局部的結構來看其方案也是最優的。

成本最優假設利用了貪心算法的思想，在計算的過程中， 如果一個方案是由幾個局部區域組合而成，那麼在計算總成本時， 我們只考慮每個局部目前已知的最優方案和成本即可。

換句話說，在 Volcano 優化算法下，下圖所表示的關係代數的計算成本，大體上正比於各個部分計算成本的和。 這一假設不僅應用於單個 Operator 節點之間，也應用於子樹之間和被規則匹配的區域內外。

對於成本最優假設的另一種更直觀的描述是，如果關係代數局部的某個輸入的計算成本上升， 那麼這一子樹的整體成本趨向於上升，反之則會下降。也即是在上圖右側有

上述假設對於大部分關係代數算子都是有效的，但是並非百分之一百準確。 對於部分反例的處理方法將會在後文進一步介紹。

動態規划算法與等價集合

由於引入了成本最優假設，在優化過程中我們就可以對任意子樹目前已知的最優方案和最優成本進行緩存。 此後在計算的過程中，如果需要利用這一子樹，可以直接使用之前緩存的結果。這里應用了動態規划算法的思想。

要做到這一算法，只需要建立緩存結果到子樹雙向映射即可。在 Calcite 的做到當中，一顆子樹使用其根結點作為代表。 某一棵子樹所有可能的變換方案組成的集合被稱為等價集合(Equivalent Set)， 等價集合將會維護自身元素當中具有最優成本的方案。

等價集合在 Calcite 當中對應的是RelSet類。

對每一顆子樹都枚舉其等價集合的內容會十分耗費空間。其實，對於某一棵以 A 為根結點的子樹來說， 我們只關心 A 本身和包含 A 了的匹配內的節點。對於 A 和包含 A 的匹配之外的部分， 我們可以直接鏈接到子樹對應的等價集合當中。基於成本最優假設，在計算方案成本的時候， 我們還可以直接從這些部分的等價集合中選取最佳方案。

假設從 A 起，可以應用兩種不同的變換規則，如下圖所示:

則除了 A 本身和規則匹配到的部分，其他部分的計算就可以通過遞推的方式做到 具體來說，對應上述三種情況，會計算等價集合的元素：

1、A 節點結合 B、C 節點等價集合的最優元素和成本

2、A、C 轉化後的節點結合 B、E、F 節點對應等價集合當中的最優元素和成本

3、A、B 轉換後的節點結合 C、D、E 節點對應等價集合當中的最優元素和成本

A 所代表的子樹對應的最優方案也即是從上述三種方案中選取。

通過鏈接到子樹優化方案的技巧，我們的算法縮減了狀態空間、節省了計算量和儲存空間。 下圖展示了鏈接到子方案的大致思路。

當然，在關係代數表示中不相鄰的部分也可能具有重復的結構，Calcite 在做到的過程中考慮了這種情況， 將會在合適的時候對等價集合進行合併操作，也會出現樹中兩個不同子樹的根指向了同一個等價集合的現象。

要做到樹結構的相等計算和查詢計算也比較複雜，Calcite 採用了最簡單的遞歸將子樹的內容列印成字符串的方法進行 Hash 和比較。 因此在使用 Calcite 時要注意正確做到RelNode類的 getDigest方法。保證將節點的各種屬性包含在內， 防止不同的節點被認為等價。

在計算結束後要得到最後的執行方案，只需從根節點開始將原始關係代數當中的結構替換成最優方案當中的即可。

自底向上 vs. 自頂向下

在做到上述動態規划算法的時候存在兩種遍歷方法，一種是自底向上的動態規划算法， 一種是自頂向下的動態規划算法。

自底向上的算法最為直觀：當我們試圖計算節點 A 的最優方案時， 其子樹上每個節點對應的等價集合和最優方案都已經計算完成了，我們只需要在 A 節點上不斷尋找可以應用的規則，並利用已經計算好的子樹成本計算出母樹的成本，就可以得到最優方案。 事實上，包括 SQL Server 在內的一些成熟的數據庫系統都採用這種方法。

然而這種方案存在一些難以解決的問題:

1、不方便應用剪枝技巧，在查詢中可能會遇到在父親節點的某一種方案成本很高，後續完全無需考慮的情況， 盡管如此，需要被利用的子計算都已經完成了，這部分計算因此不可避免

2、難以做到啟發式計算和限制計算層數。由於程序要不斷遞歸到最後才能得到比較好的方案， 因此即使計算量比較大也無法提前得到一個可行的方案並停止運行

因此，Volcano Optimizer 採取了自頂向下的計算方法，在計算開始， 每棵子樹先按照原先的樣子計算成本並作為初始結果。在不斷應用規則的過程中，如果出現一種新的結構被加入到當前的等價集合中， 且這種等價集合具有更優的成本，這時需要向上冒泡到所有依賴這一子集合的父親等價集合， 更新集合里每個元素的成本並得到新的最優成本和方案。

值得注意的是，在向上冒泡的過程中需要遍歷父親集合內的每一個方案，這是因為不同方案對於 Input 成本變化的敏感性不同，不能假設之前的最優方案仍然是最優的。

自頂向下的方法盡管解決了一些問題，但是也帶來了對關係代數節點操作十分繁瑣、 要不斷維護父子等價集合的關係等問題，做到相對比較複雜。

廣度優先搜尋與啟發式算法

如前文所述，採用自頂向下的方法之後就不需要保證子樹的等價集合先被計算出來， 因此可以使用廣度優先的順序自根節點起向下遍歷執行搜尋任務。 在 Calcite 的做到之中，對於自某一節點開始激發的匹配規則(RuleMatch)，將會先被壓入隊列(RuleQueue)之中等待執行。 這樣就比較方便限制搜尋的層數從而提前返回結果。

如同 A* 算法應用在尋路任務當中用來加速執行一樣，在引入隊列之後的 Volcano Optimizer 當中也可以使用啟發式算法——某一匹配規則及其產生的等價集合可以具備一定的 Importance。 用優先隊列就可以在使這些規則的搜尋按照重要性從高到低的順序執行。

某一匹配規則也可以將變化後的結果設定為極高優先級，從而直接勝出而不會被其他規則所取代， 另一種個方向是給結果設定 0.0 值作為優先級，此時這一分支在未來幾乎不會在被繼續探索。 這也是做到自頂向下搜尋做到剪枝的一種方法。促進算法收斂也是使用Importance的原因之一。

在這一基礎上，Calcite 做到的 Volcano Optimizer 支持如下三種算法終止條件:

1、時鐘: 使用最大迭代計數或最大物理執行時間作為限制

2、成本閾值: 當優化方案的成本低於某個閾值是結束算法(相比原始成本或固定值)

3、規則窮盡: 當無法再應用規則獲得新的關係代數結構的時候結束算法

Trait/Physical properties vector

前文提到，Volcano Optimizer 大致基於一個「成本最優假設」。 這一假設是在進行動態規劃加速計算的基礎之一。然而這一假設在一些情況下並不成立。 考慮下面的情況

如圖左邊是對兩個表進行 SORT JOIN 的關係代數。此時從 B 和 C 讀入的數據直接按照儲存順序讀取， 雖然成本很低但是是亂序的。這時就需要在 SORT JOIN 算子之中進行排序操作從而需要不少的計算量。 而系統如果利用索引進行讀取，雖然不是再是順序讀取而有性能損失， 但是可以獲得排序好的記錄。這時在 SORT JOIN 算子只需進行合併操作即可， 整體的成本由於避免了全表排序反而更優。

也就是說，雖然兩個輸入的成本都變高了，但是由於引入了新的特性，整體執行反而更快。 這種問題在 Volcano Optimizer 當中使用 Physical properties vector 來解決。

在 Calcite 當中，這個東西稱為 Trait。一個 RelNode可以聲明自己的 Trait， 人們也可以編寫規則利用輸入節點的 Trait 來優化執行。

在 Calcite 當中，具有不同 Trait 的優化方案雖然都在一個RelSet當中， 卻按照相同 Trait 一類的方法分別組織在RelSubset對象里。 在進行方案成本估算和匹配規則應用等需要查詢等價集合的情況下，不同的RelSubset會分別被處理。 這樣的設計一定程度上解決了成本最優假設失效的問題。

典型的 Trait 包括記錄是否有序、是否包含 NULL 值、字符串是否都短於某一特定值等。 利用 Trait 進行查詢優化的邏輯十分複雜也需要小心處理。下圖展示了一個簡單卻典型的 Trait 的用例: 如果一個子樹的輸出已經按照某一列被排序，則取消掉上層重復的排序算子。

其他

前文分步驟解釋了 Volcano Optimizer 的主要算法思想，在這里再結合 Calcite 的做到列舉一些值得了解的事項：

1、在最初的 Volcano Optimizer 論文中，算法存在邏輯優化和物理優化兩個步驟， 在前者中會盡量將所有邏輯算子變換和展開。這一做法在後續的 Cascades 論文以及 Calcite 的做到中並沒有體現。後兩者當中，邏輯變換的規則和物理變換的規則沒有本質的差別， 兩者會在一輪優化當中同時使用，以期待快速從邏輯表示轉換為物理執行方案。

2、在 Calcite 當中，可以覆寫RelNode的getCost方法為自行做到的算子指定成本計算的方法， 盡管 Calcite 的 Cost類包括 rows、IO、CPU等多個字段，但現階段只會比較 rows的大小。 因此需要考慮把其他方面的成本換算為行數。

3、在關係代數樹上查找匹配的結構是優化過程中最頻繁的操作。Calcite 做到的匹配方法十分簡單： 如果一個節點和某一匹配模式的根結點相互匹配，則從該節點進行一次校驗。 從實踐來看此方法性能較好。

4、Calcite 默認並不進行枚舉式的優化方案計算，而是結合啟發式算法進行有限的搜尋， 因此也不一定能返回「成本最優假設」下的最優方案。

總結

本文介紹了基於關係代數對 SQL 查詢進行優化的基本原理並結合 Calcite 項目詳細介紹了 Volcano Optimizer 的設計思路。筆者認為，Apache Calcite 提供的 SQL 解析、優化和執行層十分有價值，不單是學習數據庫相關邏輯的極好教材， 也足以應用在各種成熟的項目當中。

除了本文介紹的查詢優化算法，在查詢執行過程中還有很多其他很重要的優化方式，例如

1、Vectorized Execution 通過元素在關係代數節點之間的獲取批量化以及利用 SIMD 指令集優化提高並行性從而優化執行

2、Query Compilation 通過將優化好的執行方案通過 LLVM 等工具編譯成機器碼極大地加速了解釋速度。 實際上 Calcite 就利用了 Janino 庫來將優化後的方案編譯成 JVM Bytecode 來執行

3、利用索引信息和物化視圖來加速結果的返回

以上每種方式都十分值得研究，希望以後有機會將相關的知識總結出來與大家一起探討。