岳文靜 屈穩(wěn)穩(wěn) 林 寬 王曉玲

1 （華東師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200062）

2 （華東師范大學(xué)上海智能教育研究院 上海 200062）

3 （中國科學(xué)院空天信息創(chuàng)新研究院 北京 100190）

（wjyue@stu.ecnu.edu.cn）

基數(shù)估計(jì)（cardinality estimation）是數(shù)據(jù)庫執(zhí)行查詢優(yōu)化中的一個(gè)重要環(huán)節(jié)，用于估計(jì)在數(shù)據(jù)庫中執(zhí)行查詢后返回的結(jié)果數(shù). 理論上，只要提供了準(zhǔn)確的基數(shù)估計(jì)和物理計(jì)劃執(zhí)行代價(jià)，并可以在巨大搜索空間中有效地枚舉計(jì)劃，數(shù)據(jù)庫就可以在合理的時(shí)間內(nèi)制定出最佳查詢計(jì)劃. 傳統(tǒng)的基數(shù)估計(jì)技術(shù)一般采用像直方圖等數(shù)據(jù)結(jié)構(gòu)的統(tǒng)計(jì)方法來表示數(shù)據(jù)表上的數(shù)據(jù)分布，或者通過采樣的方法估計(jì)數(shù)據(jù)的分布. 但實(shí)際上，由于復(fù)雜謂詞和對(duì)多個(gè)數(shù)據(jù)表估計(jì)等復(fù)雜查詢的固有難題，以及數(shù)據(jù)日益增加的復(fù)雜性，數(shù)據(jù)庫的查詢場(chǎng)景越來越復(fù)雜，其對(duì)于基數(shù)估計(jì)技術(shù)在處理多列、多謂詞查詢以及多表連接等情況下的能力要求逐漸增強(qiáng). 盡管傳統(tǒng)的基數(shù)估計(jì)技術(shù)可以在短時(shí)間內(nèi)給出數(shù)據(jù)集的統(tǒng)計(jì)結(jié)果，但由于其難以兼顧空間開銷與估計(jì)準(zhǔn)確率、難以處理復(fù)雜數(shù)據(jù)分布等特性，使其在面對(duì)復(fù)雜困難的查詢場(chǎng)景時(shí)，基數(shù)估計(jì)的性能仍有待提升.

近年來，鑒于人工智能技術(shù)在復(fù)雜的數(shù)據(jù)處理和模型學(xué)習(xí)方面的能力，數(shù)據(jù)庫研究人員在基數(shù)估計(jì)技術(shù)中引入了人工智能技術(shù)，提出了基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù). 如何建模查詢與基數(shù)之間的映射關(guān)系，以及如何建模數(shù)據(jù)、列屬性與數(shù)據(jù)表之間的映射關(guān)系是目前研究中關(guān)心的2 個(gè)核心問題. 在已有的研究中，基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)方法一般分為2 類：一類方法為查詢驅(qū)動(dòng)的基數(shù)估計(jì)方法[1-14]，此類方法直接建模查詢負(fù)載和基數(shù)之間的關(guān)系；另一類方法為數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)方法[15-21]，此類方法通過擬合數(shù)據(jù)庫中的數(shù)據(jù)聯(lián)合分布函數(shù)來計(jì)算基數(shù).

最新的研究[22-25]中對(duì)比了傳統(tǒng)的基數(shù)估計(jì)算法和基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)算法，展示了基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)可以很好地提升基數(shù)估計(jì)的準(zhǔn)確性. 但它們也繼承了人工智能算法建模的一些不可解釋性、魯棒性差等問題，距離實(shí)際落地應(yīng)用仍有很大的差距.

基數(shù)估計(jì)技術(shù)是查詢處理中的核心技術(shù)之一，也是學(xué)術(shù)界一直關(guān)注的研究熱點(diǎn). 文獻(xiàn)[25]主要介紹了傳統(tǒng)的基數(shù)估計(jì)技術(shù)和查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù). 文獻(xiàn)[22]詳細(xì)地介紹了傳統(tǒng)的基數(shù)估計(jì)相關(guān)技術(shù)，并從是否使用了監(jiān)督學(xué)習(xí)技術(shù)的角度討論了基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)的相關(guān)技術(shù)，同時(shí)對(duì)相關(guān)基數(shù)估計(jì)技術(shù)中編碼的內(nèi)容進(jìn)行了簡單說明. 文獻(xiàn)[24]側(cè)重于比較在無數(shù)據(jù)更新和數(shù)據(jù)頻繁更新的查詢場(chǎng)景下，傳統(tǒng)的基數(shù)估計(jì)技術(shù)與基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)的性能表現(xiàn). 同時(shí)從技術(shù)實(shí)際落地角度出發(fā)，給出了基于學(xué)習(xí)的基數(shù)估計(jì)技術(shù)未來的研究方向. 文獻(xiàn)[23]為基于學(xué)習(xí)的基數(shù)估計(jì)技術(shù)探索了統(tǒng)一的設(shè)計(jì)空間，主要介紹了查詢驅(qū)動(dòng)與數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)，同時(shí)在準(zhǔn)確率和效率2 個(gè)方面對(duì)相關(guān)技術(shù)進(jìn)行了分析比較. 本文在已有綜述研究的基礎(chǔ)上：1）增加了針對(duì)基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)特征編碼技術(shù)的對(duì)比、分析和總結(jié)；2）基于文獻(xiàn)[23]中提供的設(shè)計(jì)空間，以及對(duì)基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)相關(guān)技術(shù)的總結(jié)，本文提煉了建模查詢驅(qū)動(dòng)和數(shù)據(jù)驅(qū)動(dòng)2 類不同映射關(guān)系的核心工作流程，進(jìn)一步在傳統(tǒng)的SQL 查詢和NoSQL 應(yīng)用中分析了查詢驅(qū)動(dòng)、數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)，同時(shí)補(bǔ)充了最新的前沿技術(shù). 由于混合模型的基數(shù)估計(jì)技術(shù)的興起，本文增加了對(duì)這類基數(shù)估計(jì)技術(shù)的介紹與分析，從而進(jìn)一步完善基數(shù)估計(jì)技術(shù)的分類體系.

本文的組織結(jié)構(gòu)包含4 個(gè)方面：1）全面闡述數(shù)據(jù)庫中的基數(shù)、基數(shù)估計(jì)以及基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)的定義，并分析了其使用的特征編碼技術(shù)及基數(shù)估計(jì)技術(shù)中的分類體系. 2）根據(jù)提煉出的查詢驅(qū)動(dòng)的基數(shù)估計(jì)和數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)的建模流程，分別介紹了這2 類具有代表性的基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)，并補(bǔ)充了混合模型的基數(shù)估計(jì)建模流程以及相關(guān)技術(shù). 3）在查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)中整理了其在NoSQL 的應(yīng)用技術(shù). 4）討論了基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)面臨的挑戰(zhàn)以及未來的研究方向.

1 基數(shù)估計(jì)定義及分類

1.1 基數(shù)估計(jì)

給定SQL 查詢語句和數(shù)據(jù)庫D，基數(shù)（cardinality）是在數(shù)據(jù)庫D中執(zhí)行查詢q返回的結(jié)果行數(shù)，記為C(q|D)=|D′|，其中D′表示查詢結(jié)果，而基數(shù)估計(jì)則表示在不執(zhí)行查詢q的情況下，對(duì)基數(shù)進(jìn)行估計(jì)[23].Leis 等人[26]證明了代價(jià)估計(jì)的性能主要與基數(shù)估計(jì)的精度有關(guān)，而代價(jià)估計(jì)是數(shù)據(jù)庫查詢優(yōu)化中的關(guān)鍵步驟. 因此基數(shù)估計(jì)對(duì)查詢優(yōu)化器產(chǎn)生最優(yōu)的查詢計(jì)劃至關(guān)重要.

1.2 基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)

給定SQL 查詢q、數(shù)據(jù)庫D，基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)是要學(xué)習(xí)q和基數(shù)C之間的一個(gè)映射函數(shù)[23]，或者學(xué)習(xí)一個(gè)擬合數(shù)據(jù)庫中數(shù)據(jù)分布的函數(shù)[23]，輸入q后函數(shù)返回估計(jì)的基數(shù)，不同的任務(wù)使得函數(shù)的表現(xiàn)形式不同. 基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)的目標(biāo)就是盡可能地使=C.

1.3 特征編碼技術(shù)

