面向OLAP數(shù)據(jù)庫(kù)查詢處理功能的模糊測(cè)試工具

項(xiàng)兆坤 陳婷 蘇仟 張蓉

摘要：查詢處理是現(xiàn)代關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）中最重要的功能之一，主要包括查詢優(yōu)化和查詢 執(zhí)行.然而查詢處理的復(fù)雜性導(dǎo)致了測(cè)試的高成本，阻礙了開發(fā)過(guò)程中的快速迭代，并可能在生產(chǎn)環(huán)境中 導(dǎo)致嚴(yán)重錯(cuò)誤.為了更好地服務(wù)于DBMS查詢處理功能的評(píng)測(cè)，采用模糊測(cè)試的方法生成基于主鍵約束的 隨機(jī)數(shù)據(jù)和完全有效的復(fù)雜分析型查詢;構(gòu)建約束優(yōu)化，對(duì)查詢中算子的精確基數(shù)進(jìn)行高效計(jì)算，從而獲 得查詢的正確結(jié)果;最后實(shí)現(xiàn)了完整的工具.通過(guò)對(duì)TiDB的不同版本進(jìn)行了小規(guī)模的測(cè)試，結(jié)果表明可 以有效地檢測(cè)出TiDB不同版本的一些Bug.

關(guān)鍵詞：分析型數(shù)據(jù)庫(kù);查詢處理;查詢執(zhí)行;查詢優(yōu)化器;模糊測(cè)試

中圖分類號(hào)：TP392?????? 文獻(xiàn)標(biāo)志碼：A?????? DOI： 10.3969/j.issn.1000-5641.2021.05.007

A fuzzer for query processing functionality of OLAP databases

XIANG Zhaokun1， CHEN Ting1， SU Qian2， ZHANG Rong1

（1. School of Data Science and Engineering， East China Normal University， Shanghai 200062， China;

2. China Industrial Control Systems Cyber Emergency Response Team， Beijmg 100040， China）

Abstract： Query processing， including optimization and execution， is one of the most critical functionalities of modern relational database management systems （DBMS）. The complexity of query processing functionalities， however， leads to high testing costs. It hinders rapid iterations during the development process and can lead to severe errors when deployed in production environments. In this paper， we propose a tool to better serve the testing and evaluation of DBMS query processing functionalities; the tool uses a fuzzing approach to generate random data that is highly associated with primary keys and generates valid complex analytical queries. The tool constructs constrained optimization problems to efficiently compute the exact cardinalities of operators in queries and furnish the results. We launched small-scale testing of our method on different versions of TiDB and demonstrated that the tool can effectively detect bugs in different versions of TiDB.

Keywords： OLAP database; query processing; query execution; exact cardinality; fuzzing

0引 言

分析型數(shù)據(jù)庫(kù)管理系統(tǒng)（Database Management System， DBMS）主要用于處理復(fù)雜的查詢，艮口 OLAP負(fù)載，被廣泛應(yīng)用于金融科技、商業(yè)智能等領(lǐng)域，查詢處理[1]是分析型數(shù)據(jù)庫(kù)中最重要的功能

收稿日期：2021-08-04

基金項(xiàng)目：國(guó)家自然科學(xué)基金（62072179）; 2020年關(guān)鍵軟件適配驗(yàn)證中心項(xiàng)目

通信作者：張蓉，女，教授，博士生導(dǎo)師，研究方向?yàn)榉植际綌?shù)據(jù)管理.E-mail： rzhang@dase.ecnu.edu.cn

之一.這些分析型SQL語(yǔ)句大多包含多表連接、聚集運(yùn)算等操作，幫助分析師完成復(fù)雜的分析處理任務(wù).

對(duì)于分析型數(shù)據(jù)庫(kù)來(lái)說(shuō)，一個(gè)復(fù)雜的SQL語(yǔ)句查詢要經(jīng)歷查詢解析（Parser）、查詢優(yōu)化（Query Optimization）和查詢執(zhí)行（Query Execution）.在查詢解析階段，解析器會(huì)對(duì)SQL語(yǔ)句進(jìn)行語(yǔ)法檢查 （Syntactic Check）和語(yǔ)義檢查（Semantic Check），如果SQL語(yǔ)句有語(yǔ)法或者語(yǔ)義錯(cuò)誤，DBMS會(huì)直接 返回錯(cuò)誤信息，不會(huì)進(jìn)入查詢優(yōu)化和執(zhí)行階段.通過(guò)查詢解析階段，SQL語(yǔ)句會(huì)被轉(zhuǎn)換為初始的邏輯 查詢計(jì)劃，接著會(huì)經(jīng)過(guò)查詢優(yōu)化將初始的邏輯查詢計(jì)劃優(yōu)化為代價(jià)較低的等價(jià)查詢執(zhí)行計(jì)劃.然后將 該執(zhí)行計(jì)劃交給查詢執(zhí)行器去執(zhí)行，最終得到SQL的執(zhí)行結(jié)果.

