“SQL at SCALE”（出自 PingCAP 官網）是我們對 TiDB 的一個精簡概括，而我們 TiDB SQL Engine Team 正是負責這 3 個單詞中的 “SQL” 部分，其重要性可見一斑。SQL 在數據庫中的大致處理流程可以簡短概括為查詢優化和執行，這期間涉及到 SQL Parser、優化器、統計信息和執行引擎等模塊，他們就是 TiDB SQL Engine Team 目前所負責的模塊。接下來我會用簡短的篇幅向大家介紹 SQL Engine 的背景知識，以及我們在做的事情，面臨的挑戰等。
關於查詢優化
優化器是 SQL 引擎的大腦，負責查詢優化。查詢優化的主要工作概括起來很簡單：搜索可行的執行計劃，從中挑一個最好的。但要做好這兩件事卻是整個分佈式數據庫中最難的地方。
1979 年 Selinger 發佈了 “Access Path Selection in a Relational Database Management System [1]”，正式拉開了 Cost Based Optimization 的帷幕，這篇論文也被視為 CBO 優化器的聖經。在這之後陸續出現了 Starburst [2]（1988 年），Volcano Optimizer Generator [3]（1993 年）和 Cascades Framework [4]（1995 年） 等，每年數據庫三大頂會中也能看到不少查詢優化相關的論文，整個優化器領域可謂是蓬勃發展。但即使如此，優化器也仍然有很多問題未能得到很好的解決，比如：
- Guy Lohman 2014 年在 “Is Query Optimization a “Solved” Problem? [5]” 中詳細講述的 SQL 算子結果集估算的難題。簡單來說，要估算某個表需要掃多少行數據比較容易，但是要再估算更上層的 SQL 算子，比如 Join 或者 Join 之後再 Group By 的結果集有多大，這個就很難了。可以想象的是，估算誤差會隨著層數的增加而被放大，這個放大有時候是數量級的。此外還會出現負負得正的情況：明明估算錯了，但是執行計劃卻是對的，糾正估算誤差後，執行計劃反而不對了 。
- Viktor Leis 等人在 2015 年的論文 How Good Are Query Optimizers, Really? [6] 中討論了優化器的另一朵烏雲：Join Order。如果枚舉所有可行的 Join Order，光是考慮左深樹，N 個表的 Join 就可能有 N! 種執行計劃。目前大家普遍採用一種妥協的方案：當參與 Join 的表比較少時用動態規劃來確定 Join 的順序，表比較多的時候用貪心或者遺傳算法（PG 用的模擬退火）來做。但是採用什麼樣的動態規劃和搜索算法也仍然處在熱烈的研究中，而算子結果集的估算誤差又進一步讓這個問題雪上加霜，難上加難。
作為一個從頭到尾完全自己手寫的優化器，TiDB 優化器的發展歷史也算精彩：一開始我們是 Selinger 的 System R 模型，但是它的擴展性不是很好，搜索空間有限，維護成本也高，於是我們調研後，決定開發 Cascades 模型的新優化器。具體請參考：十分鐘成為Contributor 系列| 為Cascades Planner 添加優化規則 和 揭秘TiDB 新優化器：Cascades Planner 原理解析 。在開發 Cascades Planner 的同時，我們還在做著另外一件非常重要的事情，提升優化器的穩定性：
- 優化器的穩定性非常重要。去年之前我們經常遇到選錯索引，或者乾脆不選索引的問題。這個對業務的影響非常大，有時候一個慢查詢可能拖垮整個集群，很多用戶都吐槽過這個問題。後來調查研究後，我們引入了 Skyline Pruning 的剪枝優化，極大地提升了優化器選擇索引的穩定性。參考：Proposal: Support Skyline Pruning [7]。
- 優化器的穩定性非常重要。要穩定的做出好的執行計劃，統計信息非常非常關鍵。以前我們收集統計信息需要整個表都掃描一遍，掃的過程中用蓄水池算法做抽樣。小表這樣做沒啥問題，大表也這樣做就不行了：一方面擔心對正在運行的業務造成影響，另一方面這種方式也很低效。於是我們結合 TiKV 的存儲特點引入了 Fast Analyze，極大的提升了統計信息的蒐集速度，也降低了對業務負載的影響。參考：PR/10214（https://github.com/pingcap/tidb/pull/10214）。
- 優化器的穩定性非常重要。即使我們做了各種優化，解了各種 Bug，仍然會出現執行計劃不優的問題。有條件的用戶還可以改一改 SQL，那沒條件的呢？比如 SQL 是通過第三方工具自動拼接的怎麼改？為了解決這些問題，我們決定引入 SQL Plan Management（https://github.com/pingcap/tidb/projects/19），先實現了給 SQL 綁定執行計劃的功能，使得不用更改業務也能搶救 SQL 的執行計劃（pingcap/tidb/Issue/8935）；為了能夠應對更多業務場景，更加細粒度的控制優化行為，我們還豐富了 SQL Hint 集合（pingcap/tidb/Issue/12304）；為了讓 SQL 執行計劃不會變差，我們為 SQL 確定了 Plan 的 Baseline，並且再往前走一步，我們做了 Baseline 的自動演進，使得執行計劃不但不會變壞，而且只會變的越來越好。
重要的事情重複 3 遍：優化器的穩定性非常重要。
除了穩定性之外，還有性能問題：
- 如何在儘量短的時間內消耗盡量少的硬件資源找到最佳執行計劃？
- 而目前 TiDB 正在 HTAP 之路上邁出堅實步伐，如何自動識別一條 SQL 是 AP 還是 TP 查詢？
- 如何為 TP 查詢選擇合理的索引？
- 又如何為 AP 查詢做出一個高效的分佈式執行計劃？
可以預見，在這條道路上，優化器又將迎接新的困難和挑戰，不斷自我演進。
關於查詢執行
我的第一份工作從執行引擎開始，對它的感情異常深厚。執行引擎的目標是儘量利用計算資源，正確且快速的完成執行計劃所描述的計算任務。光有看起來很完美的執行計劃，卻沒有高效的執行引擎，整個 SQL 引擎也是廢的。
執行引擎也是一個熱門的研究領域。最經典的執行模型當屬 1994 年 Goetz Graefe 發表的 Volcano 迭代器模型 [8]，至今仍被廣大數據庫使用。原因很簡單：接口抽象度高，擴展性好，實現起來簡單。在數據量不大的 TP 請求中，這種模型足夠用了。不過後來大家發現，隨著數據量的上升，這玩意的執行性能很差：每完成一條數據的計算，要額外花費的很多 CPU 指令，計算效率非常低。於是有了後來的兩大優化方向：Vectorization 和 Compilation，各自的代表分別為：2005 年 Marcin Zukowski 的 ”MonetDB/X100: Hyper-Pipelining Query Execution [9]”和 2011 年 Thomas Neumann 的 “Efficiently Compiling Efficient Query Plans for Modern Hardware [10]”。
除了執行框架，如何利用 CPU 硬件特性優化各種執行算子也被廣泛的討論和研究。比如 2013 年的《Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited [11]》這篇論文詳細的探討和對比了 Hash Join 和 Merge Join 的實現和性能，2015 年的《Rethinking SIMD Vectorization for In-Memory Databases [12]》這篇論文詳細討論瞭如何利用 SIMD 指令提升 SQL 算子性能。此外，底層軟硬件技術的革新帶來更多的優化機會，比如還有一系列論文來討論如何適配 NUMA 架構，提升算子執行性能等。
作為一個從頭到尾完全自己手寫的執行引擎，TiDB 執行引擎的發展也非常豐富多彩：一開始我們使用的是傳統 Volcano 迭代器模型，後來我們和社區同學在 TiDB 2.0 版本中將其優化成了向量化模型（/pingcap/tidb/Issue/5261），得到了巨大的性能提升：TPC-H 50G, TiDB 2.0 VS 1.0 [13]。之後我們和社區同學優化了聚合算子，重構了整個聚合函數的執行框架，執行性能又取得了飛躍的發展（/pingcap/tidb/Issue/6952）。再之後，我們和社區同學優化了表達式執行框架，使得表達式執行效率得到了 10 倍的性能提升，這期間 10x Performance Improvement for Expression Evaluation Made Possible by Vectorized Execution and the Community [14] 這篇文章還佔據了 Hacker News 的首頁和 DZone Database 頭版頭條。
穩定性和易用性也非常重要。為了解決用戶 OOM 的問題，我們先後引入了內存追蹤和記錄的機制，後來乾脆讓算子落盤真正解決內存使用過多的問題，另外我們也在優化排查問題的調查工具，方便在出問題時快速定位和 workaround。
如前文所說，目前 TiDB 正在 HTAP 之路上邁出堅實的步伐。執行引擎將在新的征程上肩負著新的使命。在分佈式數據庫中，廣義上的執行引擎需要考慮更多的事情：任務如何調度？shuffle 如何優化？目前三套執行引擎（TiDB、TiKV、TiFlash）三套代碼的維護成本如何降低？這些問題都等待著我們去探索和解決，可以預見，在這條道路上，執行引擎又將迎接新的困難和挑戰，不斷自我演進。
期待你的加入
很開心，TiDB 的優化器和執行引擎是從零開始由我們純手工打造的，我們有很大的自由度來發揮自己的創造力；很緊張，上面這些列出來的種種問題我們都會遇到；很榮幸，我們能夠和業界大牛、廣大開源愛好者們一起來攻克這些難題；也很有成就感，我們能在廣大 TiDB 用戶的業務中看到這些改進為他們帶來的價值。
我們熱愛開源，相信開源能夠為我們的產品帶來巨大的收益，也願意為開源奉獻，非常期待同樣熱愛開源的你的加入。如果你：
- 熱愛和相信開源，聰明且有激情；
- 敢於挑戰上面那些難題，突破極限；
- 熟悉分佈式系統、優化器和執行引擎的實現，熟悉 CPU 硬件特性；
- 有團隊帶領經驗（加分項）。
那麼我們就加入我們吧，一起向這些難題發起挑戰，構建一個前沿、穩定的優化器和高效易用的執行引擎。
[1].https://www2.cs.duke.edu/courses/compsci516/cps216/spring03/papers/selinger-etal-1979.pdf
[2].https://people.eecs.berkeley.edu/~brewer/cs262/23-lohman88.pdf
[3].https://15721.courses.cs.cmu.edu/spring2017/papers/14-optimizer1/graefe-icde1993.pdf
[4].https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/Papers/Cascades-graefe.pdf[
5].https://wp.sigmod.org/?p=1075
[6].http://www.vldb.org/pvldb/vol9/p204-leis.pdf
[7].https://github.com/pingcap/tidb/blob/master/docs/design/2019-01-25-skyline-pruning.md
[8].https://paperhub.s3.amazonaws.com/dace52a42c07f7f8348b08dc2b186061.pdf
[9].http://cidrdb.org/cidr2005/papers/P19.pdf
[10].https://www.vldb.org/pvldb/vol4/p539-neumann.pdf
[11].http://www.vldb.org/pvldb/vol7/p85-balkesen.pdf
[12].http://www.cs.columbia.edu/~orestis/sigmod15.pdf
[13].https://github.com/pingcap/docs-cn/blob/master/v2.1-legacy/benchmark/tpch.md
[14].https://pingcap.com/blog/10x-performance-improvement-for-expression-evaluation-made-possible-by-vectorized-execution/
加入我們吧！
我們認為優秀的工程師或多或少有以下共同特質：
· A Quick Learner
· A- n Earnest Curiosity
· Faith in Open Source
· Self-driven
· Get Things Done
如果你符合以上特質，歡迎進入招聘頁面查看目前開放的工作機會：
https://www.pingcap.com/recruit-cn/join/#positions
簡歷投遞通道：[email protected]
實習生：公司的各項福利和學習資源對實習生全面開放，更重要的是實習生還未畢業就有機會接觸工業級項目，而且實習期間表現優異者將有機會獲得校招綠色通道特權。針對實習時間並不充裕的小夥伴，你可以先通過 Talent Plan 豐富基礎知識（https://university.pingcap.com/talent-plan/），也可以通過參與 TiDB 開源社區獲得更多實踐機會！
伯樂推薦：如果你身邊有符合以上要求的小夥伴，也可以找我們聊一聊，推薦成功就有機會獲得伯樂推薦獎勵。伯樂推薦郵件格式：[伯樂推薦] 候選人姓名-職位名稱-推薦人姓名-推薦人手機號。延展閱讀
延展閱讀
- 是的，我們在招人！PingCAP 2020 招聘季正式開啟
- TiDB Architecture Team：挑戰數據庫的本質難題
- 揭秘 PingCAP 年輕前沿的團隊：用戶生態
- TiDB SQL Infra Team：一起打造從計算層到存儲層的完美橋樑
- 原廠 DBA：連接技術和價值的“最後一米”
閱讀更多 PingCAP 的文章
