基于多頭自注意力機制的基數估計研究

王 焱， 陳珊珊

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

0 引 言

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

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

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

1 相關工作

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

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

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

2 模型架構和技術要點

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

現有基于機器學習的基數估計模型框架如圖1所示。

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

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

2.1 查詢特征表達（Query Featurization）

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

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

2.1.2 列編碼（Columns Encoding）

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

2.1.3 值編碼（Value Encoding）

值編碼主要是對于WHERE 子句中出現的值進行編碼。 先對WHERE 子句中所有的值篩選并進行格式規范化處理，轉換為范圍查詢，即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）對連接圖進行編碼和優化。

假設分別有表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 多頭自注意力機制

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

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

其中， 輸入參數Q（Query）、K（Key）、V（Value）均為矩陣參數，分別代表查詢矩陣、鍵矩陣和值矩陣；代表調節因子；k是矩陣K的維度；W0為轉換矩陣。

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

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

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

3 實 驗

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

（1）根據IMDb 數據集生成隨機樣本數據；

（2）對樣本數據進行查詢特征編碼；

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

3.1 實驗環境

實驗配置見表1。

表1 實驗配置Tab.1 Experimental configuration

3.2 數據集和訓練集生成

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

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

3.3 數據預處理

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

3.4 實驗結果分析

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

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

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

基于機器學習的本文方法（SELF）和MSCN 方法在不同訓練周期后的損失收斂對比如圖6 所示。可以看出利用機器學習的基數估計方法在經過多次訓練周期之后，其方法的損失迅速下降，準確度迅速提高；基于多頭自注意力機制的本文方法在初期時效果不如MSCN 方法，但是經過20 次左右的訓練周期之后，在準確性上略優于MSCN，并且在75 次訓練周期之后，這兩種基于機器學習的模型損失收斂趨于接近。

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

4 結束語

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

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