王 焱， 陳珊珊

（南京郵電大學 計算機學院， 南京 210023）

0 引 言

基數(shù)估計是數(shù)據(jù)庫查詢數(shù)據(jù)過程中的關鍵流程，數(shù)據(jù)庫的查詢優(yōu)化器根據(jù)基數(shù)估計算法的結果來選擇最終執(zhí)行計劃，所以提高基數(shù)估計的準確性對查詢優(yōu)化十分重要。

傳統(tǒng)的基數(shù)估計方法，如采樣法和直方圖等，在數(shù)據(jù)量不大、數(shù)據(jù)分布較均勻的情況下能夠獲得相對準確的結果。 然而現(xiàn)實中數(shù)據(jù)分布差異明顯，不同屬性之間往往存在一定的關聯(lián)性，數(shù)據(jù)規(guī)模也經常難以預料，基于直方圖或采樣法的基數(shù)估計準確性就會降低。 尤其是查詢中關聯(lián)到多張表，數(shù)據(jù)規(guī)模急劇增大時，計算結果的偏差會成倍增加，準確性快速下降，最終導致優(yōu)化器選擇非最優(yōu)的執(zhí)行計劃［1］。 而Leis［2］等提出基于索引的IBJS（Index-Based Join Sampling） 方法，在一定程度上解決了數(shù)據(jù)量的問題，但比較依賴于表的索引結構，較差的索引結構會導致基數(shù)估計結果也較差。

近年來，以神經網(wǎng)絡為代表的機器學習技術迅速發(fā)展，也推動了數(shù)據(jù)庫相關技術的研究，尤其是在一些復雜場景，如Li［3］等針對參數(shù)調優(yōu)的問題提出了一種基于深度強化學習的自動化調優(yōu)系統(tǒng)。 為了提高基數(shù)估計的準確性，本文采用神經網(wǎng)絡中的多頭注意力機制對表中數(shù)據(jù)列之間存在的邏輯關系進行學習，并針對SQL 語句的特征編碼算法進行研究，結合多種更細粒度的特征編碼算法，提升數(shù)據(jù)的編碼效果。 實驗結果表明該方法可以有效提高基數(shù)估計的準確率，優(yōu)化數(shù)據(jù)庫的查詢，驗證了模型的有效性。

1 相關工作

最近一些研究者已經開始將機器學習與基數(shù)估計 結 合， Kipf 等［4］提 出 了 MSCN （ Multi - Set Convolutional Network）框架，開創(chuàng)了將機器學習用于基數(shù)估計處理的先河；Karamyan 等［5］在MSCN 的基礎上進行擴展，提出了一種基于遞歸樹型的神經網(wǎng)絡框架；LingChen 等［6］則提出了一種結合算子級深度神經網(wǎng)絡的基數(shù)估計方法。

從對數(shù)據(jù)處理方式上看，目前利用機器學習來優(yōu)化基數(shù)估計的方法主要分為兩種：數(shù)據(jù)驅動（Data-Driven）和查詢驅動（Query-Driven）。 基于數(shù)據(jù)驅動的模型主要是利用深度自回歸模型（Deep Autoregressive）分析測試集中數(shù)據(jù)列的分布來計算估計值，主要缺點是其假設數(shù)據(jù)每一列都和前面列存在相關性，而現(xiàn)實中數(shù)據(jù)一些列有關，一些列之間無關，所以數(shù)據(jù)驅動模型在數(shù)據(jù)分布偏差較大時會出現(xiàn)明顯誤差［7］。 查詢驅動則主要依賴于對于查詢語句的分析和學習，使用特征化方法將查詢語句轉化為特征向量。 現(xiàn)有基于查詢驅動的方法基本都采用單熱編碼（One-Hot Encoding）、二進制編碼（Binary Encoding）等特征化的編碼方法。 本文采用基于查詢驅動的方式進行研究。