將SQL 語句或者使用的數(shù)據(jù)表編碼為特征向量作為基數(shù)估計(jì)模型的輸入是基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)的基礎(chǔ). 本文對(duì)基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)中的特征編碼技術(shù)進(jìn)行了2 個(gè)維度上的分類，一類為特征編碼的類型，分為謂詞（運(yùn)算符、查詢值與列序號(hào)（id）、連接類型、數(shù)據(jù)庫元數(shù)據(jù)、數(shù)據(jù)表數(shù)據(jù)和其他屬性的特征. 另一類為特征的編碼方式，共分為3類. 其中獨(dú)熱（One-Hot）編碼、嵌入（Embedding）編碼是最常用的編碼方式，其余基于特定查詢屬性的編碼方式歸結(jié)為其他類型的編碼方式. 表1 將已有研究分別對(duì)應(yīng)到特征編碼技術(shù)的2 個(gè)分類中. 下面本文將根據(jù)特征編碼方式對(duì)已有研究中編碼的特征類型進(jìn)一步歸納總結(jié).

Table 1 Feature Encoding Techniques Based on Machine Learned Cardinality Estimation Techniques表1 基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)的特征編碼技術(shù)

1.3.1 One-Hot 編碼

One-Hot 編碼將查詢屬性特征轉(zhuǎn)換為同一維度的向量表示，并使用0 或1 表示. 基于神經(jīng)網(wǎng)絡(luò)（neural network, NN）的模型NNST[3]使用One-Hot 編碼了查詢計(jì)劃，其中將查詢計(jì)劃根據(jù)數(shù)據(jù)庫屬性信息和單一操作運(yùn)算符支持的謂詞（即支持等值謂詞編碼，對(duì)于1 維范圍選擇謂詞，僅編碼了查詢值）編碼為子查詢的特征向量，其中數(shù)據(jù)庫屬性信息包括最大值、最小值、基數(shù)和1 維等寬直方圖表示. 不同的研究對(duì)于查詢計(jì)劃的屬性特征定義不同，其中模型MSCN[5]編碼了查詢語句中表的集合、連接的集合和謂詞集合的表示，并作為模型的輸入. 值得注意的是，謂詞集合中僅使用了One-Hot 編碼列id 和運(yùn)算符id，查詢值使用的是歸一化的數(shù)值. 而文獻(xiàn)[6]編碼了查詢語句中的表id、選擇謂詞以及等值連接謂詞，同樣使用了歸一化的方式將范圍選擇謂詞中的查詢值進(jìn)行編碼.該文獻(xiàn)中提出的模型支持?jǐn)?shù)據(jù)表的等值連接，通過選用不同的編碼特征和不同的機(jī)器學(xué)習(xí)模型，使其可以適用于文獻(xiàn)[6] 中定義的查詢類型. 文獻(xiàn)[8]由于同時(shí)可以估計(jì)查詢成本，因此使用了One-Hot 編碼物理操作，包括連接類型和3 類算子，同時(shí)也對(duì)數(shù)值型的查詢謂詞進(jìn)行了編碼.

1.3.2 Embedding 編碼

在屬性個(gè)數(shù)較多的情況下使用One-Hot 編碼，特征空間維度巨大且編碼稀疏，進(jìn)而計(jì)算代價(jià)較大. 為了解決One-Hot 編碼的缺陷，Embedding 編碼將稀疏的查詢特征表示變?yōu)榈途S稠密空間的特征表示. 文獻(xiàn)[17,19]均編碼了數(shù)據(jù)表中的數(shù)據(jù)作為模型的輸入向量，對(duì)于不同取值數(shù)較大的列，均使用Embedding編碼來將表內(nèi)數(shù)據(jù)編碼為一個(gè)稠密向量，否則使用One-Hot 編碼. 模型GL（global-local）[27]將查詢、提出的閾值編碼為向量，同樣使用了One-Hot，Embedding編碼等方式將高維圖片或者文本等數(shù)據(jù)編碼為數(shù)據(jù)向量，然后使用神經(jīng)網(wǎng)絡(luò)將向量進(jìn)一步轉(zhuǎn)換為模型輸入需要維度的特征向量.

1.3.3 其他編碼方式

除了1.3.1 節(jié)和1.3.2 節(jié)中所述的2 種常見的編碼方式之外，一些研究對(duì)特定的查詢特征屬性提出了特定的編碼方式. 模型Local NN[4]使用了2 種方式進(jìn)行編碼，該模型使用One-Hot 編碼技術(shù)編碼運(yùn)算符，對(duì)于查詢中的值，若其為數(shù)值型則使用歸一化公式進(jìn)行編碼，否則，使用字典編碼將非數(shù)值型的值轉(zhuǎn)換為數(shù)值型. 文獻(xiàn)[7]利用語義模板定義了查詢的多種特征，并直接使用特征的變量值作為查詢的多維特征向量.其中，多種特征包括查詢的屬性、運(yùn)算符、查詢數(shù)值、模型參數(shù)、聚合和用戶自定義函數(shù)（user-defined function, UDF）的參數(shù)等. 文獻(xiàn)[8]提出使用字符串編碼技術(shù)編碼字符型的查詢謂詞，使用位圖來編碼樣本位圖，即使用固定大小的向量來判斷每位對(duì)應(yīng)的元組是否滿足查詢節(jié)點(diǎn)的謂詞. 文獻(xiàn)[9]中提出的2 類模型，分別為樹模型和NN 模型. 將范圍查詢中d個(gè)數(shù)字屬性的范圍上下界直接拼接為1 個(gè)2d的元組作為范圍特征. 此外，還將單屬性直方圖中的信息生成查詢的選擇度估計(jì)作為回歸模型的額外特征. 模型DLM[18]將數(shù)據(jù)表中的一行數(shù)據(jù)看作一個(gè)序列，根據(jù)值id 將每個(gè)值編碼為一個(gè)二進(jìn)制向量. 而文獻(xiàn)[28]自動(dòng)確定規(guī)模的極端梯度提升（extreme gradient boosting,XGBoost）模型使用數(shù)值轉(zhuǎn)換的方式將查詢范圍謂詞和分類謂詞轉(zhuǎn)換為十進(jìn)制數(shù)字作為查詢特征，并將計(jì)算查詢中單表的選擇度估計(jì)值作為選擇度特征.

1.4 基數(shù)估計(jì)技術(shù)分類體系

基數(shù)估計(jì)技術(shù)根據(jù)是否使用了機(jī)器學(xué)習(xí)算法分為傳統(tǒng)的基數(shù)估計(jì)技術(shù)和基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)2 類，其分類體系如圖1 所示.

Fig. 1 The classification system of cardinality estimation圖1 基數(shù)估計(jì)分類體系

傳統(tǒng)的基數(shù)估計(jì)技術(shù)一般被分為基于統(tǒng)計(jì)的和基于采樣的方法. 基于統(tǒng)計(jì)的方法[29-35]的核心是使用某種數(shù)據(jù)結(jié)構(gòu)，例如直方圖[29-31]、數(shù)據(jù)畫像[32-35]來擬合表上的數(shù)據(jù)分布，其中，文獻(xiàn)[29]采用了直方圖來近似數(shù)據(jù)庫中的數(shù)據(jù)分布，這類基于直方圖的統(tǒng)計(jì)方法估計(jì)精度較高，但是由于其內(nèi)存占用大，所以檢索速度較慢. 該類方法只考慮了擬合單列的數(shù)據(jù)分布，沒有考慮多列屬性之間的相關(guān)性；文獻(xiàn)[32]采用數(shù)據(jù)畫像來估計(jì)數(shù)據(jù)集中不同元素的個(gè)數(shù)，使用隨機(jī)哈希函數(shù)并基于隨機(jī)假設(shè)，可以將任意數(shù)據(jù)集映射成服從均勻分布的隨機(jī)值序列從而進(jìn)行估計(jì).HyperLogLog[33]基于基數(shù)估計(jì)器LogLog，使用調(diào)和平均數(shù)降低了方差. 相比于基于直方圖的估計(jì)方法，基于數(shù)據(jù)畫像的方法通常探索一個(gè)性能良好的哈希函數(shù)來擬合數(shù)據(jù)分布，占用內(nèi)存較小、檢索速度更快.但是這類方法仍舊僅針對(duì)單列的數(shù)據(jù)估計(jì)其基數(shù)，不適用于現(xiàn)實(shí)中復(fù)雜的查詢應(yīng)用. 基于采樣的方法[36-40]的核心是通過從原始數(shù)據(jù)集中采樣到小數(shù)據(jù)集來估計(jì)數(shù)據(jù)的整體分布，以反映不同表之間的關(guān)聯(lián)關(guān)系. 不同于基于統(tǒng)計(jì)的基數(shù)估計(jì)方法，基于采樣的基數(shù)估計(jì)方法不依賴于特定的假設(shè)，通過對(duì)不同的表按照一定的采樣方式采集元組，并進(jìn)一步利用這些元組估計(jì)基數(shù). 但如何高效地在一個(gè)規(guī)模較大的數(shù)據(jù)集上進(jìn)行采樣，當(dāng)?shù)讓訑?shù)據(jù)發(fā)生更新后如何進(jìn)行重采樣，如何支持非等值連接仍然是需要解決的問題[22].