查詢優(yōu)化問(wèn)題已經(jīng)被研究了 40余年，是計(jì)算機(jī)領(lǐng)域的NP難問(wèn)題之一[2].查詢優(yōu)化器目的是選出 一個(gè)比較好的查詢執(zhí)行計(jì)劃交給執(zhí)行器去執(zhí)行，幾乎所有的現(xiàn)代數(shù)據(jù)庫(kù)系統(tǒng)使用的都是基于成本的 優(yōu)化器（Cost-Based Optimizer），使用枚舉算法（Enumeration Algorithm）在計(jì)劃搜索空間中搜索執(zhí)行 計(jì)劃，同時(shí)使用代價(jià)模型（Cost Model）預(yù)估執(zhí)行計(jì)劃的代價(jià)，最終選擇代價(jià)最低的執(zhí)行計(jì)劃[3].在代價(jià) 模型中最重要的因素是查詢中算子的中間結(jié)果集大小，簡(jiǎn)稱基數(shù)（Cardinality），基數(shù)預(yù)估的誤差是造 成優(yōu)化器無(wú)法選出合適的執(zhí)行計(jì)劃的因素之一[4]，所以使用某種方法快速獲得精確的基數(shù)能使查詢優(yōu) 化器的效果獲得很大的提升.

模糊測(cè)試（Fuzzing）是一種軟件測(cè)試技術(shù)，被廣泛運(yùn)用于檢查軟件系統(tǒng)的漏洞模糊器（Fuzzer） 是指實(shí)施模糊測(cè)試的工具.模糊測(cè)試分為基于突變的模糊測(cè)試和基于生成的模糊測(cè)試.基于突變的模 糊測(cè)試依賴于對(duì)測(cè)試輸入的變異來(lái)構(gòu)造新的測(cè)試輸入，基于生成的模糊測(cè)試依賴于一個(gè)給定的輸入 模型來(lái)生成測(cè)試輸入[6].

數(shù)據(jù)庫(kù)系統(tǒng)在快速迭代開發(fā)階段進(jìn)行充分的測(cè)試是很有必要的，能夠提前發(fā)現(xiàn)問(wèn)題，避免上線后 產(chǎn)生錯(cuò)誤.針對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的模糊測(cè)試工具不同于通用的模糊測(cè)試工具，由于數(shù)據(jù)庫(kù)系統(tǒng)的輸入為高 度結(jié)構(gòu)化的SQL語(yǔ)句，有著嚴(yán)格的語(yǔ)法格式和語(yǔ)義格式，不同的SQL關(guān)鍵字的組合可以抵達(dá)不同的 代碼邏輯，所以需要設(shè)計(jì)特別的測(cè)試工具.服務(wù)于DBMS的基于生成的模糊器根據(jù)預(yù)先設(shè)計(jì)的 SQL生成模型生成SQL，而服務(wù)于DBMS的基于突變的模糊器主要對(duì)SQL語(yǔ)句進(jìn)行突變來(lái)產(chǎn)生新 的SQL.目前已經(jīng)有很多針對(duì)數(shù)據(jù)庫(kù)功能的模糊測(cè)試工具[7-12]和數(shù)據(jù)庫(kù)性能回歸診斷的模糊測(cè)試 工具[13]. —些傳統(tǒng)的模糊器[14-15]以及負(fù)載生成工具[16]也可以生成復(fù)雜度高的SQL語(yǔ)句，它們有的生成 的SQL語(yǔ)句不能保證語(yǔ)法正確性，有的雖然保證了語(yǔ)法正確性，但是無(wú)法保證語(yǔ)義正確性，這些 SQL語(yǔ)句無(wú)法通過(guò)數(shù)據(jù)庫(kù)查詢處理的解析器，不能抵達(dá)更深的代碼邏輯.RAGS[7]保證了語(yǔ)義的正確 性但是有50%左右的SQL執(zhí)行為NULL，這些SQL也不能很好地對(duì)數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行測(cè)試.總體來(lái)說(shuō)， 現(xiàn)有的一些模糊測(cè)試工具要么無(wú)法保證負(fù)載語(yǔ)法正確性和語(yǔ)義正確性[14-15，17-18]，要么大量的負(fù)載執(zhí)行 結(jié)果為NULL[7]，而且一些工具[8，11]需要去使用權(quán)威數(shù)據(jù)庫(kù)作為結(jié)果參照.另外，當(dāng)前的一些針對(duì)查詢 優(yōu)化器的測(cè)試工具[19-20]都無(wú)法保證測(cè)試方法能觸及優(yōu)化器的核心——基數(shù)，已有的一些精確基數(shù)獲取 的工作[21-23]都是通過(guò)使用數(shù)據(jù)庫(kù)執(zhí)行額外的負(fù)載獲取查詢中所有算子的精確基數(shù)，會(huì)造成很大的開銷.

針對(duì)DBMS查詢處理功能的模糊測(cè)試工具應(yīng)該提供測(cè)試數(shù)據(jù)生成器、測(cè)試負(fù)載生成器以及結(jié)果 驗(yàn)證器.那么，如何更好地生成測(cè)試所需要數(shù)據(jù)，如何生成更有效的負(fù)載以檢測(cè)數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)核代碼 邏輯，以及如何高效地進(jìn)行結(jié)果驗(yàn)證，是開發(fā)面向數(shù)據(jù)庫(kù)系統(tǒng)的模糊測(cè)試工具所要著重考慮的難點(diǎn)問(wèn) 題.本文提出一款面向OLAP數(shù)據(jù)庫(kù)查詢處理功能的模糊測(cè)試工具，采用基于主鍵的關(guān)聯(lián)數(shù)據(jù)生成、 避免NULL值的負(fù)載生成、構(gòu)建約束優(yōu)化問(wèn)題進(jìn)行算子基數(shù)及查詢結(jié)果計(jì)算，實(shí)現(xiàn)更加有效的分析型 數(shù)據(jù)庫(kù)查詢處理功能的正確性測(cè)試，可服務(wù)于面向金融應(yīng)用的數(shù)據(jù)庫(kù)系統(tǒng)的評(píng)測(cè).