在結合機器學習應用和基數(shù)估計的過程中，Karamyan 等［5］采 用 的 RNN （ Recurrent Neural Network）模型，嚴重依賴數(shù)據(jù)的序列順序，在查詢語句含有多表連接的時候速度較慢；而Sun J 等［8］采用CNN （Convolutional Neural Network）模型，針對復雜查詢時需要構建較多的卷積核來進行特征提取，參數(shù)較多，模型復雜。 針對上述問題，本文創(chuàng)新性地采用多頭自注意力機制來對基數(shù)估計進行優(yōu)化。 注意力機制的優(yōu)點主要是不依賴于數(shù)據(jù)的序列順序，更擅長捕捉數(shù)據(jù)或特征內部的相關性，能夠充分利用和靈活捕捉數(shù)據(jù)列之間存在的邏輯關系，提高基數(shù)估計的準確性，減小估計誤差。 注意力機制（Attention Mechanism）最早由Mnih 等［9］提出，用于計算機視覺，后來慢慢擴展到其他諸多領域的研究，比如語音識別、視頻解析等。

2 模型架構和技術要點

數(shù)據(jù)庫的查詢過程中，查詢優(yōu)化部分會根據(jù)基數(shù)估計的結果來選擇最終執(zhí)行計劃。 而基于多頭自注意力機制的機器學習模型能夠根據(jù)樣本數(shù)據(jù)進行訓練和學習，找到不同列之間的內在聯(lián)系，提高基數(shù)估計的準確性，從而提高查詢效率。

現(xiàn)有基于機器學習的基數(shù)估計模型框架如圖1所示。

圖1 基于機器學習的基數(shù)估計模型框架Fig.1 Machine learning based cardinality estimation model framework

本文主要在現(xiàn)有的模型框架基礎上，對編碼和模型部分進行優(yōu)化。 為了更好地獲取數(shù)據(jù)列之間的關系，本文采用了多種編碼方式，從而在編碼環(huán)節(jié)提高對數(shù)據(jù)關系的提取；不同于其他大多模型采用的CNN 和RNN 神經網(wǎng)絡模型，本文使用多頭注意力機制作為模型主體。

2.1 查詢特征表達（Query Featurization）

查詢特征表達主要是將一條文字形式的查詢語句通過編碼轉為查詢向量，以作為后續(xù)訓練模型的輸入，所以特征表達的編碼方式十分關鍵。 與通常的單熱編碼、二進制編碼不同，為了提高特征表達編碼后得到的信息量，能夠更細粒度捕獲列之間的相關性，針對不同SQL 不同部分采用了不同的編碼方法。

一條典型的SQL 查詢語句可以分為4 個部分：查詢涉及到的表、WHERE 子句中的列、WHERE 子句中的值、JOIN 連接關系。 例如語句SELECT *FROM orders JOIN users ON orders.user_id ＝user.id WHERE order.create_time ＞＝“2022-01-01”AND user.age ＞＝25，組成部分可以表示為：表-orders，列-order.create_time 和user.age，值-“2022-01-01”和25，連接關系-orders.user_id ＝user.id。

2.1.1 表編碼（Tables Encoding）

因為可以把數(shù)據(jù)庫中的所有表看做一個無向圖（Undirected-graph）G，其中頂點是單個表，每邊連接兩個可以JOIN 的表，所以針對表編碼采用了圖嵌入的編碼方法。

2.1.2 列編碼（Columns Encoding）

對于數(shù)據(jù)表中的不同列，本文采用隨即相關系數(shù)（Randomized Dependence Coefficient，RDC） 計算出數(shù)據(jù)列之間的相關性，并設置關系閾值。 經過驗證，將相關系數(shù)的閾值取值為0.5，當RDC ＞0.5時，認為兩列相關，否則認為兩列無關；基于每兩列之間的RDC值，本文針對每個表都構建出一個有向無環(huán)圖（Directed Acyclic Graph， DAG）；最后，利用node2vec 算法進行編碼。

2.1.3 值編碼（Value Encoding）