由于傳統(tǒng)的基數(shù)估計(jì)技術(shù)計(jì)算需要存儲(chǔ)直方圖、位圖、采樣的元組等信息，會(huì)占用較大的存儲(chǔ)空間；而基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)僅需要存儲(chǔ)學(xué)習(xí)映射函數(shù)的模型，因此相較于傳統(tǒng)基數(shù)估計(jì)技術(shù)，其模型占用空間小. 基于統(tǒng)計(jì)的基數(shù)估計(jì)技術(shù)適用于擬合單列的數(shù)據(jù)分布，而在處理任意多列組合數(shù)據(jù)之間的復(fù)雜關(guān)系，其能力較弱. 基于采樣的方法可以有效支持小規(guī)模數(shù)據(jù)表的查詢. 但隨著數(shù)據(jù)的日益增加，基于采樣的基數(shù)估計(jì)技術(shù)在大規(guī)模數(shù)據(jù)表的復(fù)雜查詢場(chǎng)景中需要消耗大量空間存儲(chǔ)采樣的元組，同時(shí)有效采樣元組會(huì)隨著多表復(fù)雜的連接而減少，損失估計(jì)的性能. 因此，傳統(tǒng)的基數(shù)估計(jì)技術(shù)在處理涉及多列、多謂詞的查詢，以及多表連接等復(fù)雜困難的查詢場(chǎng)景時(shí)，常會(huì)導(dǎo)致較高的預(yù)測(cè)偏差[23]. 由于機(jī)器學(xué)習(xí)技術(shù)可以學(xué)習(xí)到非線性數(shù)據(jù)之間的復(fù)雜關(guān)系，因此基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)可以更好地表達(dá)查詢特征以及擬合數(shù)據(jù)的復(fù)雜分布，進(jìn)而能夠支持較為復(fù)雜的查詢場(chǎng)景.

基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)由于基數(shù)估計(jì)精度高、占用空間小、擬合復(fù)雜數(shù)據(jù)關(guān)系能力強(qiáng)等特點(diǎn)，受到了研究者們的廣泛關(guān)注與青睞. 根據(jù)已有工作，本文將基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)在主流數(shù)據(jù)庫中的應(yīng)用分為3 類，分別為查詢驅(qū)動(dòng)的基數(shù)估計(jì)、數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)和兩者混合模型的基數(shù)估計(jì). 此外，查詢驅(qū)動(dòng)的基數(shù)估計(jì)在NoSQL 中也得到了廣泛應(yīng)用.

2 查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)

查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)的核心思路是學(xué)習(xí)查詢q和基數(shù)C之間映射的一個(gè)回歸函數(shù)fθ(q,C)，其中θ表示模型需要學(xué)習(xí)的參數(shù). 查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)通常使用不同的編碼方式、編碼查詢負(fù)載的不同特征屬性，基于不同的監(jiān)督學(xué)習(xí)算法模型建模查詢、列屬性和表三者之間的關(guān)系，以支持不同數(shù)據(jù)量的查詢操作. 首先，本文基于已有的查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)，歸納出查詢驅(qū)動(dòng)的基數(shù)估計(jì)的一般性建模流程；然后對(duì)不同查詢驅(qū)動(dòng)的基數(shù)估計(jì)相關(guān)模型進(jìn)行了詳細(xì)的介紹，其中包括了在NoSQL 中的相關(guān)研究；最后對(duì)相關(guān)模型進(jìn)行了對(duì)比和總結(jié).

2.1 查詢驅(qū)動(dòng)的基數(shù)估計(jì)建模流程

查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)的核心思想是建立一個(gè)查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型，其一般性的建模流程如圖2 所示，分為輸入、輸出和模型建立3 部分[23-24].

Fig. 2 General modeling flow for query-driven cardinality estimation圖2 查詢驅(qū)動(dòng)的基數(shù)估計(jì)的一般性建模流程

1）輸入

輸入數(shù)據(jù)集DStrain/test{〈q,C〉}、數(shù)據(jù)庫D以及模型約束參數(shù) ?. 例如，對(duì)于查詢驅(qū)動(dòng)的代表模型MSCN[5]，其輸入為數(shù)據(jù)集DStrain/test和數(shù)據(jù)庫D. 其中，給定SQL查詢q經(jīng)過查詢解析器后構(gòu)建出的數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)，同時(shí)將q對(duì)應(yīng)的真實(shí)基數(shù)C作為標(biāo)簽.

2）輸出

在數(shù)據(jù)庫D中執(zhí)行查詢q后估計(jì)的基數(shù). 在得到估計(jì)的基數(shù)后，經(jīng)過基于代價(jià)模型的代價(jià)估計(jì)，使得數(shù)據(jù)庫可以制定查詢計(jì)劃，進(jìn)而完成查詢優(yōu)化.

3）模型建立

①模型訓(xùn)練. 如圖2 中粗實(shí)線條箭頭所示，模型共包含2 個(gè)模塊：查詢特征編碼器和監(jiān)督學(xué)習(xí)模型.首先模型使用查詢特征編碼器，根據(jù)不同的任務(wù)或者模型需求，將輸入的查詢q解析為具有固定維度φ的查詢特征向量Q、謂詞特征等，其中|Q|=φ，查詢特征編碼器中的編碼技術(shù)如表1 所示. 將Q與真實(shí)基數(shù)C構(gòu)建為輸入對(duì)〈Q,C〉輸入到監(jiān)督學(xué)習(xí)模型中進(jìn)行訓(xùn)練，在訓(xùn)練過程中構(gòu)造特定的損失函數(shù)，不斷優(yōu)化模型的學(xué)習(xí)參數(shù) θ.

本文以模型MSCN 為例來解釋查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型訓(xùn)練的流程. 首先將連接查詢q分為3 部分，分別表示查詢語句中表的集合、連接的集合和謂詞的集合，從而將查詢、列屬性和表關(guān)聯(lián)起來. 然后將這3 個(gè)集合分別輸入到3 個(gè)2 層的神經(jīng)網(wǎng)絡(luò)中得到3個(gè)對(duì)應(yīng)的特征向量. 3 個(gè)特征向量拼接后得到的查詢特征向量與真實(shí)的基數(shù)一起輸入到2 層的多層感知機(jī)中，并使用梯度下降算法進(jìn)行訓(xùn)練.

②模型推理. 如圖2 中細(xì)實(shí)線條箭頭所示，基數(shù)估計(jì)在推理階段同樣需要經(jīng)過①中的2 個(gè)模塊. 不同的是，在模型推理階段，模型參數(shù)θ已知，數(shù)據(jù)庫可以直接通過已經(jīng)訓(xùn)練好的模型估計(jì)查詢q的基數(shù).

同理以模型MSCN 為例來解釋查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型推理的流程. 當(dāng)輸入一個(gè)新的查詢q后，MSCN 同樣將q分為3 部分并利用訓(xùn)練好的3 個(gè)神經(jīng)網(wǎng)絡(luò)分別編碼這3 個(gè)部分為特征向量，拼接這3 個(gè)特征向量后輸入到訓(xùn)練好的多層感知機(jī)中得到最終估計(jì)的基數(shù).

2.2 查詢驅(qū)動(dòng)的基數(shù)估計(jì)相關(guān)模型

在目前的研究[1-9,28]中，許多研究人員根據(jù)不同的查詢需求和基于不同的監(jiān)督學(xué)習(xí)方法建立了不同的基數(shù)估計(jì)模型. 本文根據(jù)監(jiān)督學(xué)習(xí)類型將已有研究分為2 類，其中文獻(xiàn)[1?6]是基于神經(jīng)網(wǎng)絡(luò)算法的基數(shù)估計(jì)模型，文獻(xiàn)[7?9, 28] 是基于樹結(jié)構(gòu)的基數(shù)估計(jì)模型. 其次，本文分析了查詢驅(qū)動(dòng)的基數(shù)估計(jì)在NoSQL[27,41-47]上的應(yīng)用研究.