1相關(guān)工作

模糊測(cè)試是生成輸入到軟件系統(tǒng)以發(fā)現(xiàn)漏洞，是一種傳統(tǒng)的漏洞發(fā)現(xiàn)方法.在數(shù)據(jù)庫(kù)系統(tǒng)的評(píng)測(cè)中，生成數(shù)據(jù)、生成負(fù)載都是服務(wù)于DBMS的模糊測(cè)試工具要考慮的重要環(huán)節(jié).

在傳統(tǒng)的負(fù)載生成工具中，微軟開發(fā)的RAGS[7]是比較有代表性的工作.它根據(jù)已有的數(shù)據(jù)庫(kù) Schema信息，參照標(biāo)準(zhǔn)的SQL語(yǔ)法隨機(jī)生成大量語(yǔ)法正確的SQL語(yǔ)句，將這些SQL在不同的數(shù)據(jù) 庫(kù)上執(zhí)行并利用對(duì)比庫(kù)進(jìn)行結(jié)果驗(yàn)證，即使用差異測(cè)試的方法來(lái)測(cè)試SQL Server版本迭代中出現(xiàn)的 Bug.但是RGAS生成的負(fù)載大約有50%的查詢的執(zhí)行結(jié)果為空，造成了測(cè)試資源很大的浪費(fèi).同時(shí) RGAS使用的差異測(cè)試方法需要數(shù)據(jù)和負(fù)載在不同的數(shù)據(jù)庫(kù)上去執(zhí)行，不同數(shù)據(jù)庫(kù)的語(yǔ)法可能還不 兼容，是一種耗時(shí)耗力的方法.

文獻(xiàn)[16]中介紹了微軟提出的一個(gè)基于突變的負(fù)載生成工具，主要通過(guò)增減關(guān)鍵字來(lái)對(duì)已有的 SQL語(yǔ)句進(jìn)行突變，能保證語(yǔ)法的正確性，但是無(wú)法保證語(yǔ)義的正確性.

目前，有一些通用模糊測(cè)試工具支持生成結(jié)構(gòu)化的SQL.但文獻(xiàn)[14]提出的工具生成的SQL 大多數(shù)語(yǔ)法不正確，AFL（American Fuzzy Lop）|15]生成的SQL語(yǔ)句中只有30%語(yǔ)法正確，其中語(yǔ)義正 確的SQL比例不到5%.這些通用型模糊測(cè)試工具無(wú)法很好地對(duì)數(shù)據(jù)庫(kù)進(jìn)行測(cè)試.故后續(xù)出現(xiàn)了專門 針對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的模糊測(cè)試工具，比如SQLSmith、SQLFuzz、SQLancer、SQUIRREL、SparkFuzz、 MutaSQL 等.

SQLSmith[8]是基于生成的模糊測(cè)試工具，基于給定的數(shù)據(jù)庫(kù)模式（Schema）隨機(jī)生成大量語(yǔ)法正 確的SQL，用于發(fā)現(xiàn)DBMS的系統(tǒng)崩潰問(wèn)題（Crash），但是它無(wú)法保證生成SQL的語(yǔ)義正確，同時(shí)也 不包含查詢結(jié)果的正確性驗(yàn)證模塊.SQLFuzz[13]是數(shù)據(jù)庫(kù)系統(tǒng)性能回歸測(cè)試工具APOLLO中的一部 分，通過(guò)隨機(jī)生成SQL在數(shù)據(jù)庫(kù)的不同版本上執(zhí)行以檢測(cè)數(shù)據(jù)庫(kù)系統(tǒng)的性能回退.SQLancer[9]是主要 用于檢測(cè)數(shù)據(jù)庫(kù)系統(tǒng)邏輯Bug的模糊測(cè)試工具，其中的PQS（Pivoted Query Synthesis）測(cè)試方法通過(guò) 選擇表中的一行作為Pivot Row，然后去構(gòu)造一定可以包含該行的查詢，如果數(shù)據(jù)庫(kù)執(zhí)行該查詢后結(jié) 果中沒(méi)有出現(xiàn)預(yù)設(shè)的Pivot Row，則表明數(shù)據(jù)庫(kù)實(shí)現(xiàn)有Bug.但是，PQS在測(cè)試Left Join、Group By等關(guān)鍵字時(shí)存在缺陷，同時(shí)無(wú)法驗(yàn)證查詢中間結(jié)果集大小，不支持測(cè)試聚集運(yùn)算.8卩。1只只瓦^(guò)12]通 過(guò)保留語(yǔ)法的突變來(lái)提高生成SQL的語(yǔ)法正確性，使用語(yǔ)義指導(dǎo)的查詢參數(shù)實(shí)例化算法來(lái)提高生成 SQL的語(yǔ)義正確性，發(fā)現(xiàn)了許多數(shù)據(jù)庫(kù)中內(nèi)存相關(guān)的Bug. SparkFuzz[11]通過(guò)隨機(jī)生成數(shù)據(jù)和負(fù)載，以 測(cè)試SparkSQL的查詢執(zhí)行引擎Bug，但是它分別在PostgreSQL和SparkSQL上執(zhí)行生成的負(fù)載，耗 時(shí)耗力.MutaSQL[10]使用基于突變的方法將SQL改寫成結(jié)果等價(jià)但形式不同的其他SQL，如果兩個(gè) SQL執(zhí)行結(jié)果不同，表明數(shù)據(jù)庫(kù)存在Bug.但是MutaSQL的缺點(diǎn)是需要將SQL在數(shù)據(jù)庫(kù)上執(zhí)行才能 知道結(jié)果.