值編碼主要是對于WHERE 子句中出現(xiàn)的值進行編碼。 先對WHERE 子句中所有的值篩選并進行格式規(guī)范化處理，轉換為范圍查詢，即a≤V（c）≤b的形式，其中V（c） 表示表V中的任意字段c，［a，b］是c的取值范圍。 具體過程為等值查詢V（c）＝x表示為x≤V（c）≤x；對于單邊范圍查詢，假設字段的范圍大小是［0，1 024］，則V（c）＞x可以表示為x ＜V（c） ≤1 024；最終對于一條含有m個字段查詢語句的值編碼，可以用向量＜ac1，bc1，ac2，bc2， … ，acm，bcm ＞表示。

2.1.4 連接編碼（Join Encoding）

連接編碼采用Joins2Vec 算法。 該算法分為3步：

（1）獲取查詢表的所有連接圖；

（2）獲得每個連接圖的上下文關系；

（3）對連接圖進行編碼和優(yōu)化。

假設分別有表T1、T2 和T3，其中T1 和T3 均與T2 存在連接關系，則獲取表T3 的JOIN 編碼過程如圖2 所示。

圖2 JOIN 編碼過程示例Fig.2 Join coding process example

本文模型特征表達原理示例如圖3 所示。

圖3 模型特征表達原理示例Fig.3 Example of model feature expression principle

2.2 多頭自注意力機制

由于自注意力機制在對特征加權處理等多方面優(yōu)勢，逐漸成為深度學習領域的熱門方向［10］。 而多頭自注意力機制是針對需要獲取多個維度特征等場景需求對注意力機制的一種優(yōu)化［11］。 多頭自注意力機制利用多個頭部采用相同的計算方式，給予不同的參數(shù)，從而從多個子空間進行特征表達，能夠捕捉到更加豐富的特征信息，其基本原理是縮放點注意力機制如圖4 所示，主要公式（1）：

圖4 縮放點積注意力機制Fig.4 Scaled dot-product attention mechanism

其中， 輸入?yún)?shù)Q（Query）、K（Key）、V（Value）均為矩陣參數(shù)，分別代表查詢矩陣、鍵矩陣和值矩陣；代表調節(jié)因子；k是矩陣K的維度；W0為轉換矩陣。

在注意力機制中Q、K、V均由同一個輸入，即由數(shù)據(jù)編碼最終生成的特征向量，經過線性變換得到。 這樣每一列都會和查詢中涉及到的其他列進行注意力計算，從而提取學習列與列之間的依賴關系。 在對QKT點乘操作后，為避免維度爆炸導致梯度消失，增加因子進行調節(jié)。 多頭注意力機制會賦予多個頭部不同的參數(shù)來進行多次的線性映射，最后拼接所有子空間的注意力值。

本文考慮到某一列可能同時和其他多個數(shù)據(jù)列之間存在關系，所以選擇多頭自注意力機制提高對于不同字段關系的特征提取效果，其原理如圖5所示。

圖5 多頭自注意力機制Fig.5 Multi-head self-attention mechanism

3 實 驗

本文實驗步驟主要分為3 步：

（1）根據(jù)IMDb 數(shù)據(jù)集生成隨機樣本數(shù)據(jù)；

（2）對樣本數(shù)據(jù)進行查詢特征編碼；

（3）將第二步得到的查詢向量表達和實際基數(shù)作為機器學習模型的輸入，然后進行模型訓練，最終得到結果。

3.1 實驗環(huán)境

實驗配置見表1。

表1 實驗配置Tab.1 Experimental configuration

3.2 數(shù)據(jù)集和訓練集生成

IMDb 是一個收集全球影視數(shù)據(jù)的數(shù)據(jù)集，主要包括名稱、演員、評論、票房、評分等信息，被廣泛應用于科學研究。