2.2.1 基于神經(jīng)網(wǎng)絡(luò)算法的基數(shù)估計(jì)模型

神經(jīng)網(wǎng)絡(luò)優(yōu)秀的大規(guī)模數(shù)據(jù)擬合能力和非線性建模能力可以帶來更好的估計(jì)精度. 因此，許多研究將神經(jīng)網(wǎng)絡(luò)引入到查詢回歸模型中，用于處理不同類型的查詢負(fù)載. 在基于神經(jīng)網(wǎng)絡(luò)算法的基數(shù)估計(jì)技術(shù)中，Lakshmi 等人[1]將神經(jīng)網(wǎng)絡(luò)應(yīng)用到用戶自定義函數(shù)的基數(shù)估計(jì)中，并將反向傳播算法應(yīng)用到基數(shù)估計(jì)技術(shù). 此研究是將基數(shù)估計(jì)應(yīng)用到神經(jīng)網(wǎng)絡(luò)的初步探索. 隨著深度學(xué)習(xí)的發(fā)展Ortiz 等人[3]提出使用深度強(qiáng)化學(xué)習(xí)對(duì)子查詢的屬性進(jìn)行編碼，將執(zhí)行計(jì)劃轉(zhuǎn)換為強(qiáng)化學(xué)習(xí)中的動(dòng)作表示，并使用一個(gè)神經(jīng)網(wǎng)絡(luò)NNST得到在新動(dòng)作下新的子查詢計(jì)劃的表示. 同時(shí)使用另一個(gè)神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)每個(gè)狀態(tài)下子查詢的基數(shù)，并根據(jù)預(yù)測(cè)的基數(shù)利用強(qiáng)化學(xué)習(xí)優(yōu)化查詢. 2019 年，Ortiz 等人[6]提出使用循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network, RNN）模型預(yù)測(cè)查詢的基數(shù)，該模型將一個(gè)SQL 語句看作一個(gè)序列. Ortiz 等人[6]的這2 個(gè)研究可以很好地適配不同長度、不同類型的查詢操作，但這2 個(gè)技術(shù)僅專注于解決左深度支持的查詢計(jì)劃，而對(duì)于一些其他結(jié)構(gòu)支持的查詢計(jì)劃無法直接適用.

為了解決使用神經(jīng)網(wǎng)絡(luò)方法建模整個(gè)數(shù)據(jù)庫模式帶來的數(shù)據(jù)稀疏問題，Woltmann 等人[4]使用神經(jīng)網(wǎng)絡(luò)為不同且固定的查詢連接條件訓(xùn)練了一個(gè)局部模型Local NN. 該局部模型的思想使基數(shù)估計(jì)模型可以更好地表示出數(shù)據(jù)之間的相關(guān)性，然而這種訓(xùn)練方式消耗較大. 不同于該模型， Kipf 等人[5]基于卷積神經(jīng)網(wǎng)絡(luò)算法，同時(shí)基于采樣的思想來學(xué)習(xí)多表謂詞關(guān)聯(lián)性，并為整個(gè)查詢訓(xùn)練了一個(gè)全局模型MSCN用于估計(jì)連接查詢的基數(shù)以減小訓(xùn)練消耗.

2.2.2 基于樹結(jié)構(gòu)的基數(shù)估計(jì)模型

樹結(jié)構(gòu)由于其模型參數(shù)較小、運(yùn)行時(shí)間快的特點(diǎn)被廣泛關(guān)注. 為了使模型具有學(xué)習(xí)能力，同時(shí)模型參數(shù)或運(yùn)行時(shí)間又不會(huì)太大，樹結(jié)構(gòu)這種模型結(jié)構(gòu)被應(yīng)用到基數(shù)估計(jì)模型中用于增量學(xué)習(xí)查詢負(fù)載的特征屬性. 在基于樹結(jié)構(gòu)的基數(shù)估計(jì)中，Malik 等人[7]率先提出了一種“黑盒”的方法來估計(jì)查詢基數(shù)，在不了解查詢執(zhí)行基數(shù)和數(shù)據(jù)分布的情況下提供了準(zhǔn)確的估計(jì).該黑盒的主要思想是將查詢分組到固定的句法組中，并使用基于樹狀模型等機(jī)器學(xué)習(xí)技術(shù)來學(xué)習(xí)每個(gè)句法組的查詢結(jié)果大小的分布，并編碼了查詢的屬性、運(yùn)算符、模型參數(shù)、聚合和用戶自定義函數(shù)的參數(shù)，該方法顯著提高了Open SkyQuery 中的緩存性能.

為了適應(yīng)不同結(jié)構(gòu)的查詢負(fù)載，Sun 等人[8]提出了一個(gè)基于樹結(jié)構(gòu)模型的端到端成本估計(jì)學(xué)習(xí)框架，該框架可以同時(shí)估計(jì)成本和基數(shù). 該研究提出了有效的特征提取和編碼技術(shù). 其中，在特征提取時(shí)考慮了查詢和物理操作，并將特征嵌入到樹結(jié)構(gòu)模型中；在特征編碼時(shí)提出了一種有效的字符串值編碼技術(shù)，可以提高謂詞匹配的泛化能力. 同時(shí)，該研究提出了一種基于模式（pattern）的方法，用于覆蓋所有的字符串值并編碼其嵌入.

Dutt 及其團(tuán)隊(duì)分別于2019 年[9]和2020 年[28]提出了基于XGboost 算法的基數(shù)估計(jì)模型. 文獻(xiàn)[9]為多列范圍查詢提出了一種輕量級(jí)的選擇度估計(jì)方法，并提出了基于樹模型和基于神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)的選擇度. 該研究首先將范圍查詢編碼為范圍特征，并使用啟發(fā)式的基數(shù)估計(jì)器為單屬性直方圖中的信息計(jì)算查詢的選擇度來作為額外特征，并將2 類特征輸入到樹結(jié)構(gòu)或神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的回歸模型中進(jìn)行訓(xùn)練.為解決訓(xùn)練集收集耗時(shí)長、模型構(gòu)建時(shí)間長和為大型數(shù)據(jù)集計(jì)算選擇度標(biāo)簽代價(jià)大的問題，從構(gòu)建訓(xùn)練數(shù)據(jù)的角度上，文獻(xiàn)[28]提出了一個(gè)基于霍夫?。℉oeffding）不等式的生成近似選擇度標(biāo)簽策略，用于增量標(biāo)記數(shù)據(jù). 該研究首先隨機(jī)選擇少量的訓(xùn)練數(shù)據(jù)并標(biāo)記，然后將查詢特征和單表的選擇度特征輸入到XGBoost 模型中計(jì)算查詢的選擇度，若模型的Q-error 值低于閾值的置信區(qū)間，則模型停止訓(xùn)練.此研究在使用回歸模型預(yù)測(cè)查詢基數(shù)的同時(shí)自動(dòng)確定了訓(xùn)練數(shù)據(jù)規(guī)模大小.

2.2.3 NoSQL 中查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型

以上的研究聚焦于傳統(tǒng)的SQL 查詢語句，模型適用于低維數(shù)據(jù)的處理，但對(duì)于NoSQL 中高維的圖片、文本數(shù)據(jù)以及復(fù)雜的SPARQL 查詢，以上模型不能直接適用. Sun 等人[27]將SQL 查詢對(duì)象擴(kuò)展到了圖片、文本等更高維的數(shù)據(jù)，基于神經(jīng)網(wǎng)絡(luò)算法并結(jié)合全局和局部模型的思想，針對(duì)高維數(shù)據(jù)的相似性查詢和連接任務(wù)設(shè)計(jì)了一個(gè)基數(shù)估計(jì)模型GL，用于平衡模型數(shù)量和模型參數(shù)規(guī)模. 該模型提出了查詢分割和數(shù)據(jù)分割2 個(gè)策略，盡管僅使用了簡單的神經(jīng)網(wǎng)絡(luò)模型進(jìn)行特征編碼和基數(shù)估計(jì)，但其效果顯著. 該模型有效解決了神經(jīng)網(wǎng)絡(luò)方法中的數(shù)據(jù)饑餓問題，提高了高維數(shù)據(jù)在相似性查詢和連接操作中的準(zhǔn)確率. 雖然此模型相對(duì)于以往基于神經(jīng)網(wǎng)絡(luò)的模型，模型規(guī)模和參數(shù)量下降，但該模型的訓(xùn)練和預(yù)訓(xùn)練的時(shí)間仍然較長.