綜上所述，由于SQL的高度結(jié)構(gòu)化，需要保證語(yǔ)法語(yǔ)義的嚴(yán)格正確性才能對(duì)數(shù)據(jù)庫(kù)進(jìn)行測(cè)試，通 用的模糊測(cè)試工具[14—15，17—181無(wú)法對(duì)數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行很好的測(cè)試;一部分負(fù)載生成工具[7，16]生成的負(fù)載質(zhì) 量需要提升;針對(duì)數(shù)據(jù)庫(kù)的模糊測(cè)試工具[8，，10-11]需要在真實(shí)數(shù)據(jù)庫(kù)上執(zhí)行生成的SQL才能獲得查詢的 基準(zhǔn)結(jié)果，測(cè)試代價(jià)太高.

2系統(tǒng)整體架構(gòu)

系統(tǒng)的整體架構(gòu)如圖1所示.用戶首先在配置文件中定義本次測(cè)試所需要生成數(shù)據(jù)庫(kù)模式中表的 數(shù)目、每張表的屬性列數(shù)目分布、屬性列數(shù)據(jù)分布、每張表的大小、生成查詢中連接算子的數(shù)目等關(guān) 鍵信息;Schema生成器會(huì)讀取配置文件，根據(jù)要生成的屬性列的數(shù)據(jù)類型及分布情況進(jìn)行屬性生成 函數(shù)生成，同時(shí)根據(jù)每張表的外鍵數(shù)量進(jìn)行表的參照關(guān)系生成;接著進(jìn)入數(shù)據(jù)生成器進(jìn)行大規(guī)模數(shù)據(jù) 生成，其中屬性生成函數(shù)是數(shù)據(jù)生成機(jī)制的核心，所有的非主鍵屬性是基于主鍵通過(guò)屬性生成函數(shù)確 定性計(jì)算得出.

負(fù)載生成器也會(huì)用到Schema生成器的結(jié)果，在負(fù)載生成器中，首先會(huì)根據(jù)定義的連接算子的數(shù)目進(jìn)行復(fù)雜負(fù)載模板的生成，負(fù)載生成器所生成的負(fù)載模板保證語(yǔ)法和語(yǔ)義正確.為了進(jìn)一步提升生 成負(fù)載的質(zhì)量，使用參數(shù)實(shí)例化器進(jìn)行合理的查詢參數(shù)填充.

生成完數(shù)據(jù)和負(fù)載后，將這些數(shù)據(jù)和負(fù)載導(dǎo)入數(shù)據(jù)庫(kù)中執(zhí)行，獲得數(shù)據(jù)庫(kù)執(zhí)行結(jié)果，同時(shí)將負(fù)載 輸入算子基數(shù)計(jì)算器進(jìn)行算子中間結(jié)果的計(jì)算，可與數(shù)據(jù)庫(kù)查詢優(yōu)化器基數(shù)預(yù)估的結(jié)果進(jìn)行對(duì)比;最 后再到查詢結(jié)果計(jì)算器中進(jìn)行最終查詢結(jié)果的計(jì)算，與數(shù)據(jù)庫(kù)執(zhí)行的結(jié)果進(jìn)行對(duì)比.如果兩者不一樣， 則表明數(shù)據(jù)庫(kù)有Bug，工具會(huì)把生成的數(shù)據(jù)以及該條SQL保存下來(lái)以便對(duì)Bug進(jìn)行復(fù)現(xiàn).

2.1基于主鍵的數(shù)據(jù)生成

在數(shù)據(jù)生成模塊中使用了關(guān)聯(lián)主鍵的確定性的數(shù)據(jù)生成機(jī)制，為后續(xù)在算子基數(shù)計(jì)算器和查 詢結(jié)果計(jì)算器中構(gòu)建約束優(yōu)化問(wèn)題奠定基礎(chǔ).確定性數(shù)據(jù)生成機(jī)制具有關(guān)聯(lián)主鍵的性質(zhì)，即所有非主 鍵屬性以主鍵為自變量使用生成函數(shù)確定性計(jì)算，其中主鍵值是采用自增形式產(chǎn)生，即被設(shè)置為 AUTO_INCREMENT.

數(shù)據(jù)生成器首先根據(jù)擬生成的屬性列的數(shù)據(jù)分布情況進(jìn)行屬性生成函數(shù)的生成，從而使得生成 的數(shù)據(jù)滿足一定的數(shù)據(jù)分布，比如高斯分布、ZipFian分布，具體做法是生成隨機(jī)的分段函數(shù).如果生 成的數(shù)據(jù)不需要滿足任何分布，則默認(rèn)為隨機(jī)分布.具體做法是先確定要生成的屬性列的數(shù)據(jù)類型， 如INT類型的范圍是-2 147483648?2147483647，再確定生成函數(shù)，確保主鍵經(jīng)過(guò)生成的函數(shù)映射 后的值不能超過(guò)預(yù)定數(shù)據(jù)類型的范圍.

假如要生成10000個(gè)值域?yàn)??100并滿足高斯分布的數(shù)，首先將10000個(gè)數(shù)按照高斯分布序列 分塊，將這些塊隨機(jī)裝到100個(gè)桶中，這100桶即代表值域?yàn)??100.按照上述方法生成的分段函數(shù) 如圖2所示，1?10000的主鍵值通過(guò)該分段函數(shù)生成的10000個(gè)數(shù)即為值域?yàn)??100、滿足高斯分 布的數(shù).

