引言

近日，在國際數(shù)據(jù)庫領(lǐng)域頂級會議ACM SIGMOD 2023上，阿里云數(shù)據(jù)庫與浙江大學合作的一篇論文《Detecting Logic Bugs of Join Optimizations in DBMS》獲得最佳論文。

SIGMOD數(shù)據(jù)管理國際會議（Special Interest Group on Management Of Data.）是由美國計算機協(xié)會（ACM）數(shù)據(jù)管理專業(yè)委員會（SIGMOD）發(fā)起、在數(shù)據(jù)庫領(lǐng)域具有最高學術(shù)地位的國際性學術(shù)會議，所收錄的論文代表了行業(yè)內(nèi)的最高水平。會議的目的是在全球范圍內(nèi)為數(shù)據(jù)庫領(lǐng)域的研究者、開發(fā)者以及用戶提供一個探索最新學術(shù)思想和研究方法、交流開發(fā)技巧、工具以及經(jīng)驗的平臺，引導和促進數(shù)據(jù)庫學科的發(fā)展。

每年，該會議都會對在數(shù)據(jù)管理領(lǐng)域做出的貢獻頒發(fā)多個獎項，其中的“最佳論文獎”，用于表彰每次會議上質(zhì)量最高的論文，這是中國大陸研究團隊自SIGMOD自1975年開始以來49年的歷史中，第一次獲得該會議的最佳論文獎！

阿里云數(shù)據(jù)庫研究的崛起

數(shù)據(jù)庫是理論研究和工程實踐結(jié)合非常強的計算機學科，因此除了相關(guān)高校外，國內(nèi)數(shù)據(jù)庫廠商在數(shù)據(jù)庫研究方面也投入巨大，國產(chǎn)數(shù)據(jù)庫及相關(guān)技術(shù)在國際上的地位逐年攀升。以阿里云PolarDB為代表的中國新一代數(shù)據(jù)庫在國產(chǎn)化替代中的大規(guī)模應用及云化部署數(shù)據(jù)庫方面的技術(shù)創(chuàng)新，在數(shù)據(jù)庫行業(yè)中備受關(guān)注。

除了依靠自身的研發(fā)力量去開展前沿技術(shù)研究，阿里云數(shù)據(jù)庫團隊與國內(nèi)各大高校和研究機構(gòu)都有深入的合作研究，特別是與以杭州為主場的浙江大學，更是合作共建了下一代數(shù)據(jù)庫實驗室。每年P(guān)olarDB數(shù)據(jù)庫研發(fā)團隊會根據(jù)業(yè)務研發(fā)過程中的技術(shù)挑戰(zhàn)，提煉出需要聯(lián)合攻關(guān)研究的問題并“張榜”出來，而浙江大學的師生則根據(jù)其擅長的研究領(lǐng)域，對感興趣的研究問題提出初步的解決思路并“揭榜”，雙方針對目標問題進行多次討論確定大致技術(shù)路線之后，浙江大學會派遣博士/碩士實習生進入PolarDB研發(fā)團隊實習以深入挖掘問題背景并在實際業(yè)務中對解決方案進行驗證。對于那些值得深入研究的問題，聯(lián)合實驗室會多年延續(xù)同一個課題進行研究。該次獲獎的浙大團隊即與PolarDB數(shù)據(jù)庫團隊有著多年合作歷史。合作團隊基于該Best Paper技術(shù)開發(fā)的數(shù)據(jù)庫邏輯測試工具，落地于PolarDB內(nèi)核測試系統(tǒng)，該工具累積檢測出50余項數(shù)據(jù)庫邏輯錯誤，最終代碼漏洞均在上線前被修復。在此之前，雙方合作的另一項研究方向，數(shù)據(jù)庫查詢表示學習項目也落地于PolarDB數(shù)據(jù)庫的外圍服務系統(tǒng)，通過自動化慢查詢檢測與慢查詢分類，及時預警慢查詢并推薦合理的優(yōu)化方法。該研究的結(jié)果論文也發(fā)表在SIGMOD 2022上。