此外，傳統(tǒng)SQL 查詢的基數(shù)估計(jì)模型同樣不能直接適用于語義網(wǎng)底層數(shù)據(jù)模型資源描述框架的查詢語言SPARQL. 基于此挑戰(zhàn)，Hasan[41]提出了利用機(jī)器學(xué)習(xí)技術(shù)預(yù)測(cè) SPARQL 查詢的執(zhí)行時(shí)間. 該工作采用支持向量回歸模型作為基數(shù)估計(jì)模型，并使用圖編輯距離（graph edit distance，GED）方法提取SPARQL查詢輔助的特征屬性. 但是，當(dāng)訓(xùn)練數(shù)據(jù)集很大的前提下，GED 的計(jì)算非常耗時(shí)，且系統(tǒng)規(guī)模較大.

針對(duì)這一問題，Zhang 等人[42]首先定義了SPARQL的代數(shù)特征和基本圖模型2 類特征，該特征分別代表了查詢算子的出現(xiàn)次數(shù)、層次信息和查詢子集，并從現(xiàn)有的基準(zhǔn)查詢模板中挑選出具有代表性的模板，將每個(gè)模板生成的查詢作為目標(biāo)查詢.然后根據(jù)圖映射的方式建模查詢和目標(biāo)查詢的基本圖模型，并通過計(jì)算兩者之間的GED 來減少計(jì)算量. 此外，該研究使用增量學(xué)習(xí)的方式進(jìn)行特征選擇，并驗(yàn)證了k近鄰算法相比于支持向量回歸算法更適合作為SPARQL 基數(shù)估計(jì)的模型. 雖然該研究在減少計(jì)算量上做了一些改進(jìn)，但固定特征數(shù)量會(huì)損失一定的估計(jì)準(zhǔn)確性.

由于SPARQL 中的三元組之間存在許多（自）連接，因此SPARQL 查詢估計(jì)不應(yīng)該基于連接一致性假設(shè)[43-44]. 為了遵循這個(gè)規(guī)則，同時(shí)適用于SPARQL查詢中的多種類型的查詢模式[45-46]，例如星形或鏈?zhǔn)讲樵兡Ｊ?，Davitkova 等人[47]提出了一個(gè)用于資源描述框架（resource description framework，RDF）圖中基數(shù)估計(jì)的學(xué)習(xí)模型框架LMKG. 具體來說，模型LMKG提出了一個(gè)子圖編碼方式SG-Encoding，該編碼方式實(shí)現(xiàn)了在稠密空間中表示各種子圖模式，從而可以適用各種查詢模式. 同時(shí)，LMKG 提供了一種無監(jiān)督的自回歸模型和一個(gè)基于深度神經(jīng)網(wǎng)絡(luò)的監(jiān)督模型來進(jìn)行基數(shù)估計(jì)，以適應(yīng)不同的查詢輸入. 該研究通過學(xué)習(xí)子圖模型之間的相關(guān)性而不是三元組之間的相關(guān)性，打破了連接一致性假設(shè)，同時(shí)該技術(shù)通過采樣的方法來生成訓(xùn)練數(shù)據(jù)，緩解了處理大量數(shù)據(jù)耗時(shí)長的問題.

2.3 小 結(jié)

本文首先給出了查詢驅(qū)動(dòng)的基數(shù)估計(jì)的一般性建模路線，詳細(xì)分析了查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)中相關(guān)的模型，這些模型使用了不同的編碼方式，將查詢負(fù)載編碼為不同的特征，從而建立查詢與數(shù)據(jù)庫中列屬性和表之間的聯(lián)系，以支持不同的查詢操作.同時(shí)，這些模型基于不同的監(jiān)督學(xué)習(xí)方法，建立了查詢及其基數(shù)之間的映射. 此外，在包括高維圖像、文本和復(fù)雜的SPARQL 三元組的NoSQL 查詢中，查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型也得到了很好的應(yīng)用. 本文對(duì)比了2 類查詢驅(qū)動(dòng)的基數(shù)估計(jì)中的代表模型[3,5,9,28]，以及NoSQL 代表模型[27,47]，如表2 所示. 基于神經(jīng)網(wǎng)絡(luò)的基數(shù)估計(jì)技術(shù)相較于基于樹結(jié)構(gòu)的基數(shù)估計(jì)技術(shù)，由于神經(jīng)網(wǎng)絡(luò)優(yōu)越的數(shù)據(jù)擬合能力，其估計(jì)準(zhǔn)確性較高，但模型參數(shù)較大，導(dǎo)致運(yùn)行時(shí)間較長. 基于樹結(jié)構(gòu)的基數(shù)估計(jì)技術(shù)由于使用了增量學(xué)習(xí)，其模型參數(shù)相對(duì)較少，但以損失精度為代價(jià). 從表2 中可以看到，查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型的核心在于編碼查詢的特征是什么及使用哪種回歸模型建模. 查詢驅(qū)動(dòng)的基數(shù)估計(jì)方法在準(zhǔn)確度上取得了良好的效果，使用查詢特征編碼器容易建模表之間、列之間的關(guān)系，并支持多表連接估計(jì).

Table 2 Comparison of Query-Driven Cardinality Estimation Models表2 查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型比較

3 數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)

數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)的核心是擬合數(shù)據(jù)庫D中N維（即表的N列）數(shù)據(jù)的聯(lián)合分布函數(shù)fθ(D)=P(A1,A2,…,AN)，其中 θ表示模型需要學(xué)習(xí)的參數(shù)，Ai表示數(shù)據(jù)庫表中的列屬性. 數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)通常使用不同的采樣策略，通過不同的監(jiān)督/無監(jiān)督的模型直接建模表中所有列的關(guān)系. 首先，本文基于已有的數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)歸納出數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)的一般性建模流程；然后對(duì)不同數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型進(jìn)行了詳細(xì)的介紹；最后對(duì)相關(guān)模型進(jìn)行了對(duì)比和總結(jié).

3.1 數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)建模流程

數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)的核心思想是建立一個(gè)數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型，其一般性的建模流程如圖3 所示，分為3 部分[23-24]：輸入、輸出和模型建立.

Fig. 3 General modeling flow for data-driven cardinality estimation圖3 數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)的一般性建模流程

1）輸入

輸入數(shù)據(jù)庫D、查詢q. 例如，對(duì)于數(shù)據(jù)驅(qū)動(dòng)的代表模型Naru[17]，其模型的輸入為數(shù)據(jù)庫D和查詢q.其中，在模型推理階段需要輸入查詢q，而訓(xùn)練階段僅需要給定數(shù)據(jù)庫（表）中存儲(chǔ)的數(shù)據(jù).

2）輸出

輸出N維數(shù)據(jù)的聯(lián)合概率分布P以及查詢估計(jì)的選擇度.

3）模型建立

①模型訓(xùn)練. 如圖3 中粗實(shí)線條箭頭所示，數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型包含2 個(gè)模塊：數(shù)據(jù)采樣和數(shù)據(jù)分布模型. 模型可選擇不同的數(shù)據(jù)采樣方法，并基于數(shù)據(jù)庫中的數(shù)據(jù)采樣合理規(guī)模的元組（多列數(shù)據(jù)）.在這些高維數(shù)據(jù)的基礎(chǔ)上，使用基于監(jiān)督/無監(jiān)督學(xué)習(xí)的數(shù)據(jù)分布模型擬合這些元組的分布，不斷訓(xùn)練參數(shù)θ使得模型擬合最優(yōu)的數(shù)據(jù)分布來作為整個(gè)數(shù)據(jù)庫的數(shù)據(jù)分布.

本文以模型Naru 為例來解釋數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型訓(xùn)練的流程. 首先Naru 掃描數(shù)據(jù)表，采樣合理規(guī)模的元組作為數(shù)據(jù)集，其次，Naru 編碼采樣的每個(gè)元組作為自回歸模型的輸入向量，元組在每列樣本上的數(shù)據(jù)分布作為其訓(xùn)練標(biāo)簽. 對(duì)于每個(gè)元組，自回歸模型以先前列的取值為輸入，估計(jì)當(dāng)前列的概率分布向量. 通過訓(xùn)練縮小該概率分布向量與該列實(shí)際的數(shù)據(jù)分布之間的誤差，從而得到一個(gè)可以處理所有列之間關(guān)系的自回歸函數(shù).