函數(shù)生成完成后，主鍵就可以通過(guò)已經(jīng)生成的函數(shù)進(jìn)行確定性數(shù)據(jù)生成.具體過(guò)程如圖3所示. 首先，數(shù)據(jù)生成器根據(jù)配置文件的要求生成滿足特定分布的數(shù)據(jù)：如果某一列需要滿足分布，則根據(jù) 分布的參數(shù)A盧等隨機(jī)生成分段函數(shù)，否則根據(jù)列的屬性（如值域Domain）隨機(jī)生成普通函數(shù).接著 生成數(shù)據(jù)，最后再進(jìn)行數(shù)據(jù)類型的轉(zhuǎn)換.

2.2表間依賴關(guān)系生成

在Schema生成器中，重點(diǎn)關(guān)注表間參照依賴關(guān)系生成.Schema生成器會(huì)根據(jù)配置文件生成每張 表，基于依賴的拓?fù)浒葱蛏擅繌埍淼乃型怄I以及這些外鍵的參照關(guān)系.一張表中可能有很多外鍵， Schema生成器確保單個(gè)表中的每個(gè)外鍵參照的表都不同，以此構(gòu)建表的參照依賴關(guān)系圖，如圖4所示.

2.3有效負(fù)載生成

負(fù)載生成器會(huì)參考Schema生成器的結(jié)果，同時(shí)組合不同種類的關(guān)鍵字生成語(yǔ)法和語(yǔ)義正確的負(fù)載模板，并使用查詢參數(shù)實(shí)例化算法填充模板，最終生成有效負(fù)載.

2.3.1負(fù)載模板生成

負(fù)載模板生成器使用SQL生成模型，根據(jù)配置選擇SQL關(guān)鍵字來(lái)生成語(yǔ)法語(yǔ)義正確的負(fù)載模板. 如圖5所示，首先SQL生成模型會(huì)根據(jù)Schema定義獲得表間參照依賴關(guān)系，然后選擇有依賴關(guān)系的 表來(lái)生成多表連接;接著從這些表中預(yù)先生成一個(gè)謂詞生成順序，按照該順序進(jìn)行謂詞語(yǔ)句的生成以 及查詢參數(shù)實(shí)例化，接著再生成Group By和Order By關(guān)鍵字;最后生成Select關(guān)鍵字以及5種聚集 運(yùn)算表達(dá)式.

2.3.2查詢參數(shù)實(shí)例化

負(fù)載模板生成器生成的是參數(shù)化的查詢模板.如圖6所示，該查詢模板以A、B、C、D四表連接為 例，查詢參數(shù)實(shí)例化器將按照的謂詞順序進(jìn)行相關(guān)參數(shù)（K）的實(shí)例化.進(jìn)行查詢參數(shù)實(shí) 例化后負(fù)載才能被DBMS正常執(zhí)行.查詢參數(shù)實(shí)例化十分重要，因?yàn)樗梢钥刂撇樵冎兴阕拥闹虚g結(jié) 果集大小，從而使得查詢優(yōu)化器選擇代價(jià)不同的查詢執(zhí)行計(jì)劃，直接影響查詢的執(zhí)行時(shí)間.

負(fù)載生成器使用查詢參數(shù)實(shí)例化器進(jìn)行有效查詢參數(shù)實(shí)例化，按照查詢模板中的預(yù)定的連接順 序?qū)λ械闹^詞進(jìn)行查詢參數(shù)實(shí)例化.

基于關(guān)聯(lián)主鍵的確定性數(shù)據(jù)生成機(jī)制，預(yù)生成的謂詞參數(shù)的取值范圍可以由已經(jīng)實(shí)例化完成的 算子的連接結(jié)果確定性得到.查詢參數(shù)實(shí)例化器會(huì)根據(jù)這個(gè)取值范圍選擇合理的參數(shù)對(duì)查詢模板進(jìn) 行填充.這種感知數(shù)據(jù)的查詢參數(shù)實(shí)例化算法可以確保每個(gè)過(guò)濾謂詞（Filter）算子以及每個(gè)連接 （Join）算子的有效性，故查詢的最終結(jié)果不會(huì)為NULL，從而提高了生成負(fù)載的測(cè)試效果.

