引言
近日，在國際資料庫領域頂級會議ACM SIGMOD 2023上，阿裡雲資料庫與浙江大學合作的一篇論文《Detecting Logic Bugs of Join Optimizations in DBMS》獲得最佳論文。
SIGMOD資料管理國際會議（Special Interest Group on Management Of Data.）是由美國計算機協會（ACM）資料管理專業委員會（SIGMOD）發起、在資料庫領域具有最高學術地位的國際性學術會議，所收錄的論文代表了行業内的最高水準。會議的目的是在全球範圍内為資料庫領域的研究者、開發者以及使用者提供一個探索最新學術思想和研究方法、交流開發技巧、工具以及經驗的平台，引導和促進資料庫學科的發展。
每年，該會議都會對在資料管理領域做出的貢獻頒發多個獎項，其中的“最佳論文獎”，用于表彰每次會議上品質最高的論文，這是中國大陸研究團隊自SIGMOD自1975年開始以來49年的曆史中，第一次獲得該會議的最佳論文獎！
阿裡雲資料庫研究的崛起
資料庫是理論研究和工程實踐結合非常強的計算機學科，是以除了相關高校外，國内資料庫廠商在資料庫研究方面也投入巨大，國産資料庫及相關技術在國際上的地位逐年攀升。以阿裡雲PolarDB為代表的中國新一代資料庫在國産化替代中的大規模應用及雲化部署資料庫方面的技術創新，在資料庫行業中備受關注。
除了依靠自身的研發力量去開展前沿技術研究，阿裡雲資料庫團隊與國内各大高校和研究機構都有深入的合作研究，特别是與以杭州為主場的浙江大學，更是合作共建了下一代資料庫實驗室。每年PolarDB資料庫研發團隊會根據業務研發過程中的技術挑戰，提煉出需要聯合攻關研究的問題并“張榜”出來，而浙江大學的師生則根據其擅長的研究領域，對感興趣的研究問題提出初步的解決思路并“揭榜”，雙方針對目标問題進行多次讨論确定大緻技術路線之後，浙江大學會派遣博士/碩士實習生進入PolarDB研發團隊實習以深入挖掘問題背景并在實際業務中對解決方案進行驗證。
對于那些值得深入研究的問題，聯合實驗室會多年延續同一個課題進行研究。該次獲獎的浙大團隊即與PolarDB資料庫團隊有着多年合作曆史。合作團隊基于該Best Paper技術開發的資料庫邏輯測試工具，落地于PolarDB核心測試系統，該工具累積檢測出50餘項資料庫邏輯錯誤，最終代碼漏洞均在上線前被修複。在此之前，雙方合作的另一項研究方向，資料庫查詢表示學習項目也落地于PolarDB資料庫的外圍服務系統，通過自動化慢查詢檢測與慢查詢分類，及時預警慢查詢并推薦合理的優化方法。該研究的結果論文也發表在SIGMOD 2022上。
2023年截至目前，阿裡雲資料庫團隊共有23篇論文被SIGMOD、VLDB、ICDE、OSDI、ASPLOS等國際頂會收錄，其中就包括了這篇最佳論文。研究範圍覆寫雲原生、智能化、HTAP、安全可信等資料庫前沿研究方向。也代表中國在資料庫國際性學術會議中已占據非常重要的席位。
而針對本次PolarDB 查詢優化器當中的漏洞探測這一傳統經典問題，阿裡雲與浙大的研究團隊創新使用Learning-Base的方法來指導在給定shcehma集合之上搜尋有效的Join Query組合，最終取得了突破性成果，這充分展現了計算機系統多領域交叉技術研究的效力。下文概述本篇論文要解決的核心問題及技術思路。
最佳論文的研究背景及動機
阿裡雲PolarDB是國内領先的雲原生資料庫系統，其自2017年釋出以來，迅速被雲上企業廣泛采用。随着PolarDB資料庫的客戶數越來越多，在其上運作的應用複雜程度的增加，使用者對于更強大、更安全的資料庫的需求也越來越迫切。是以，如何檢查資料庫漏洞和錯誤，成為保障資料庫安全、提升資料庫穩定性的關鍵之一。
在資料庫查詢執行期間，主要有兩類錯誤（bug）：一種常見的錯誤是資料庫突然崩潰停止，這種錯誤對于開發人員來說相對容易檢測，因為資料庫連接配接會突然中斷。然而，還存在一類隐藏的錯誤，即邏輯漏洞。在這種情況下，資料庫正常運作并傳回結果，但實際上并非正确的結果。
邏輯漏洞舉例
以上圖中的兩個邏輯漏洞為例，
- 圖a展現了MySQL的一個哈希連接配接錯誤，這種錯誤發生在錯誤地将零和負零視為不同值的情況下，導緻最終傳回一組空集合；
- 圖b涉及資料類型轉換和資料精度損失導緻的錯誤半連接配接：在MySQL中，當比較兩個值是否相等時，資料類型轉換和精度損失可能導緻意外的結果，進而影響查詢結果集的建構。
邏輯漏洞很難檢測，但其導緻的後果确很嚴重，是以也被視為“無聲的漏洞”，而本次Best Paper的便主要聚焦于此問題。
針對邏輯漏洞，領域内已經有一些檢測方法，例如部分查詢語義（PQS），但這些方法通常隻支援針對單表選擇查詢的檢測，在涉及多表查詢以及不同的連接配接算法和連接配接結構的情況下，仍存在大量的研究空白。而最常用的差分測試，通過在不同資料庫中執行相同操作，以驗證其一緻性，這種測試仍存在問題：假如兩個資料庫傳回相同的結果，也有可能是基于同樣錯誤的邏輯生成了一樣的結果，也即如何驗證查詢結果正确性的關鍵問題。同時，測試資料庫現在面臨的搜尋空間是非常龐大的，如何引導測試以盡可能消耗最小的資源窮盡全部測試，也是一個需要解決的問題。
核心技術思路
圍繞這兩個關鍵問題，阿裡雲與浙大聯合團隊引入了一個名為TQS（轉換查詢合成）的全新解決方案，以解決MySQL資料庫中可能出現的邏輯錯誤。
TQS架構圖
TQS包括DSG和KQE兩部分，分别為資料驅動的模式和查詢生成，與知識引導的查詢空間探索。
測試資料生成
為解決測試資料的真值生成問題，阿裡雲與浙大的聯合團隊采用了以下方法：
1、首先，根據給定的寬表，使用函數依賴（FD）将該表拆分為多個表。
DSG拆分寬表的方式
2、在測資料集中插入一些噪聲資料作為邊緣情況的樣本（圖中彩色資料），并基于資料庫的模式圖模型，随機遊走生成一系列查詢。這樣是為了覆寫邊緣測試場景。
3、建構RowID映射表，用于記錄在表拆分過程中，寬表中的行和拆分後表的行的對應關系。根據表連接配接是表拆分的逆向過程的直覺，建構基于建構RowID映射的Bitmap索引，以便從寬表中檢索到連接配接查詢的理論真值。這些真值生成後，便是檢測潛在邏輯錯誤的參照樣本。
查詢模式生成
在解決了資料生成及其有效性問題之後，接下來需要解決查詢SQL的自動化生成問題， 在既定資料集合上可生成的連接配接查詢的數量會随着表格和列的數量呈指數級增長，這顯然無法使用枚舉法一一驗證。為了：更高效地探索查詢未知空間呢， 聯合研究團隊提出了TQS的第二部分設計——KQE。
KQE 原理圖
KQE首先将模式圖進一步拓展為一個規劃疊代圖，來表示整個查詢生成空間。同時，在大量的曆史查詢圖中，KQE建構了一個基于嵌入的圖索引，以確定新生成的查詢圖盡可能地遠離其在曆史查詢中的近鄰，探索更多的未知空間。
總體來看，KQE可基于結構相似性為生成的查詢圖評分，同時也通過自适應随機遊走多樣化查詢生成，進而極大降低了對于重複查詢的機率，節省了計算資源開支。
實驗效果分析
為了驗證TQS方法的通用性，除了PolarDB之外, 研究團隊也在MySQL、MariaDB、TiDB另外三款流程的DBMS上進行了實驗。
運作了 24 小時後，TQS 成功找到了 115 個漏洞：MySQL 中 31 個、MariaDB 中 30 個、TiDB 中 31 個、PolarDB 中 23 個。通過最小化測試樣例，我們進一步将它們分為20種類型。
實驗檢出的漏洞分類詳表
目前所有這些被檢測到的漏洞都送出給了相應資料庫社群，并得到了他們積極的回報。這些漏洞的危機程度被資料庫社群判定為首要危急或嚴重級别，一些漏洞已經修複在了其資料庫最新版本中。
具體來說，MySQL 8.0.28的錯誤主要集中在Semi-join和Sub-query的執行過程中，其中，幾個錯誤被評定為首要危急，即最緊急的錯誤，這些錯誤已經在MySQL 8.0.30版本中得到修複，并提供了相應的修複說明。另外，針對PolarDB，我們則直接送出錯誤報告，相關錯誤已經被修複。
總的來說，相比于其它方法，TQS在多項名額上取得了更優的效果，較原有方法實作高達100倍的性能提升，各元件的有效性也通過控制變量實驗得到了檢驗。
後記
依托于阿裡巴巴-浙江大學前沿技術聯合研究中心這一研究載體，阿裡雲瑤池資料庫團隊與浙江大學師生，完成了從實踐中提出問題、由校企聯合攻關、成果落地産業界的科研新探索。論文一作、浙江大學博士唐秀正是在阿裡雲PolarDB進行研究型實習期間，與聯合團隊一起完成的課題攻堅。而這篇Best Paper隻是一個起點，阿裡雲瑤池資料庫團隊将繼續與各大高校合作探索資料庫技術的邊界，為客戶提供安全，穩定，高性能，低成本的資料庫服務。