②模型推理. 如圖3 中細(xì)實(shí)線條箭頭所示，基數(shù)估計(jì)在推理階段同樣需要經(jīng)過2 個(gè)模塊. 不同的是，數(shù)據(jù)分布模型已經(jīng)確定，根據(jù)查詢q，經(jīng)過查詢解析器后，根據(jù)數(shù)據(jù)表的信息（例如列的編碼信息、統(tǒng)計(jì)信息等），采樣出若干條滿足查詢條件的元組. 將這些元組輸入到數(shù)據(jù)分布模型中計(jì)算元組對(duì)應(yīng)列的聯(lián)合概率分布，即為該查詢q的選擇度，從而計(jì)算出基數(shù).

同理以模型Naru 為例來解釋數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型推理的流程. 對(duì)于等值查詢q1，首先Naru 根據(jù)q1和每列的數(shù)據(jù)分布進(jìn)行采樣生成元組，并對(duì)這些元組進(jìn)行編碼. 對(duì)于范圍查詢q2，Naru 提出了一個(gè)漸進(jìn)式采樣的方式，在已知數(shù)據(jù)分布的情況下對(duì)范圍涵蓋的樣本進(jìn)行采樣，并將采樣出的元組轉(zhuǎn)換為等值查詢這種點(diǎn)查詢. 將編碼后的樣本向量輸入到訓(xùn)練好的自回歸模型中產(chǎn)生n個(gè)條件概率，并將這n個(gè)條件概率相乘即為查詢q的選擇度，從而計(jì)算出其基數(shù).

3.2 數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)相關(guān)模型

數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型的挑戰(zhàn)是如何無需基于多列獨(dú)立假設(shè)來建模單表多列之間的關(guān)系，以及多表連接中表與表之間的依賴關(guān)系. 從是否使用監(jiān)督學(xué)習(xí)的角度來看，Heimel 等人[15]使用核函數(shù)進(jìn)行監(jiān)督學(xué)習(xí)，Park 等人[16]使用均勻混合模型建模多列之間的關(guān)系；文獻(xiàn)[17?20, 48?49]使用無監(jiān)督學(xué)習(xí)模型建模數(shù)據(jù)分布模型；文獻(xiàn)[17?19]基于自回歸模型擬合數(shù)據(jù)分布； Halford 等人[48]基于貝葉斯網(wǎng)絡(luò)進(jìn)行建模；Liu 等人[49]提出了基于多維直方圖的模型用于范圍查詢的基數(shù)估計(jì). 此外，目前大多數(shù)文獻(xiàn)[15-18,48-49]專注于建模多列之間的依賴關(guān)系，而表之間的關(guān)系建模建立在多表獨(dú)立假設(shè)之上. 最新的文獻(xiàn)[19]基于自回歸模型，以及Hilprecht 等人[20]利用和積網(wǎng)絡(luò)建模了表之間的關(guān)系，很好地補(bǔ)充了查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型中多表查詢的相關(guān)工作. 因此，本文將模型根據(jù)是否建模多列之間還是多表之間的關(guān)系，分為面向多列連接查詢的基數(shù)估計(jì)模型和面向多表連接查詢的基數(shù)估計(jì)模型.

3.2.1 面向多列連接查詢的基數(shù)估計(jì)模型

模型Feedback-KDE[15]將基于高斯核函數(shù)的密度估計(jì)器應(yīng)用到基數(shù)估計(jì)技術(shù)中，用于估計(jì)單表多列查詢的選擇度. 該模型首先從數(shù)據(jù)庫表中隨機(jī)采樣合理規(guī)模的元組，并基于高斯核函數(shù)初始化高斯密度模型的帶寬. 接著使用訓(xùn)練集中的查詢和其對(duì)應(yīng)的真實(shí)基數(shù)訓(xùn)練高斯模型，來優(yōu)化高斯核的帶寬. 因此，模型Feedback-KDE 是一個(gè)有監(jiān)督訓(xùn)練的模型，其為每種連接類型訓(xùn)練一個(gè)高斯模型. 當(dāng)輸入一個(gè)新的查詢后，F(xiàn)eedback-KDE 首先解析該查詢的連接類型，并根據(jù)其連接類型找到對(duì)應(yīng)的高斯模型.

模型QuickSel[16]使用均勻混合模型來表示數(shù)據(jù)的分布，從而擬合給定查詢的基數(shù). 該模型支持范圍查詢，其查詢范圍由查詢中的謂詞定義. 首先QuickSel從查詢范圍中隨機(jī)采樣數(shù)據(jù)，并建立統(tǒng)一的模型. 然后計(jì)算真實(shí)查詢范圍和選擇樣本中的范圍之間的重疊度并通過二次規(guī)劃優(yōu)化權(quán)值. 最后根據(jù)混合密度函數(shù)計(jì)算累計(jì)分布（選擇度）. 當(dāng)輸入一個(gè)新的查詢后，QuickSel 首先解析該查詢的連接類型，然后根據(jù)其連接類型找到對(duì)應(yīng)的混合模型.

作為自回歸模型中具有代表性的模型，模型Naru[17]沒有引入列的獨(dú)立性這一假設(shè)，提出使用自回歸模型學(xué)習(xí)查詢q每列樣本在前一列樣本條件下的條件概率分布（選擇度），將所有列的選擇度相乘得到查詢q的選擇度. 模型DLM[18]同樣是基于自回歸模型，與Naru 不同的是，該模型將數(shù)據(jù)表中的一行數(shù)據(jù)看作一個(gè)序列，并將序列表示為由多個(gè)二進(jìn)制向量組成. 同Naru 一樣，DLM 同樣支持點(diǎn)查詢和范圍查詢.對(duì)于點(diǎn)查詢操作，DLM 將查詢中二進(jìn)制向量的條件概率相乘來估計(jì)基數(shù)；對(duì)于范圍查詢，DLM 使用了重要性采樣策略進(jìn)行采樣.

不同于基于自回歸的模型，模型Extended Chow-Liu trees[48]從貝葉斯網(wǎng)絡(luò)模型角度出發(fā)，將單表多列之間的依賴關(guān)系使用貝葉斯網(wǎng)絡(luò)轉(zhuǎn)換為條件概率.該模型啟發(fā)式地選擇Chow-Liu 樹作為最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，將高維數(shù)據(jù)聯(lián)合分布轉(zhuǎn)換為多個(gè)2 維數(shù)據(jù)的條件概率分布. 此外，該模型提出了一個(gè)帶有間隔的等高條件概率分布，用于減少存儲(chǔ)條件概率分布的代價(jià). 以等值查詢?yōu)槔?，首先解析查詢中包含的謂詞；其次在構(gòu)建好的Chow-Liu 樹中，根據(jù)涉及到的列抽取Steiner 樹；最后使用變量消除算法計(jì)算其選擇度，從而得到基數(shù). 同時(shí)，此模型同樣適合單表的范圍查詢.

為了降低多維數(shù)據(jù)在查詢估計(jì)中的查詢成本，Liu 等人[49]提出了以RMI[50]的思想將MEH[51]轉(zhuǎn)換為可學(xué)習(xí)的多維直方圖模型LHist 來學(xué)習(xí)數(shù)據(jù)庫的空間概要. LHist 為一個(gè)d層完全K叉樹，其中d為數(shù)據(jù)的維度，K是在每維的分割數(shù). 樹中的每個(gè)節(jié)點(diǎn)都為一個(gè)可訓(xùn)練的回歸模型，用于預(yù)測(cè)輸入此節(jié)點(diǎn)數(shù)據(jù)的索引，并輸出該數(shù)據(jù)在下一層的節(jié)點(diǎn)的位置. 以范圍查詢?yōu)槔?dāng)輸入一個(gè)新的范圍查詢后，LHist 首先編碼其范圍謂詞，并將該查詢轉(zhuǎn)換為一個(gè)超矩形，然后通過LHist 找到葉子節(jié)點(diǎn)，并計(jì)算范圍謂詞向量對(duì)應(yīng)的索引值，最終將不同列上2 個(gè)索引值的差加和得到查詢的基數(shù).

3.2.2 面向多表連接查詢的基數(shù)估計(jì)模型