2.4算子基數(shù)的高效計(jì)算

查詢優(yōu)化器依賴代價(jià)模型為搜索空間中的每個(gè)執(zhí)行計(jì)劃進(jìn)行代價(jià)預(yù)估.代價(jià)模型中的一個(gè)關(guān)鍵 參數(shù)就是算子的基數(shù)，現(xiàn)代查詢優(yōu)化器使用基數(shù)預(yù)估技術(shù)來(lái)獲取算子的基數(shù)大小，但是會(huì)有很大的誤 差，而且誤差會(huì)隨著連接算子數(shù)量的增多而越來(lái)越嚴(yán)重，最終導(dǎo)致優(yōu)化器選擇不到良好的執(zhí)行計(jì)劃. 如果能夠提供算子的精確基數(shù)，消除基數(shù)預(yù)估帶來(lái)的影響，可以對(duì)查詢優(yōu)化器進(jìn)行很好的評(píng)測(cè).

例 1 select * from a join b on a.fkx = b.primaryKey where a.colx < 1 993 and b.col2 > 2 000 算子基數(shù)計(jì)算器參照確定性的數(shù)據(jù)生成機(jī)制為每個(gè)算子構(gòu)造約束優(yōu)化問(wèn)題來(lái)表示其結(jié)果.以例 1為例，單表、Filter算子、Join算子的約束優(yōu)化表達(dá)式如圖7所示.在本例中，表a和表b的主鍵的取 值范圍分別是[0， 23444]和[0， 32345]，所以表a未加過(guò)濾謂詞（Filter）的約束為[Ka， [0， 23444]].表 a存在一個(gè)過(guò)濾謂詞為a.col1 < 1993，屬性a.col1是主鍵Ka使用生成函數(shù)F1（Ka）生成，所以 Filter的約束表示為[F1（Ka） < 1993， [0， 23444]].對(duì)于連接（Join）算子，涉及約束的轉(zhuǎn)移，由于連接 條件是a.fki = b.primaryKey， &.&1屬性同時(shí)又是表a的主鍵Ka使用f（Ka）函數(shù)生成的，所以可推導(dǎo) 出表b的主鍵Kb = f（Ka），將表b上的過(guò)濾謂詞約束F2（Kb） > 2000加入Filter的約束中，連接（Join） 算子的約束表達(dá)式即為[FjKa） < 1993， F2（f（Ka）） > 2000，[0， 23444]].

對(duì)于每個(gè)算子的約束表達(dá)式，使用Mathematical進(jìn)行約束求解.查詢中所有算子的精確基數(shù)被 基數(shù)計(jì)算器計(jì)算出后，查詢結(jié)果計(jì)算器會(huì)以主鍵對(duì)的形式表示每個(gè)算子的具體結(jié)果，接著參照查詢中 Select關(guān)鍵字后面的復(fù)雜表達(dá)式的情況再計(jì)算查詢的最終結(jié)果.基數(shù)計(jì)算器和查詢結(jié)果計(jì)算器為生成 的復(fù)雜分析型負(fù)載提供了基準(zhǔn)結(jié)果高效自計(jì)算、不用去執(zhí)行額外負(fù)載即可獲得算子的精確基數(shù)，可服 務(wù)于查詢優(yōu)化器的評(píng)估，同時(shí)查詢的精準(zhǔn)結(jié)果可用于發(fā)現(xiàn)數(shù)據(jù)庫(kù)執(zhí)行引擎的執(zhí)行問(wèn)題.

3實(shí)驗(yàn)分析

本章首先展示了工具的生成效率;然后，在開源的分布式數(shù)據(jù)庫(kù)TiDB的不同版本上來(lái)驗(yàn)證本文 提出的模糊測(cè)試工具的有效性.

3.1實(shí)驗(yàn)環(huán)境

TiDB部署在UCloud集群中的5臺(tái)機(jī)器上.本工具使用Java語(yǔ)言開發(fā)，運(yùn)行環(huán)境為OpenJDK 14， 約束求解工具使用的是Mathematica12[24]. TiDB集群中有1臺(tái)主TiDB節(jié)點(diǎn)用于處理客戶端連接， 3臺(tái)TiKV節(jié)點(diǎn)用于存儲(chǔ)數(shù)據(jù)，1臺(tái)PD節(jié)點(diǎn)用于調(diào)度以及1臺(tái)Monitor節(jié)點(diǎn)用于監(jiān)控整個(gè)TiDB集群 的情況.部署TiDB模塊和TiKV模塊的機(jī)器的主要配置是16核心CPU、16GB內(nèi)存，部署PD模塊 的機(jī)器的主要配置是2核心CPU、2GB內(nèi)存，部署Monitor監(jiān)控節(jié)點(diǎn)的機(jī)器的主要配置是8核心 CPU、8GB 內(nèi)存.

3.2負(fù)載生成效率