?2023年截至目前，阿里云數(shù)據(jù)庫團隊共有23篇論文被SIGMOD、VLDB、ICDE、OSDI、ASPLOS等國際頂會收錄，其中就包括了這篇最佳論文。研究范圍覆蓋云原生、智能化、HTAP、安全可信等數(shù)據(jù)庫前沿研究方向。也代表中國在數(shù)據(jù)庫國際性學術(shù)會議中已占據(jù)非常重要的席位。

而針對本次PolarDB 查詢優(yōu)化器當中的漏洞探測這一傳統(tǒng)經(jīng)典問題，阿里云與浙大的研究團隊創(chuàng)新使用Learning-Base的方法來指導在給定shcehma集合之上搜尋有效的Join Query組合，最終取得了突破性成果，這充分展現(xiàn)了計算機系統(tǒng)多領(lǐng)域交叉技術(shù)研究的效力。下文概述本篇論文要解決的核心問題及技術(shù)思路。

最佳論文的研究背景及動機

阿里云PolarDB是國內(nèi)領(lǐng)先的云原生數(shù)據(jù)庫系統(tǒng)，其自2017年發(fā)布以來，迅速被云上企業(yè)廣泛采用。隨著PolarDB數(shù)據(jù)庫的客戶數(shù)越來越多，在其上運行的應用復雜程度的增加，用戶對于更強大、更安全的數(shù)據(jù)庫的需求也越來越迫切。因此，如何檢查數(shù)據(jù)庫漏洞和錯誤，成為保障數(shù)據(jù)庫安全、提升數(shù)據(jù)庫穩(wěn)定性的關(guān)鍵之一。
在數(shù)據(jù)庫查詢執(zhí)行期間，主要有兩類錯誤（bug）：一種常見的錯誤是數(shù)據(jù)庫突然崩潰停止，這種錯誤對于開發(fā)人員來說相對容易檢測，因為數(shù)據(jù)庫連接會突然中斷。然而，還存在一類隱藏的錯誤，即邏輯漏洞。在這種情況下，數(shù)據(jù)庫正常運行并返回結(jié)果，但實際上并非正確的結(jié)果。

以上圖中的兩個邏輯漏洞為例，

• 圖a展現(xiàn)了MySQL的一個哈希連接錯誤，這種錯誤發(fā)生在錯誤地將零和負零視為不同值的情況下，導致最終返回一組空集合；

• 圖b涉及數(shù)據(jù)類型轉(zhuǎn)換和數(shù)據(jù)精度損失導致的錯誤半連接：在MySQL中，當比較兩個值是否相等時，數(shù)據(jù)類型轉(zhuǎn)換和精度損失可能導致意外的結(jié)果，從而影響查詢結(jié)果集的構(gòu)建。

邏輯漏洞很難檢測，但其導致的后果確很嚴重，因此也被視為“無聲的漏洞”，而本次Best Paper的便主要聚焦于此問題。

針對邏輯漏洞，領(lǐng)域內(nèi)已經(jīng)有一些檢測方法，例如部分查詢語義（PQS），但這些方法通常只支持針對單表選擇查詢的檢測，在涉及多表查詢以及不同的連接算法和連接結(jié)構(gòu)的情況下，仍存在大量的研究空白。而最常用的差分測試，通過在不同數(shù)據(jù)庫中執(zhí)行相同操作，以驗證其一致性，這種測試仍存在問題：假如兩個數(shù)據(jù)庫返回相同的結(jié)果，也有可能是基于同樣錯誤的邏輯生成了一樣的結(jié)果，也即如何驗證查詢結(jié)果正確性的關(guān)鍵問題。同時，測試數(shù)據(jù)庫現(xiàn)在面臨的搜索空間是非常龐大的，如何引導測試以盡可能消耗最小的資源窮盡全部測試，也是一個需要解決的問題。

核心技術(shù)思路

圍繞這兩個關(guān)鍵問題，阿里云與浙大聯(lián)合團隊引入了一個名為TQS（轉(zhuǎn)換查詢合成）的全新解決方案，以解決MySQL數(shù)據(jù)庫中可能出現(xiàn)的邏輯錯誤。

TQS包括DSG和KQE兩部分，分別為數(shù)據(jù)驅(qū)動的模式和查詢生成，與知識引導的查詢空間探索。

測試數(shù)據(jù)生成