模型NeuroCard[19]可以看作模型Naru 多表連接的擴(kuò)展版本，該模型在所有列連接后的大表上通過使用加權(quán)抽樣的方式均勻地選擇樣本并分批掃描大表，對(duì)于每批掃描得到的結(jié)果行，NeuroCard 首先編碼每個(gè)屬性值的嵌入表示輸入到模型中. 其次模型更新自回歸模型的參數(shù)并進(jìn)行訓(xùn)練. 同Naru 模型一樣，NeuroCard 同樣考慮了點(diǎn)查詢和范圍查詢. 對(duì)于范圍查詢，同樣使用了漸進(jìn)式采樣策略.

模型DeepDB[20]與模型Naru 思想相似，同樣是要學(xué)習(xí)所有列的聯(lián)合概率分布. 不同的是，DeepDB 基于和積網(wǎng)絡(luò)建模數(shù)據(jù)分布模型并支持多表連接. 該模型首先將數(shù)據(jù)庫中所有的表連接為一個(gè)大表作為數(shù)據(jù)集，其次將該數(shù)據(jù)集中的樣本按行聚類為若干個(gè)具有相似分布的數(shù)據(jù)組，然后將數(shù)據(jù)組中的樣本按列分割成子節(jié)點(diǎn). 對(duì)于同一組的葉子節(jié)點(diǎn)，使用一個(gè)乘積節(jié)點(diǎn)聚合其估計(jì)的選擇度. 其次，使用加和節(jié)點(diǎn)組合成不同組的數(shù)據(jù). DeepDB 通過擬合乘積節(jié)點(diǎn)中數(shù)據(jù)的聯(lián)合分布概率，訓(xùn)練與加和節(jié)點(diǎn)之間邊的權(quán)重，用于建模每個(gè)分組分布對(duì)整體聯(lián)合分布的影響.

3.3 小 結(jié)

針對(duì)數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)，本文首先給出了數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)的一般性建模流程，其次分析了面向多列和多表連接查詢的代表模型. 這些模型使用了不同的采樣方式，將查詢語句在數(shù)據(jù)表中相應(yīng)的元組進(jìn)行采樣，輸入到不同的數(shù)據(jù)分布模型中. 而不同的數(shù)據(jù)分布模型基于不同的學(xué)習(xí)模型，建模多維數(shù)據(jù)的聯(lián)合分布概率，從而建立起查詢、列和表之間的關(guān)聯(lián). 本文從多個(gè)角度對(duì)比了數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)中的代表模型，如表3 所示. 從表3 中可以看到，數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型的核心在于采用何種采樣方式處理查詢的元組，以及采用哪種數(shù)據(jù)分布模型建立多列、多表之間的關(guān)系. 相對(duì)于查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型，數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型擁有更小的訓(xùn)練開銷，但在數(shù)據(jù)庫刪除和更新等操作中表現(xiàn)不佳.

Table 3 Comparison of Data-Driven Cardinality Estimation Models表3 數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型比較

4 混合模型的基數(shù)估計(jì)技術(shù)

查詢驅(qū)動(dòng)和數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)各有利弊，而目前僅有少量研究[52]將兩者之中的優(yōu)點(diǎn)結(jié)合起來，提出將查詢驅(qū)動(dòng)和數(shù)據(jù)驅(qū)動(dòng)結(jié)合的混合模型的基數(shù)估計(jì)技術(shù)，并相互彌補(bǔ)這2 類模型的一些缺點(diǎn). 其核心思想是建立一個(gè)混合查詢負(fù)載和數(shù)據(jù)分布的基數(shù)估計(jì)模型fθ(q,C,D)，來同時(shí)處理和學(xué)習(xí)查詢負(fù)載與數(shù)據(jù)樣本中的信息，其中 θ表示模型需要學(xué)習(xí)的參數(shù).本文給出了混合模型的一般性建模流程，同時(shí)對(duì)混合模型的基數(shù)估計(jì)技術(shù)中具體的混合模型進(jìn)行了介紹.

混合模型的一般性建模流程包含了查詢驅(qū)動(dòng)和數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)的建模流程，同樣定義為輸入、輸出和模型建立3 個(gè)部分，其一般的建模流程如圖4所示.

Fig. 4 General modeling flow for hybrid model cardinality estimation圖4 混合模型基數(shù)估計(jì)的一般性建模流程

1）輸入

涵蓋了查詢驅(qū)動(dòng)的輸入和數(shù)據(jù)驅(qū)動(dòng)的輸入，即輸入為數(shù)據(jù)集DStrain/test{〈q,C〉}、模型約束參數(shù) ?、數(shù)據(jù)庫D和查詢q.

2）輸出

在數(shù)據(jù)庫D中執(zhí)行查詢q估計(jì)的基數(shù).

3）模型建立

①模型訓(xùn)練. 如圖4 中粗實(shí)線條箭頭所示，混合分析模型共包含3 個(gè)模塊：查詢特征編碼器、數(shù)據(jù)采樣和混合學(xué)習(xí)模型. 首先模型遵循查詢驅(qū)動(dòng)的基數(shù)估計(jì)中的建模流程，將輸入的查詢q進(jìn)行編碼. 同時(shí)遵循數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)中的建模流程，將數(shù)據(jù)表中的數(shù)據(jù)采樣出一定規(guī)模的元組. 其次，利用查詢特征編碼器和數(shù)據(jù)采樣2 個(gè)模塊進(jìn)一步加工查詢負(fù)載和數(shù)據(jù)樣本的信息. 具體來說，既可以通過將元組輸入到查詢特征編碼器中進(jìn)行元組編碼后作為查詢q特征屬性的一部分，又可以通過查詢q來采樣更加精準(zhǔn)的元組以擬合數(shù)據(jù)表中數(shù)據(jù)的分布. 將真實(shí)的基數(shù)和采樣后的元組輸入到混合學(xué)習(xí)模型中，使用監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的損失函數(shù)同時(shí)優(yōu)化模型的學(xué)習(xí)參數(shù) θ.

UAE 模型[52]是第一個(gè)同時(shí)考慮查詢驅(qū)動(dòng)和數(shù)據(jù)驅(qū)動(dòng)的模型，其既包含數(shù)據(jù)驅(qū)動(dòng)的無監(jiān)督學(xué)習(xí)，又擁有查詢驅(qū)動(dòng)的有監(jiān)督學(xué)習(xí)的能力. 該模型創(chuàng)造性地在模型Naru[17]的基礎(chǔ)上融合了查詢驅(qū)動(dòng)的回歸模型，共同學(xué)習(xí)數(shù)據(jù)分布概率參數(shù). 本文以UAE 模型為例來解釋混合模型分析的訓(xùn)練流程. UAE 分為2 個(gè)部分UAE-D 和UAE-Q. 其中UAE-D 為數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型Naru，直接學(xué)習(xí)數(shù)據(jù)表中列數(shù)據(jù)之間的聯(lián)合分布概率及得到數(shù)據(jù)分布在Naru 的損失. 同時(shí)，將查詢及其真實(shí)的選擇度作為輸入，首先使用與Naru同樣的漸進(jìn)式采樣策略，將查詢的元組進(jìn)行采樣，并使用One-Hot 編碼為向量；其次使用混合模型將不可微的采樣元組向量轉(zhuǎn)換為可微的元組向量輸入到Naru 的自回歸模型中得到預(yù)測(cè)的選擇度，并分析與真實(shí)選擇度之間的誤差和計(jì)算損失值. UAE 將2 部分損失加和作為總損失，然后使用梯度更新的方式來優(yōu)化自回歸模型的參數(shù).

②模型推理. 如圖4 中細(xì)實(shí)線條箭頭所示，基數(shù)估計(jì)在推理階段同樣需要經(jīng)過3 個(gè)模塊. 不同的是，混合學(xué)習(xí)模型的參數(shù)已經(jīng)確定. 根據(jù)查詢q可以得到其編碼后的向量表示、采樣的元組及其向量表示這3 個(gè)元素，將這3 個(gè)元素根據(jù)混合學(xué)習(xí)模型的設(shè)計(jì)，全部或部分輸入到混合模型中直接估計(jì)出查詢q的基數(shù).