本節(jié)展示工具的負(fù)載生成效率，設(shè)置生成1000個(gè)Query，在每個(gè)Query中分別設(shè)置生成0 ～ 8個(gè) 連接算子，查看Query中連接算子的個(gè)數(shù)對(duì)Query平均生成時(shí)間的影響，實(shí)驗(yàn)結(jié)果如圖8所示.由于 負(fù)載生成過(guò)程中需要根據(jù)預(yù)定的連接順序進(jìn)行每個(gè)過(guò)濾謂詞的參數(shù)范圍計(jì)算，所以Query中連接算 子的個(gè)數(shù)會(huì)影響單條Query的生成效率.

3.3測(cè)試有效性展示

本節(jié)展示了利用該工具測(cè)試TiDB的不同版本，發(fā)現(xiàn)的一些查詢處理功能的缺陷或者Bug.

3.3.1Decimal 類型轉(zhuǎn)換 Bug

本例展示了 TiDB Master：1cebae2b版本的一個(gè)已經(jīng)確認(rèn)的Bug.在表中創(chuàng)建decimal（17， （3）類型 的屬性列，并插入相應(yīng)數(shù)據(jù)，但是在查詢結(jié)果時(shí)使用cast as decimal關(guān)鍵字轉(zhuǎn)換的時(shí)候出現(xiàn)結(jié)果錯(cuò)誤. decimal默認(rèn)長(zhǎng)度為10，但是返回的結(jié)果長(zhǎng)度為11.本工具通過(guò)生成如下的數(shù)據(jù)和查詢發(fā)現(xiàn)了該問(wèn)題： ---創(chuàng)建表

create table table_0_0 （primaryKey bigint，col_0 int，col_1 double，col_2 int，col_3 int，col_4 int，col_5 int，col_6 double，col_7 decimal（17，（3），primary key （primaryKey））;

---插入工具生成的數(shù)據(jù)

insert into table_0_0 values （1，1，544.67，65，766，5 544，65 554， 44 336.7，93 994 883 422 334.30（1）; ---執(zhí)行工具生成的負(fù)載

select length （cast（col_7 as decimal）） from table_0_0;

-工具計(jì)算出的理想結(jié)果 10

---數(shù)據(jù)庫(kù)執(zhí)行的真實(shí)結(jié)果 11

3.3.2TiDB Float類型不精確的問(wèn)題

本例展示了 TiDB的表中屬性列設(shè)置float數(shù)據(jù)類型不能被精確查找出來(lái)的問(wèn)題.由于本工具中 的數(shù)據(jù)生成器采用確定性的數(shù)據(jù)生成機(jī)制，所有的數(shù)據(jù)都能被精確地生成，同時(shí)約束求解器求解過(guò)程 準(zhǔn)確，所以可以對(duì)float類型參與的計(jì)算進(jìn)行精確的表示.該問(wèn)題盡管已經(jīng)證實(shí)是TiDB的原始設(shè)計(jì)意 圖，但是這也證明了本工具的計(jì)算結(jié)果是精確而有效的，不用依賴權(quán)威數(shù)據(jù)庫(kù).測(cè)試樣例如下：

…創(chuàng)建表

create table table_0_13 （primaryKey bigint， col_0 int， col_1 double， col_2 int， col_3 int， col_4 int， col_5 float， primary key （primaryKey））;

---插入工具生成的數(shù)據(jù)

insert into table_0_13 values （7， 1， 9 983.22， 62， 76， 55， -8 888.9（5）;

---執(zhí)行工具生成的負(fù)載

select col_5 from table_0_13 where table_0_13.col_5 = 8 888.95;

一工具計(jì)算出的理想結(jié)果 -8 888.95

---數(shù)據(jù)庫(kù)執(zhí)行的真實(shí)結(jié)果 Empty set

3.3.3TiDB主鍵自增Bug

本例展示了在TiDB5.0版本表中設(shè)置float或double類型的主鍵同時(shí)設(shè)置auto_increment，使用 insert into或者replace into插入數(shù)據(jù)，每次插入會(huì)出現(xiàn)增量步長(zhǎng)不是1的問(wèn)題.本文提出的模糊測(cè)試 工具生成的如下負(fù)載發(fā)現(xiàn)了這個(gè)Bug，因?yàn)?個(gè)值之間的增量變成了 2，所以求和為錯(cuò)誤的結(jié)果49而 不是理想的結(jié)果28.測(cè)試樣例如下：

---創(chuàng)建表

create table table_0_2 （id double primary key AUTO_INCREMENT， col1 int）;

---插入工具生成的數(shù)據(jù)

replace into table_0_2 （col（1） values （1）; insert into table_0_2 （col（1） values （1）; replace into table_0_2 （col（1） values （1）; insert into table_0_2 （col（1） values （1）; replace into table_0_2 （col（1） values （1）; insert into table_0_2 （col（1） values （1）; replace into table_0_2 （col（1） values （1）; ---執(zhí)行工具生成的負(fù)載

select sum（id） from table_0_2; 一工具計(jì)算出的理想結(jié)果28

---數(shù)據(jù)庫(kù)執(zhí)行的真實(shí)結(jié)果 49

4結(jié)論