為解決測試數(shù)據(jù)的真值生成問題，阿里云與浙大的聯(lián)合團隊采用了以下方法：

1、首先，根據(jù)給定的寬表，使用函數(shù)依賴（FD）將該表拆分為多個表。

2、在測數(shù)據(jù)集中插入一些噪聲數(shù)據(jù)作為邊緣情況的樣本（圖中彩色數(shù)據(jù)），并基于數(shù)據(jù)庫的模式圖模型，隨機游走生成一系列查詢。這樣是為了覆蓋邊緣測試場景。

3、構(gòu)建RowID映射表，用于記錄在表拆分過程中，寬表中的行和拆分后表的行的對應關(guān)系。根據(jù)表連接是表拆分的逆向過程的直覺，構(gòu)建基于構(gòu)建RowID映射的Bitmap索引，以便從寬表中檢索到連接查詢的理論真值。這些真值生成后，便是檢測潛在邏輯錯誤的參照樣本。

查詢模式生成

在解決了數(shù)據(jù)生成及其有效性問題之后，接下來需要解決查詢SQL的自動化生成問題， 在既定數(shù)據(jù)集合上可生成的連接查詢的數(shù)量會隨著表格和列的數(shù)量呈指數(shù)級增長，這顯然無法使用枚舉法一一驗證。為了：更高效地探索查詢未知空間呢， 聯(lián)合研究團隊提出了TQS的第二部分設(shè)計——KQE。

KQE首先將模式圖進一步拓展為一個規(guī)劃迭代圖，來表示整個查詢生成空間。同時，在大量的歷史查詢圖中，KQE構(gòu)建了一個基于嵌入的圖索引，以確保新生成的查詢圖盡可能地遠離其在歷史查詢中的近鄰，探索更多的未知空間。

總體來看，KQE可基于結(jié)構(gòu)相似性為生成的查詢圖評分，同時也通過自適應隨機游走多樣化查詢生成，從而極大降低了對于重復查詢的概率，節(jié)省了計算資源開支。

實驗效果分析

為了驗證TQS方法的通用性，除了PolarDB之外, 研究團隊也在MySQL、MariaDB、TiDB另外三款流程的DBMS上進行了實驗。
運行了 24 小時后，TQS 成功找到了 115 個漏洞：MySQL 中 31 個、MariaDB 中 30?個、TiDB 中 31 個、PolarDB 中 23 個。通過最小化測試樣例，我們進一步將它們分為20種類型。

目前所有這些被檢測到的漏洞都提交給了相應數(shù)據(jù)庫社區(qū)，并得到了他們積極的反饋。這些漏洞的危機程度被數(shù)據(jù)庫社區(qū)判定為首要危急或嚴重級別，一些漏洞已經(jīng)修復在了其數(shù)據(jù)庫最新版本中。

具體來說，MySQL 8.0.28的錯誤主要集中在Semi-join和Sub-query的執(zhí)行過程中，其中，幾個錯誤被評定為首要危急，即最緊急的錯誤，這些錯誤已經(jīng)在MySQL 8.0.30版本中得到修復，并提供了相應的修復說明。另外，針對PolarDB，我們則直接提交錯誤報告，相關(guān)錯誤已經(jīng)被修復。

總的來說，相比于其它方法，TQS在多項指標上取得了更優(yōu)的效果，較原有方法實現(xiàn)高達100倍的性能提升，各組件的有效性也通過控制變量實驗得到了檢驗。

后記

依托于阿里巴巴-浙江大學前沿技術(shù)聯(lián)合研究中心這一研究載體，阿里云瑤池數(shù)據(jù)庫團隊與浙江大學師生，完成了從實踐中提出問題、由校企聯(lián)合攻關(guān)、成果落地產(chǎn)業(yè)界的科研新探索。論文一作、浙江大學博士唐秀正是在阿里云PolarDB進行研究型實習期間，與聯(lián)合團隊一起完成的課題攻堅。而這篇Best Paper只是一個起點，阿里云瑤池數(shù)據(jù)庫團隊將繼續(xù)與各大高校合作探索數(shù)據(jù)庫技術(shù)的邊界，為客戶提供安全，穩(wěn)定，高性能，低成本的數(shù)據(jù)庫服務。

論文解讀可觀看視頻