同樣以UAE 為例，UAE 將查詢q采樣的元組輸入到自回歸模型中得到估計(jì)的選擇度，從而得到估計(jì)的基數(shù). 這種混合模型的基數(shù)估計(jì)技術(shù)可以同時(shí)處理新增的數(shù)據(jù)以及具有新分布查詢負(fù)載的情況.對(duì)于增量數(shù)據(jù)，僅需要最小化UAE-D 即對(duì)數(shù)據(jù)驅(qū)動(dòng)的損失函數(shù)進(jìn)行增量訓(xùn)練. 而UAE 與訓(xùn)練查詢負(fù)載相比，具有不同分布的查詢，僅需要最小化UAE-Q 即查詢驅(qū)動(dòng)的損失函數(shù)進(jìn)行增量訓(xùn)練.

5 未來研究方向和展望

盡管基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)已經(jīng)涌現(xiàn)出大量的研究，但其仍面臨著4 個(gè)挑戰(zhàn)：

1）模型的訓(xùn)練成本和模型的可解釋性. 針對(duì)查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型，這類方法建模任務(wù)簡單，占用空間小，僅使用簡單的回歸模型即可達(dá)到不錯(cuò)的效果. 然而，由于在收集訓(xùn)練數(shù)據(jù)時(shí)構(gòu)建模型時(shí)間長，所以這類模型比較耗時(shí)，即使在文獻(xiàn)[28]提出了方法來減輕開銷，也以損失一定的精度為代價(jià). 此外，由于建模技術(shù)基于監(jiān)督學(xué)習(xí)，其模型的核心仍然是一個(gè)“黑盒”模型，因此模型的可解釋性較弱. 因此，模型的訓(xùn)練成本和模型的可解釋性是查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型面臨的兩大重要挑戰(zhàn).

2）多表之間的復(fù)雜關(guān)系. 針對(duì)數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型，這類方法相比于查詢驅(qū)動(dòng)的技術(shù)估計(jì)方法，其訓(xùn)練開銷小，僅需要根據(jù)原始數(shù)據(jù)進(jìn)行訓(xùn)練，且支持的查詢范圍更廣泛. 雖然已有研究已經(jīng)對(duì)多表之間的關(guān)系進(jìn)行了建模并取得了一定的進(jìn)展，但是這些研究均是直接將多個(gè)表連接為一個(gè)大表，進(jìn)而轉(zhuǎn)換為多列連接查詢的思想進(jìn)行建模，因此對(duì)于多表之間復(fù)雜關(guān)系的探索依然不足. 因此，多表之間的復(fù)雜關(guān)系是數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型面臨的一個(gè)重要挑戰(zhàn).

3）動(dòng)態(tài)變化的數(shù)據(jù)庫環(huán)境. 無論是查詢驅(qū)動(dòng)還是數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型，目前的研究均不能適應(yīng)動(dòng)態(tài)變化的數(shù)據(jù)庫環(huán)境[24]. 由于查詢驅(qū)動(dòng)的基數(shù)模型繼承了監(jiān)督學(xué)習(xí)的一些固有缺陷，使模型不適用于沒有見過的查詢，因此在頻繁更新的數(shù)據(jù)庫系統(tǒng)中該類模型估計(jì)的誤差較大. 對(duì)于數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型，由于其直接擬合數(shù)據(jù)庫中的數(shù)據(jù)分布，因此該類模型可以支持新的查詢. 但是，這類方法仍然不能支持?jǐn)?shù)據(jù)的刪除和更新等動(dòng)態(tài)操作. 因此，支持動(dòng)態(tài)變化的數(shù)據(jù)庫環(huán)境是數(shù)據(jù)驅(qū)動(dòng)和查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型面臨的一個(gè)共同挑戰(zhàn).

4）基數(shù)估計(jì)benchmark 和評(píng)價(jià)體系. 目前，對(duì)已有方法進(jìn)行評(píng)價(jià)的文獻(xiàn)[23-24]仍然不豐富，所以設(shè)計(jì)benchmark 對(duì)已有方法進(jìn)行對(duì)比和評(píng)價(jià)也是基數(shù)估計(jì)領(lǐng)域中研究的一個(gè)重要挑戰(zhàn).

針對(duì)以上分析，基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)的未來研究方向可以包含4 個(gè)方面：

1）考慮使用可解釋的增量學(xué)習(xí)方法. 如何降低學(xué)習(xí)模型的成本和如何提高模型的可解釋性是查詢驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)研究的兩大方向. 文獻(xiàn)[28]證明了增量學(xué)習(xí)可以降低查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型的學(xué)習(xí)成本，但其估計(jì)準(zhǔn)確性有所下降. 因此，探索可以提升估計(jì)精度的增量學(xué)習(xí)模型是降低模型學(xué)習(xí)成本有效且直觀的解決方式. 隨著可解釋模型在人工智能領(lǐng)域的發(fā)展，機(jī)器學(xué)習(xí)模型逐漸從“黑盒”走向“透明”. 因此，將增量學(xué)習(xí)與可解釋性模型相結(jié)合有助于探索一個(gè)全新的基于增量學(xué)習(xí)且擁有可解釋性的查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型.

2）建模多表之間的復(fù)雜關(guān)系. 針對(duì)于在數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)中仍然缺乏探索的多表復(fù)雜關(guān)系，應(yīng)當(dāng)考慮設(shè)計(jì)可以建模多表之間關(guān)系的數(shù)據(jù)分布模型，以更好地估計(jì)多表連接查詢的基數(shù).

3）探索更加優(yōu)越的混合模型. 混合查詢驅(qū)動(dòng)和數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)技術(shù)可以結(jié)合兩者優(yōu)點(diǎn)，互補(bǔ)兩者的缺點(diǎn)，文獻(xiàn)[52]證明了混合模型的估計(jì)效果優(yōu)于獨(dú)立的查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型和數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型，但是混合模型目前成果較少，因此結(jié)合哪些機(jī)器學(xué)習(xí)模型或者數(shù)據(jù)結(jié)構(gòu)，如何結(jié)合查詢驅(qū)動(dòng)的基數(shù)估計(jì)模型和數(shù)據(jù)驅(qū)動(dòng)的基數(shù)估計(jì)模型也是未來研究的熱點(diǎn).

4）加快機(jī)器學(xué)習(xí)模型訓(xùn)練速度應(yīng)部署到實(shí)際數(shù)據(jù)庫進(jìn)行應(yīng)用. 由于基于機(jī)器學(xué)習(xí)的模型更新速度較慢，無法適應(yīng)頻繁更新的動(dòng)態(tài)數(shù)據(jù)庫環(huán)境，距離實(shí)際落地應(yīng)用還有一定的差距[24]. 因此，基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)作為一個(gè)重要的研究方向應(yīng)以實(shí)際落地應(yīng)用為目標(biāo)進(jìn)行設(shè)計(jì)，探索可以加快機(jī)器學(xué)習(xí)模型訓(xùn)練速度的算法，以減少模型參數(shù)調(diào)優(yōu)的時(shí)間和提高模型查詢效率，最終適應(yīng)動(dòng)態(tài)變化的數(shù)據(jù)庫環(huán)境.

6 總 結(jié)

本文首先介紹了基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)的相關(guān)背景；接著介紹了基數(shù)估計(jì)的相關(guān)定義、特征編碼技術(shù)以及基數(shù)估計(jì)技術(shù)中的分類體系；然后分別從查詢驅(qū)動(dòng)、數(shù)據(jù)驅(qū)動(dòng)和混合模型的角度出發(fā)，給出了3 類基數(shù)估計(jì)的一般性建模流程；并基于建模流程，分別討論了查詢驅(qū)動(dòng)、數(shù)據(jù)驅(qū)動(dòng)和混合模型這3 類基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)的代表性模型，并總結(jié)了其利弊；最后，本文還討論了基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)中存在的挑戰(zhàn)和未來的研究方向. 基于機(jī)器學(xué)習(xí)的基數(shù)估計(jì)技術(shù)近年來涌現(xiàn)了大量的研究，但距離落地到實(shí)際動(dòng)態(tài)變化的數(shù)據(jù)庫環(huán)境還有一定的差距，未來會(huì)有更多的方法和研究成果出現(xiàn)，在數(shù)據(jù)庫實(shí)際應(yīng)用中占有一席之地.

作者貢獻(xiàn)聲明：岳文靜負(fù)責(zé)論文主要內(nèi)容的調(diào)研和撰寫,以及論文的校驗(yàn)；屈穩(wěn)穩(wěn)輔助調(diào)研相關(guān)內(nèi)容并提供指導(dǎo)意見；林寬、王曉玲對(duì)文章的結(jié)構(gòu)和內(nèi)容提供指導(dǎo)意見.