針對(duì)分析型數(shù)據(jù)庫(kù)查詢處理功能正確性的測(cè)試問(wèn)題，本文實(shí)現(xiàn)了一個(gè)模糊測(cè)試工具.使用關(guān)聯(lián)主 鍵的確定性數(shù)據(jù)生成機(jī)制生成滿足給定分布的數(shù)據(jù);使用SQL生成模型生成語(yǔ)法語(yǔ)義正確的負(fù)載模 板并使用查詢參數(shù)實(shí)例化算法使得負(fù)載有效;通過(guò)構(gòu)建約束優(yōu)化問(wèn)題高效求解算子基數(shù)及查詢結(jié)果. 經(jīng)過(guò)小規(guī)模測(cè)試，在開源的NewSQL分布式數(shù)據(jù)庫(kù)TiDB上檢測(cè)出了一些問(wèn)題，驗(yàn)證了工具的可用性.

[參考文獻(xiàn)]

[1]SILBERSCHATZ A， KORTH H F， SUDARSHAN S. Database Systems Concepts [M]. 5th ed. New York： McGraw-Hill Book Company， 2005.

[2] CHAUDHURI S. An overview of query optimization in relational systems [C]//Proceedings of the Seventeenth ACM SIGACT- SIGMOD-SIGART Symposium on Principles of Database Systems - PODS '98. Seattle： ACM Press， 1998： 34-43.

[3 ] LAN H， BAO Z， PENG Y. A survey on advancing the DBMS query optimizer： Cardinality estimation， cost model， and plan enumeration [J]. Data Science and Engineering， 2021， 6（1）： 86-101.

[4 ] LEIS V， GUBICHEV A， MIRCHEV A， et al. How good are query optimizers， really？ [J]. Proceedings of the VLDB Endowment， 2015， 9（3）： 204-215.

[5 ] LI J， ZHAO B， ZHANG C. Fuzzing： A survey [J]. Cybersecurity， 2018， 1（1）： 6.

[6 ] MANES V J M， HAN H， HAN C， et al. The art， science， and engineering of fuzzing： A survey [J]. IEEE Transactions on Software Engineering， 2019. DOI： 10.1109/TSE.2019.2946563.

[7]SLUTZ D R. Massive stochastic testing of SQL [C]//Very Large Data Base. 1998： 618-622.

[8 ] SELTENREICH A， TANG B， MULLENDER S. SQLSmith [CP/OL]. [2021-08-01]. https：//github.com/anse1/sqlsmith.

[9]RIGGER M， SU Z. Testing database engines via pivoted query synthesis [C]//14th Symposium on Operating Systems Design and Implementation. 2020： 667-682.

[10]CHEN X， WANG C， CHEUNG A. Testing query execution engines with mutations [C]//Proceedings of the Workshop on Testing Database Systems. Portland Oregon： ACM， 2020： 1-5.

[11]GHIT B， POGGI N， ROSEN J， et al. SparkFuzz： Searching correctness regressions in modern query engines [C]//Proceedings of the Workshop on Testing Database Systems. Portland Oregon： ACM， 2020： 1-6.

[12]ZHONG R， CHEN Y， HU H， et al. SQUIRREL： Testing database management systems with language validity and coverage feedback [C] //Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Virtual Event USA： ACM， 2020： 955-970.

[13]JUNG J， HU H， ARULRAJ J， et al. APOLLO： Automatic detection and diagnosis of performance regressions in database systems [J]. Proceedings of the VLDB Endowment， 2019， 13（1）： 57-70.

[14]BLAZYTKO T， BISHOP M， ASCHERMANN C， et al. GRIMOIRE： Synthesizing structure while fuzzing [C]//28th Security Symposium （Security 19）. 2019： 1985-2002.

[15]ZALEWSKI M. American fuzzy lop （2.52b） [CP/OL]. [2021-08-01]. http：//lcamtuf.coredump.cx/afl.

[16]BATI H， GIAKOUMAKIS L， HERBERT S， et al. A genetic approach for random testing of database systems [C]//Proceedings of the 33rd International Conference on Very Large Data Bases. 2007： 1243-1251.

[17]ASCHERMANN C， FRASSETTO T， HOLZ T， et al. NAUTILUS： Fishing for deep bugs with grammars [C]//NDSS. 2019.

[18]PADHYE R， LEMIEUX C， SEN K， et al. Semantic fuzzing with zest [C] //Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2019： 329-340.

[19]STILLGER M， FREYTAG J C. Testing the quality of a query optimizer [J]. IEEE Data Engineering Bulletin， 1995， 18（3）： 41-48.

[20]GU Z， SOLIMAN M A， WAAS F M. Testing the accuracy of query optimizers [C] //Proceedings of the Fifth International Workshop on Testing Database Systems. 2012： 1-6.

[21]CHAUDHURI S， NARASAYYA V， RAMAMURTHY R. Exact cardinality query optimization for optimizer testing [J] . Proceedings of the VLDB Endowment， 2009， 2（1）： 994-1005.

[22]TRUMMER I. Exact cardinality query optimization with bounded execution cost [C]//Proceedings of the 2019 International Conference on Management of Data. Amsterdam Netherlands： ACM， 2019： 2-17.

[23]SHIN J H， RUSU F， SUHAN A. Exact selectivity computation for modern in-memory database query optimization [EB/OL]. （2019- 01-06）[2021-09-18]. https：//arxiv.org/pdf/1901.01488.pdf.

[24]WOLFRAM. Mathematica 12 [CP/OL]. [2021-08-01]. https：//www.wolfram.com/mathematica/.

（責(zé)任編輯：李萬(wàn)會(huì)）