我一直認為，查詢優化器(Query Optimizer，后面簡稱優化器)一直是數據庫領域 Top 級別的 hardcore 技術，自己也一直嘗試去深入理解，但每每看到 TiDB 代碼里面那一大坨 plan 的代碼，我就望而生畏了，就像是『可遠觀而不可褻玩焉』。但雖然很難理解，還是能通過方式去理解優化器的，一個最直觀的做法就是生成不同的 Query 去驗證優化器的效果，實際在 PingCAP 內部，我們也是通過 Fuzz， A/B testing 等技術，來驗證優化器是否出現性能問題這些。

但無論怎樣，優化器的驗證和測試工作是一件非常難的事情，畢竟對于一條 Query，數據庫可能會生成非常多的查詢計劃(plan)，我們當然可以通過窮舉的方式找到最優的一條 plan，但實際中，我們只能在有限的時間內找到一個比較優的 plan。那么我們如何能確定優化器找到的是一條比較好的 plan 呢？自然需要有一些評價標準，最近看了幾篇 Paper，剛好在這個上面做了研究，也對我們后續測試的改良提供了一些方向吧。

OptMark: A Toolkit for Benchmarking Query Optimizers

首先是 OptMark: A Toolkit for Benchmarking Query Optimizers 這篇 Paper，里面提到了驗證優化器的兩個指標 - Effectiveness 和 Efficiency。對于 Effectiveness 來說，它主要是衡量優化器對于某條 Query 生成的 plan 的質量，而 Efficiency 則是衡量生成的 plan 的資源消耗。

Effectiveness 主要有兩個指標，一個是 Performance Factor，一個則是 Optimality Frequency，Performance Factor 計算公式如下：

對于任何 query q 以及優化器 Od 來說，PF 衡量的是在搜索空間里面的 plans，比優化器選擇的 plan 要差的比例。Od(q) 是優化器對于 q 生成的 plan，Pd(q) 則是所有可能被執行的 plan，r(D, p) 則是 plan p 執行的時間，而 r(D, Od(q)) 則是優化器選擇的 plan 執行的時間。有了 PF，我們就能得到 Optimality Frequency，如果 PF = 1，就表明優化器找到了一條相對不錯的 plan。

當然，實際中我們很難將搜索空間全部遍歷出來，所以通常我們都只是會找足夠多的 plan，Paper 里面提到了 Sample Size 的概念，也就是會有一個信心指數的計算，直白的說，就是如果我們需要有 x% 的信心，以及 y% 的精確度來計算 PF，那么就需要生成 n 個 plans 這種，具體的計算方法可以參考論文 2.1.2 章節。

要驗證 Effectiveness，論文使用了如下方式：

對于一條 Query，對里面的 Join 隨機進行重新排序

對于 join 的兩個 table，如果沒有指定 join 方式，則使用 cross join，否則則隨機從 joinType() 里面選擇一個 physical join，譬如 hash，index merge 等。

對任何 table，隨機選擇一種掃描方式，譬如使用某個 index，或者全表掃

生成一條 plan，去執行。然后重復執行上述操作，直到滿足我們之前說的信心指數。

對于 Efficiency 來說，論文并沒有用傳統的衡量執行時間的方式，而是選用了 4 個指標：#LP - 枚舉的 logical plan個數

#JO - 枚舉的 join 順序個數

#PP - 總的有開銷的 physical plan 的個數

#PJ - 總的有開銷的 physical join plan 的個數

論文里面將這些指標直接加到了 MySQL 和 PG 的代碼里面進行統計，這個也就是開源的好處了，能直接改代碼，后面也可以試試 TiDB。

總的來說，OptMark 這篇 Paper 從 Effectiveness 和 Efficiency 兩個維度來告訴我們如何測試一個數據庫的查詢計劃，而且也比較容易實施。不過，在測試 Effectiveness 生成 plan 的時候，其實我有點懷疑數據庫到底會不會按照這條 plan 去執行。

Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer

在前面那篇 Paper 里面，OptMark 使用的是一種 random join ordering 的方式來對一條 query 進行 join 的順序變換，然后對 join 的 table 選擇不同的 join 算法，以及對每個 table 使用不同的查詢方式，那么有沒有其他的辦法來對一條 Query 生成執行計劃，并且讓數據庫執行呢？

然后剛好看到了一篇不錯的 Paper，Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer，其中提到了一個很不錯的方式，就是通過 MEMO 這種數據結構，來建立好數字和 plan 的對應關系，我們只要給出一個數字，就能執行對應的 plan。

首先，對于一條 Query，我們可以有一個非常簡單的 plan，并且用這個 plan 來生成 MEMO 結構

當生成 MEMO 之后，我們就可以對 logical operators 進行變換，一個轉換規則可以是：在同一個 group 里面的 logical operator，譬如 join(A, B) -> join(B, A)

在同一個 group 里面的 physical operator，譬如 join -> hash join

一組能連接多個 sub plan 的 logical operators，譬如 join(A, join(B, C)) -> join(join(A, B), C)

然后做完轉換之后，MEMO 表現就更豐富了，如下：

最后一項預備工作，就是抽出所有的 physical operators，并且具現化這個 operators 和它們的可能 children 的連接，如下：

當做完了如上三個步驟，就可以通過 MEMO 這個數據結構算出來總的 Query Plans，算法可以直接看 Paper 3.2 章節，其實就是自下而上遍歷每個可能 plan 的個數并且匯總。當我們得到了總的 plan 個數，就可以通過 unranking 算法知道某個 position 上面對應的 plan，具體的 unranking 算法可以參考 3.2。當構造了這些信息之后，我們就可以在 query 里面直接指定使用某個 plan 了，如下：

其實這個方式非常的巧妙，現在 TiDB 是不支持的，沒準可以試試支持下，應該也不困難。

Testing the Accuracy of Query Optimizers

除了上面兩篇 Paper，還看了一篇，Testing the Accuracy of Query Optimizers，講的是如何測試優化器的精確度，其實就是一個 estimate time 和實際 execution time 的 pair 對比吧，會計算一個相關性 score，類似如下：

可以看到，上面 4 個 plan，P1 和 P2 其實明顯會比 P3 和 P4 要好。

然后 Paper 的作者做了一個 TAQO 系統，如下：

流程比較通俗易懂，不多做解釋了，反正可以結合上面第一篇 paper，來驗證優化器的效果吧。

總結

上面列了幾篇，我們當然是想應用到 TiDB 來驗證優化器的效果的，當然另外，我們也可以通過讓優化器強制使用不用的 plan，來看優化器會不會有 bug，譬如對于第二篇 paper，沒準我們使用 plan 8 得到的值跟 plan 9 不一樣，這事情就有意思了。

總的來說，優化器這個方向是一個非常 hardcore 的東西，不光是測試上面，還包括如何實現一個高效的優化器上面，我們需要非常多的技術儲備，如果你對這方面感興趣，歡迎聯系我 tl@pingcap.com。