為了防止多層JOIN 產生的空間爆炸，樣本數(shù)據(jù)被限制最多包含2 層JOIN 關系。 基于IMDb 數(shù)據(jù)集，從表編碼中抽取至少含有一個連接表的表t，以t為根節(jié)點進行廣度優(yōu)先搜索找到所有可以連接的表Dt，從Dt中選擇一個表t′與t進行連接，整個過程重復［0，2］次；從每個表中抽取相應的列，根據(jù)列的類型和表中數(shù)據(jù)的范圍大小選擇值，隨機組合謂詞（＝、＜或＞）生成WHERE 子句，這樣就得到了一條完整的樣本語句；最后，實際運行語句獲得真實的查詢基數(shù)，同時排除結果為空的樣本，反復執(zhí)行上述流程，即可獲得實驗所需的數(shù)據(jù)集，總計60 000 條，其中訓練集40 000條，測試集10 000 條，驗證集10 000 條。

3.3 數(shù)據(jù)預處理

為了簡化并對輸入?yún)?shù)統(tǒng)一處理，本文對實際獲得的查詢基數(shù)進行最大-最小縮放處理。 假設一個查詢基數(shù)的集合為S ＝｛card1，card2，…，cardn｝，其中 最 小 值 和 最 大 值 分 別 為card（min） 和card（max），則S中的每個數(shù)均可以用式（2） 代替。

3.4 實驗結果分析

為驗證方法的有效性，本文實驗選擇了兩種流行的 關 系 型 數(shù) 據(jù) 庫PostgresSQL （v13）、 MySQL（v5.7），和一種新型的基數(shù)估計方法（IBJS）、一種基于機器學習的基數(shù)估計方法（MSCN）作對比。采用式（3） 中的Qerror和式（4） 中的Loss來對方法的準確性進行描述，Qerror用于衡量測試結果與真實基數(shù)的偏差，Loss為模型的損失函數(shù)。 實驗結果見表2。

表2 與其它4 種方法的結果對比Tab.2 Comparison with the other four methods

由表2 可知，IBJS 方法在Qerror中值表現(xiàn)最好，但是過于依賴索引結構使得如果表中沒有合理的索引結構，IBJS 的性能就會變得較差。 本文方法在第95 和99 個百分位上優(yōu)于其他方法。 從平均值上看，方法的魯棒性要優(yōu)于IBJS 和MSCN。

基于機器學習的本文方法（SELF）和MSCN 方法在不同訓練周期后的損失收斂對比如圖6 所示?？梢钥闯隼脵C器學習的基數(shù)估計方法在經過多次訓練周期之后，其方法的損失迅速下降，準確度迅速提高；基于多頭自注意力機制的本文方法在初期時效果不如MSCN 方法，但是經過20 次左右的訓練周期之后，在準確性上略優(yōu)于MSCN，并且在75 次訓練周期之后，這兩種基于機器學習的模型損失收斂趨于接近。

圖6 本文方法和MSCN 方法的損失收斂對比Fig.6 Comparison of the loss convergence between the proposed method and the MSCN method

4 結束語

本文針對傳統(tǒng)基數(shù)估計方法存在問題，以及現(xiàn)有深度學習模型（RNN／CNN）的不足，提出了一種基于多頭自注意力機制，并結合圖嵌入等多種編碼進行特征提取的基數(shù)估計方法。 實驗結果表明該方法能夠有效提取和利用數(shù)據(jù)列之間的關系，提高基數(shù)估計結果的準確性，且該方法不依賴與特定的數(shù)據(jù)庫平臺和存儲引擎，能夠和絕大多數(shù)的數(shù)據(jù)庫結合，是數(shù)據(jù)庫和機器學習領域相結合一次應用創(chuàng)新和探索。

因為實驗是基于查詢驅動，受到查詢數(shù)據(jù)樣本和真實數(shù)據(jù)的差異影響較大，且實驗采用的是靜態(tài)數(shù)據(jù)，所以對線上動態(tài)數(shù)據(jù)進行有效建模，解決模型實時訓練慢等問題將是未來的研究重點。