人工智能賦能的查詢處理與優(yōu)化新技術(shù)研究綜述*

宋雨萌，谷 峪，李芳芳，于 戈

東北大學 計算機科學與工程學院，沈陽110169

1 引言

數(shù)據(jù)查詢一直是計算機領(lǐng)域的一個重要問題。自20世紀70年代起，數(shù)據(jù)庫研究人員對數(shù)據(jù)庫系統(tǒng)優(yōu)化與數(shù)據(jù)驅(qū)動應(yīng)用的研究使數(shù)據(jù)查詢處理與優(yōu)化技術(shù)得到了極大的發(fā)展。如今，高效的數(shù)據(jù)管理系統(tǒng)已逐漸成為信息化社會基礎(chǔ)設(shè)施建設(shè)的重要支撐[1]。

近年來，人工智能領(lǐng)域的技術(shù)被廣泛應(yīng)用于數(shù)據(jù)驅(qū)動的問題中，取得了良好的效果。受到這些研究成果啟發(fā)，數(shù)據(jù)庫研究人員將數(shù)據(jù)查詢處理與優(yōu)化技術(shù)與人工智能中機器學習、深度學習技術(shù)相融合，力求達到更優(yōu)的性能。因而，人工智能賦能的查詢處理與優(yōu)化技術(shù)正在成為計算機領(lǐng)域的一個重要的熱點問題。通過分析查詢各階段中的數(shù)據(jù)庫狀態(tài)，學習對數(shù)據(jù)動態(tài)、智能的查詢處理與優(yōu)化能力，已經(jīng)成為產(chǎn)業(yè)競爭力的體現(xiàn)。

相比通用的數(shù)據(jù)查詢處理與優(yōu)化技術(shù)，人工智能賦能的查詢處理與優(yōu)化技術(shù)在執(zhí)行效率與性能方面具有明顯優(yōu)勢。在執(zhí)行效率方面，隨著硬件的計算能力的巨大提升，越來越多的設(shè)備配置了專門用于機器學習的硬件，例如，iphone的“Neural Engine”，谷歌手機的“Visual Core”，谷歌云的云端TPU以及微軟開發(fā)的BrainWave等[2]。強大的計算能力大大降低了模型訓練與運行時間。從當前的發(fā)展趨勢可以預(yù)見，機器學習、深度學習等技術(shù)的開銷在未來可能忽略不計。因此，人工智能賦能的查詢處理與優(yōu)化新技術(shù)將提高數(shù)據(jù)查詢的執(zhí)行效率，降低時間開銷。在性能方面，機器學習方法將自動選擇使數(shù)據(jù)庫表現(xiàn)達到最優(yōu)的查詢計劃、配置參數(shù)或數(shù)據(jù)索引等，與數(shù)據(jù)庫管理員（database administrator，DBA）的手動調(diào)優(yōu)相比，人工智能方法能夠解決有經(jīng)驗的DBA 無法解決的問題，同時避免了大量的手動操作。與復(fù)雜的啟發(fā)式算法相比，人工智能方法將考慮更多的上下文因素，獲取更優(yōu)的優(yōu)化結(jié)果。

如今，大數(shù)據(jù)管理技術(shù)與系統(tǒng)已能夠滿足各類海量同/異構(gòu)數(shù)據(jù)的基本查詢需求，但如何利用新一代人工智能技術(shù)提高數(shù)據(jù)查詢處理與優(yōu)化的性能仍然面臨著諸多挑戰(zhàn)。在近期的相關(guān)綜述工作中，文獻[3]對深度學習與數(shù)據(jù)庫領(lǐng)域的交叉問題進行了總結(jié)，分析了部分深度學習模型應(yīng)用于查詢接口、查詢計劃、眾包與知識庫、時空數(shù)據(jù)等數(shù)據(jù)庫應(yīng)用的可能性。文獻[4]總結(jié)了人工智能技術(shù)在數(shù)據(jù)庫系統(tǒng)的實現(xiàn)方式和存在問題，選取有代表性的研究成果介紹了人工智能在數(shù)據(jù)庫多個方面的研究進展并提出未來研究方向。文獻[5]概述了機器學習技術(shù)與數(shù)據(jù)庫關(guān)鍵組件中具體問題的結(jié)合方式與存在的問題，并分析了現(xiàn)有的問題解決方式，對進一步融合機器學習與數(shù)據(jù)庫關(guān)鍵技術(shù)給出展望。文獻[6]從存儲管理、查詢優(yōu)化、自動化數(shù)據(jù)庫管理系統(tǒng)三方面對數(shù)據(jù)庫系統(tǒng)的機器學習化研究進行歸納，分析已有技術(shù)并指出了未來研究方向及可能面臨的問題與挑戰(zhàn)。

與上述工作相比，本文將側(cè)重于數(shù)據(jù)管理中的查詢處理與優(yōu)化問題。圖1 展示了本文總體內(nèi)容路線圖，以常見數(shù)據(jù)庫管理系統(tǒng)的層次架構(gòu)為劃分依據(jù)，有針對性地對人工智能賦能的查詢處理與優(yōu)化技術(shù)中數(shù)據(jù)存?。ㄖ悄芩饕?、查詢優(yōu)化（包括代價估計、技術(shù)估計、索引選擇、連接順序優(yōu)化、近似查詢優(yōu)化、聯(lián)合查詢優(yōu)化等）、系統(tǒng)運維（包括數(shù)據(jù)配置與調(diào)優(yōu)、查詢負載分析與預(yù)測）等關(guān)鍵性問題的發(fā)展近況進行更全面系統(tǒng)的回顧與分析，剖析不同人工智能技術(shù)應(yīng)用于查詢處理與優(yōu)化各環(huán)節(jié)的優(yōu)勢與不足，詳盡地梳理人工智能賦能的查詢處理與優(yōu)化新技術(shù)中的主要挑戰(zhàn)與解決方案，并探討發(fā)展方向，為未來的研究工作奠定基礎(chǔ)。

Fig.1 Roadmap of contents of this paper圖1 本文內(nèi)容路線圖

2 人工智能技術(shù)

人工智能（artificial intelligence，AI）是研究讓計算機來模擬人的思維過程和智能行為（比如學習、推理、思考、規(guī)劃等）的技術(shù)科學，主要研究計算機的智能原理、制造類似于人腦的智能計算機，以實現(xiàn)更高層次的計算機應(yīng)用，例如機器人、語言識別、圖像識別、自然語言處理等[7]。機器學習作為人工智能的核心內(nèi)容，是使計算機具有智能的根本途徑，其應(yīng)用遍及人工智能的各個領(lǐng)域。與傳統(tǒng)的為解決特定任務(wù)、硬編碼的軟件程序不同，機器學習不需要為機器編寫專門的業(yè)務(wù)邏輯代碼，由機器通過通用的機制對大量的數(shù)據(jù)分析學習，用于真實世界中事件的決策和預(yù)測。下面對數(shù)據(jù)庫優(yōu)化管理中幾種常用的人工智能技術(shù)進行簡單介紹。

2.1 神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)是機器學習中重要的技術(shù)。神經(jīng)網(wǎng)絡(luò)是由具有適應(yīng)性的簡單單元組成的廣泛并連的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)系統(tǒng)對真實世界物體所做出的交互反應(yīng)[8]。如圖2 所示，神經(jīng)網(wǎng)絡(luò)通常由一個具有層級結(jié)構(gòu)的加權(quán)圖表示。圖中的每個節(jié)點被稱為一個神經(jīng)元，是一個真實神經(jīng)元的功能抽象。神經(jīng)網(wǎng)絡(luò)的每一層由若干個神經(jīng)網(wǎng)絡(luò)組成，每層的神經(jīng)元與下一層神經(jīng)元全連接。每一層的神經(jīng)元將前一層神經(jīng)元的輸出值作為輸入，并根據(jù)權(quán)值和函數(shù)計算神經(jīng)元的輸出。在現(xiàn)實任務(wù)中，神經(jīng)網(wǎng)絡(luò)大多使用反向傳播算法進行權(quán)值訓練。

Fig.2 Example of neural network圖2 神經(jīng)網(wǎng)絡(luò)示意圖

2.2 強化學習

強化學習是一種針對馬爾可夫決策過程（Markov decision process，MDP）的隨機優(yōu)化技術(shù)[9]，常用的算法包括Q-learning、Policy Gradients 等。強化學習利用試錯法使機器能夠根據(jù)交互環(huán)境中的自身行為和經(jīng)驗反饋學習一個策略。如圖3所示，機器在時間t收到環(huán)境告知的當前狀態(tài)st，機器根據(jù)策略執(zhí)行動作at，環(huán)境將給出這個動作的獎勵值rt。接下來環(huán)境將給出機器t+1時刻的狀態(tài)st+1。不斷重復(fù)這個過程，直到機器完成任務(wù)。由此，狀態(tài)、動作、獎勵值構(gòu)成了機器的經(jīng)驗數(shù)據(jù)。強化學習的目標則是根據(jù)經(jīng)驗數(shù)據(jù)最大化累計獎勵值，學習最優(yōu)的策略。

Fig.3 Example of reinforcement learning圖3 強化學習示意圖

強化算法可以分為基于模型的方法（model-based）與免模型的方法（model-free）。前者主要發(fā)展自最優(yōu)控制領(lǐng)域，通常先通過高斯過程（Gaussian process，GP）或貝葉斯網(wǎng)絡(luò)（Bayesian network，BN）等工具針對具體問題建立模型，然后通過機器學習或最優(yōu)控制的方法，如模型預(yù)測控制（model predictive control，MPC）、線性二次調(diào)節(jié)器（linear quadratic control，LQR）、線性二次高斯（linear quadratic Gaussian，LQG）、迭代學習控制（iterative learning control，ICL）等進行求解。而后者更多地發(fā)展自機器學習領(lǐng)域，屬于數(shù)據(jù)驅(qū)動的方法。通過大量采樣估計機器的狀態(tài)、動作值函數(shù)或回報函數(shù)，從而優(yōu)化動作策略。

2.3 卷積神經(jīng)網(wǎng)絡(luò)

卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）是早期專門針對圖像識別問題設(shè)計的神經(jīng)網(wǎng)絡(luò)。其核心是通過局部操作對特征進行分層采樣，利用共享參數(shù)提高訓練性能。如今，CNN 也被用于自然語言處理中[10]。

CNN 包括3 種層結(jié)構(gòu)，即卷積層、池化層與全連接層。卷積層將輸入數(shù)據(jù)加入一組卷積濾波器，每個濾波器通過卷積計算提取特征。同一層的卷積濾波器共享權(quán)值，降低模型復(fù)雜度。池化層通過執(zhí)行非線性采樣，減少網(wǎng)絡(luò)需要學習的參數(shù)個數(shù)，簡化輸出。池化方式包括最大池化、加和池化、均值池化、最小值池化和隨機池化等。全連接層用于提取數(shù)據(jù)特征。

CNN的主要優(yōu)勢在于：（1）能夠較好地適應(yīng)圖像的結(jié)構(gòu)；（2）同時進行特征提取和分類，使特征提取有助于特征分類；（3）權(quán)值共享能夠減少網(wǎng)絡(luò)的訓練參數(shù)，簡化神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，提高了模型適應(yīng)性。

2.4 循環(huán)神經(jīng)網(wǎng)絡(luò)

循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）是一種根據(jù)“人的認知是基于過往的經(jīng)驗和記憶”這一觀點提出的特殊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。RNN以序列數(shù)據(jù)作為輸入，節(jié)點之間按時間順序連接成一個有向圖。RNN具有記憶性、權(quán)值共享并且圖靈完備，因此能以很高的效率對序列的非線性特征進行學習。如今，RNN已成功地用于自然語言處理中[11]。

RNN 的模型結(jié)構(gòu)如圖4 所示，主要包括輸入、輸出和一個神經(jīng)網(wǎng)絡(luò)單元。與普通神經(jīng)網(wǎng)絡(luò)不同，RNN 的神經(jīng)網(wǎng)絡(luò)單元不僅僅與輸入和輸出存在聯(lián)系，其與自身也存在一個回路。這種網(wǎng)絡(luò)結(jié)構(gòu)使上一個時刻的網(wǎng)絡(luò)狀態(tài)信息將會作用于下一個時刻的網(wǎng)絡(luò)。

Fig.4 Example of RNN圖4 循環(huán)神經(jīng)網(wǎng)絡(luò)示意圖

由于RNN 在實際應(yīng)用中有梯度消失問題，為解決該問題，研究人員提出帶有存儲單元的RNN——長短期記憶網(wǎng)絡(luò)（long short-term memory，LSTM）。LSTM 比標準的RNN 更適合于存儲和訪問信息[1]。LSTM較RNN增加了輸入門、輸出門、忘記門三個控制單元。當數(shù)據(jù)輸入模型時，LSTM中的控制單元會對該數(shù)據(jù)進行判斷，符合規(guī)則的數(shù)據(jù)會被留下，不符合的數(shù)據(jù)則被遺忘，以此解決神經(jīng)網(wǎng)絡(luò)中長序列依賴問題。

2.5 數(shù)據(jù)查詢處理與優(yōu)化任務(wù)區(qū)別于傳統(tǒng)人工智能任務(wù)的技術(shù)挑戰(zhàn)

比起傳統(tǒng)的AI 任務(wù)，如分類、聚簇等，數(shù)據(jù)查詢處理與優(yōu)化任務(wù)有著特殊的復(fù)雜性和多樣性。將現(xiàn)有的機器學習算法應(yīng)用到數(shù)據(jù)查詢的各個階段，要充分考慮這些特點和挑戰(zhàn)，甚至要探索新的定制化機器學習算法來滿足這些特殊需求。數(shù)據(jù)查詢處理與優(yōu)化任務(wù)區(qū)別于傳統(tǒng)AI 任務(wù)，主要包括以下四個技術(shù)挑戰(zhàn)。

（1）面向關(guān)鍵性任務(wù)的機器學習算法可解釋性。傳統(tǒng)AI 任務(wù)往往基于預(yù)測，具有很大的不確定性。數(shù)據(jù)查詢處理與優(yōu)化的一些關(guān)鍵性任務(wù)（如連接順序、索引選擇等）要求提供確定性的服務(wù)，而很多機器學習特別是深度學習算法的有效性內(nèi)部機理并未完全清楚，缺乏可解釋性，對可能出現(xiàn)誤差的邊界缺乏有效的估計，應(yīng)用到關(guān)鍵性任務(wù)會帶來很大的風險甚至嚴重后果。

（2）面向多樣性負載的機器學習算法適配性。傳統(tǒng)機器學習任務(wù)往往面向單一類型的數(shù)據(jù)和指定的任務(wù)類別，而新一代的大數(shù)據(jù)管理系統(tǒng)通常要求具備處理多樣化數(shù)據(jù)、工作負載并兼容新硬件環(huán)境的適配能力，不同任務(wù)的查詢分析語義和要處理的數(shù)據(jù)形態(tài)分布都具有巨大的差異，且在任務(wù)到達前不可預(yù)測。如何提高學習模型的泛化性和自適應(yīng)性面臨巨大的挑戰(zhàn)。

（3）面向數(shù)據(jù)更新的機器學習算法時效性。傳統(tǒng)AI 任務(wù)往往面向靜態(tài)的訓練數(shù)據(jù)，但數(shù)據(jù)查詢處理與優(yōu)化技術(shù)需要能夠處理頻繁的數(shù)據(jù)更新甚至數(shù)據(jù)流。數(shù)據(jù)的動態(tài)變化將導致原有的模型失效，預(yù)測準確性嚴重下降。如何針對數(shù)據(jù)管理任務(wù)的數(shù)據(jù)更新特點，定制有效的增量機器學習和在線機器學習算法，面臨巨大的挑戰(zhàn)。

（4）機器學習和傳統(tǒng)數(shù)據(jù)查詢處理與優(yōu)化方法的可協(xié)作性。當前階段，機器學習不可能完全替代傳統(tǒng)的數(shù)據(jù)查詢處理與優(yōu)化方法，兩類方法需要相互協(xié)作，取長補短。當兩種方法共存在同一系統(tǒng)時（如傳統(tǒng)索引和學習型索引共存），如何使不同類方法充分協(xié)助，達到整體性能的最大優(yōu)化，面臨巨大挑戰(zhàn)。這需要深入分析不同階段和不同任務(wù)中兩類方法的增益邊界，探索不同方法之間的交互和數(shù)據(jù)共享模式，以及自適應(yīng)的調(diào)度和切換策略。

3 人工智能賦能的查詢處理與優(yōu)化技術(shù)的相關(guān)研究

AI賦能的查詢處理與優(yōu)化新技術(shù)將AI與數(shù)據(jù)查詢問題相融合，將AI滲透于數(shù)據(jù)查詢的多個方面，提供更有效的數(shù)據(jù)查詢與優(yōu)化手段。本文通過調(diào)研，將現(xiàn)有相關(guān)研究成果分為四類：（1）智能數(shù)據(jù)存取新技術(shù)，即AI用于數(shù)據(jù)存儲組織、壓縮和索引。（2）AI賦能的查詢優(yōu)化技術(shù)，即AI 替代整體傳統(tǒng)查詢優(yōu)化器或部分組件，預(yù)測基數(shù)、代價，生成查詢計劃等。（3）智能系統(tǒng)調(diào)優(yōu)技術(shù)，即AI用于系統(tǒng)負載的預(yù)測及配置的自動調(diào)優(yōu)。（4）AI 賦能的數(shù)據(jù)庫系統(tǒng)/原型系統(tǒng)。本章將對各類研究內(nèi)容進行詳細的整理和比較分析。

3.1 智能數(shù)據(jù)存取新技術(shù)

隨著數(shù)據(jù)量的飛速膨脹，數(shù)據(jù)存取的性能面臨著巨大的挑戰(zhàn)。高效的數(shù)據(jù)存取離不開索引技術(shù)，索引技術(shù)是提高查詢性能的重要方法之一。在過去的幾十年中，已提出了多種不同的索引結(jié)構(gòu)[12]，例如用于基于硬盤系統(tǒng)的B+樹[13]，用于內(nèi)存系統(tǒng)的T-tree[14]及平衡樹[15]等。

不同的數(shù)據(jù)組織特征、用戶查詢需求及索引策略決定了查詢性能的優(yōu)劣，合理的索引設(shè)計必須要建立在對各種查詢的分析、預(yù)測以及數(shù)據(jù)組織的特點上。在現(xiàn)有數(shù)據(jù)庫中，通常使用B 樹進行范圍查詢，使用HashMap進行單值查詢，使用Bloom過濾器檢查值記錄是否存在。研究人員專注于索引性能優(yōu)化的研究，以獲得更高的內(nèi)存、緩存和CPU（central processing unit）效率。然而，目前采用的索引并未利用如數(shù)據(jù)分布等數(shù)據(jù)特征，導致在一些情況下數(shù)據(jù)查詢的性能低下。例如，在自動駕車、電子商務(wù)網(wǎng)站等應(yīng)用中產(chǎn)生了大量以時間戳為主鍵，傳感器讀數(shù)為數(shù)值的數(shù)據(jù)。若數(shù)據(jù)表中包含多個相同數(shù)值但時間戳不同的數(shù)據(jù)，數(shù)據(jù)庫管理系統(tǒng)將為每一條數(shù)據(jù)建立索引。隨著時間推移，索引的增長將占用大量的存儲空間。此外，若使用B 樹對以上數(shù)據(jù)建立索引，查詢一條數(shù)據(jù)的時間開銷為O(nlbn)，但若根據(jù)數(shù)據(jù)分布計算數(shù)據(jù)位置，查詢開銷可降低為O(1)。

針對通用數(shù)據(jù)索引存在的問題，研究人員提出了多種學習索引，根據(jù)數(shù)據(jù)的分布預(yù)測數(shù)據(jù)的存儲位置，降低索引存儲空間，提升查詢效率，相關(guān)研究如表1 所示。索引類型分為基于B 樹的混合學習索引與基于深度模型的學習索引，基于B樹的混合學習索引混合傳統(tǒng)索引算法與學習型索引結(jié)構(gòu)，提升傳統(tǒng)索引性能。基于深度模型的學習索引完全擺脫傳統(tǒng)索引算法，僅根據(jù)訓練數(shù)據(jù)生成的經(jīng)驗概率分布函數(shù)估計數(shù)據(jù)位置。

3.1.1 基于B樹的混合型學習索引

Galakatos 等人[16]設(shè)計了一種混合樹結(jié)構(gòu)與學習算法的近似索引A樹，如圖5（a）、圖5(b）所示。為了利用數(shù)據(jù)的分布構(gòu)建更有效的索引，A樹提出基于動態(tài)規(guī)劃的分段算法，將數(shù)據(jù)劃分為大小不同的段，每段是一個已排序的連續(xù)數(shù)組。對于每段中的數(shù)據(jù)構(gòu)建線性模型，使用線性插值算法學習數(shù)據(jù)的分布函數(shù)。段中任何點的插入位置與準確位置的誤差不超過錯誤閾值err，DBA 能通過設(shè)置err平衡A 樹的空間開銷與查詢性能。數(shù)據(jù)分段后，A樹將段組織到樹結(jié)構(gòu)中，如B+樹或FAST（fast architecture sensitive tree）等，每個樹結(jié)構(gòu)節(jié)點僅存儲起始關(guān)鍵字、斜率以及具體頁面的指針，樹結(jié)構(gòu)能夠有效地支持插入與查詢操作。A 樹的查詢操作分為兩步：第一步為樹搜索，根據(jù)樹結(jié)構(gòu)搜索葉子節(jié)點；第二步為段搜索，根據(jù)插入位置和錯誤閾值進行局部搜索（二分搜索等）。A樹為每個段設(shè)置一個緩存區(qū)，將被插入數(shù)據(jù)加入相應(yīng)的緩存中，緩存區(qū)滿時，根據(jù)分段算法對段進行更新。

Table 1 Learning indexes classification表1 學習索引研究分類

Fig.5 A tree schematic diagram proposed by Galakatos et al圖5 Galakatos等人提出的A樹示意圖

IFB（interpolation-friendly B-trees）樹索引由Hadian等人于文獻[17]中提出。如圖6（b）所示，與只對葉子節(jié)點查詢加速的A樹相比，IFB樹索引利用線性插值方法建立輔助模型，在查詢的不同階段改進經(jīng)典索引。Hadian等人認為B樹查詢中，節(jié)點內(nèi)部搜索占用了相當大的時間開銷。針對這一缺陷，作者利用輔助模型直接預(yù)測查詢節(jié)點位于下一層節(jié)點中的位置，避免了內(nèi)部搜索，查詢過程如圖6（a）所示。由于輔助模型并不改變B樹的結(jié)構(gòu)，因此IFB樹與B樹具有一致的理論性能保證。但由于插值算法對于不同的節(jié)點的誤差不同，若存儲多個插值將難以保證B樹的效率與開銷。為此，IFB 樹設(shè)置最大錯誤閾值Δ。建樹時，若節(jié)點的插值位置的錯誤閾值小于Δ，則將節(jié)點標記為插值友好，使用插值算法查詢，對于非插值友好節(jié)點，則使用傳統(tǒng)方法進行查詢。

Fig.6 IFB tree schematic diagram proposed by Hadian et al圖6 Hadian等人提出的IFB樹示意圖

3.1.2 基于深度模型的學習索引

Kraska 等人[18]提出了構(gòu)建學習整體索引的研究思路。作者認為了解數(shù)據(jù)的分布將高度優(yōu)化數(shù)據(jù)庫系統(tǒng)中使用的索引。然而在大多數(shù)現(xiàn)有的數(shù)據(jù)庫系統(tǒng)中，為每個數(shù)據(jù)庫設(shè)計專用的存儲方式代價十分高昂。因此，作者提出使用機器學習挖掘數(shù)據(jù)的模式和相關(guān)性，從而以低工程開銷自動生成索引結(jié)構(gòu)，稱為“學習索引”。學習索引能夠提供與傳統(tǒng)索引結(jié)構(gòu)相同的語義保證，同時在性能上也能獲得極大的提升。在文獻中，作者分別以B 樹、HashMap、Bloom過濾器為例，提出將學習索引應(yīng)用于范圍索引、點索引及存在索引。

對于范圍索引，作者將范圍索引視作一個輸入關(guān)鍵字預(yù)測值記錄位置的模型，提出相同語義的遞歸模型索引（recursive-model index，RMI）。如圖7 所示，RMI 利用層次結(jié)構(gòu)縮小問題空間。每層的模型輸入關(guān)鍵字，輸出下一層的模型選擇，直至輸出數(shù)據(jù)記錄的位置。RMI 能夠在不同層中混合多種模型，如神經(jīng)網(wǎng)絡(luò)、ReLU 激活函數(shù)或線性回歸模型等，以滿足每層中搜索子空間的精度。對于點索引，Kraska等人利用底層數(shù)據(jù)的分布函數(shù)訓練機器學習模型代替?zhèn)鹘y(tǒng)的哈希函數(shù)，減少沖突。對于存在索引，作者提供了兩種思路：其一是將存在索引作為一種二元分類問題，訓練分類器區(qū)分關(guān)鍵字與非關(guān)鍵字；其二是訓練哈希函數(shù)，最大化關(guān)鍵字之間的沖突及非關(guān)鍵字之間的沖突，同時最小化關(guān)鍵字與非關(guān)鍵字的沖突。

Fig.7 RMI proposed by Kraska et al圖7 Kraska等人提出的RMI模型示意圖

文獻[18]所提出的學習索引中，假設(shè)機器完全學習了關(guān)鍵字的經(jīng)驗分布函數(shù)，預(yù)測查詢關(guān)鍵字在數(shù)據(jù)存儲表頁中的位置，降低內(nèi)存與計算開銷。然而，訓練后的RMI模型僅適用于只讀數(shù)據(jù)。隨著關(guān)鍵字的插入和刪除，關(guān)鍵字的經(jīng)驗分布函數(shù)與初始經(jīng)驗分布函數(shù)將產(chǎn)生顯著偏移，使用初始經(jīng)驗分布函數(shù)將降低學習索引的性能與精度?；谝陨先毕?，Hadian等人[21]提出基于參考點的學習索引更新算法，參考點即已知偏移距離的點。算法利用查詢點左側(cè)右側(cè)兩個參考點進行插值計算，估計查詢點的偏移量。查詢時根據(jù)查詢點的預(yù)測位置及偏移量計算查詢點的真實位置。學習索引更新算法避免了對模型的重新訓練，并確保輸出位置在錯誤窗口之內(nèi)。

對于文獻[18]中學習Bloom過濾器，Mitzenmacher[19]提出了簡單的改進方法，提高過濾精度，增強學習Bloom 過濾器的魯棒性。作者將學習Bloom 過濾器夾在兩個小規(guī)模Bloom過濾器中，如圖8所示。預(yù)過濾器首先過濾輸入中假陽性的數(shù)據(jù)，備份過濾器對學習索引中生成的負例進行篩選，獲得假陰性的數(shù)據(jù)。

Fig.8 Improved learning Bloom filter proposed by Mitzenmacher圖8 Mitzenmacher提出的改進的學習Bloom過濾器

基于學習索引的啟發(fā)，Oosterhuis 等人[20]挖掘機器學習用于倒排索引優(yōu)化的潛力，研究學習索引如何支持倒排索引中常見的基于布爾交集的查詢。作者將每個文檔作為一個單獨的屬性集合，使用學習Bloom過濾器，判斷文檔是否包含某屬性。由于這種方法的查詢成本與集合中文檔的數(shù)量成正比，因此作者提出基于兩層檢索的方法與基于塊的方法縮小查詢空間，降低查詢成本。實驗證明，學習索引與當前索引相比提供了空間優(yōu)勢，有巨大的研究潛力。

以上學習索引中，部分模型能夠處理數(shù)據(jù)更新，例如IFB樹對傳統(tǒng)B樹進行優(yōu)化，對能保證預(yù)定義的誤差值范圍內(nèi)的節(jié)點使用線性插值，但仍維護頂層的B樹結(jié)構(gòu)。A樹的核心思想與RMI模型相同，但采用線性模型而非深度模型，因此可在較短時間內(nèi)對模型進行重新訓練。A 樹與IFB 樹使用經(jīng)典索引結(jié)構(gòu)或簡單的模型，限制了通過學習索引可能獲得的潛在性能增益。然而，使用復(fù)雜模型對數(shù)據(jù)建模的索引，并不能直接適用于更新數(shù)據(jù)，需要對數(shù)據(jù)定期重新訓練或使用有效的更新算法，校正索引誤差。

基于B 樹的混合型學習索引通過機器學習的方法優(yōu)化B樹節(jié)點的內(nèi)部查詢速度，并減少硬盤的訪問次數(shù)，但索引仍采用B 樹結(jié)構(gòu)，無法突破B 樹的瓶頸?；谏疃葘W習的學習索引使用多個神經(jīng)網(wǎng)絡(luò)替換傳統(tǒng)的索引結(jié)構(gòu)，通過學習數(shù)據(jù)的分布構(gòu)建索引模型，為數(shù)據(jù)索引提供了新的研究方向。然而，目前基于深度學習的學習索引的研究工作主要圍繞Kraska提出的初步研究想法，還存在大量值得研究的問題，如：（1）Kraska 的研究主要針對只讀數(shù)據(jù)庫系統(tǒng)，如何在數(shù)據(jù)更新頻繁的場景下進行高效的學習索引訓練。（2）針對學習索引中機器學習模型的選擇問題，需要進一步實驗與分析。（3）學習索引缺乏可解釋性，沒有理論支持，值得進一步研究。

3.2 AI賦能的查詢優(yōu)化技術(shù)

查詢處理優(yōu)化是一個傳統(tǒng)的數(shù)據(jù)庫問題。目前大多數(shù)數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化器使用復(fù)雜的啟發(fā)式和代價模型來生成查詢計劃。但現(xiàn)有的查詢優(yōu)化器在一些情況下可能無法提供最優(yōu)的查詢計劃，因此在近期的研究中，研究人員使用機器學習、深度學習算法替代傳統(tǒng)查詢優(yōu)化器或其組件，如代價模型、連接計劃枚舉、基數(shù)估計等，以提供更優(yōu)的查詢計劃[2，22]。本節(jié)對AI賦能的查詢優(yōu)化技術(shù)的研究現(xiàn)狀進行介紹。

3.2.1 連接順序優(yōu)化

連接順序優(yōu)化問題已被研究近40年且仍是數(shù)據(jù)庫系統(tǒng)研究中的重要問題之一，對查詢性能有很大的影響。連接順序優(yōu)化問題的挑戰(zhàn)即枚舉一組候選連接順序并選擇代價最小的作為查詢計劃。由于連接順序優(yōu)化問題是NP難問題，因此現(xiàn)有研究中經(jīng)常使用啟發(fā)式算法縮減查詢空間，搜索最優(yōu)的連接順序。例如，System R[23]使用動態(tài)規(guī)劃找到代價最低的左深連接樹，而PostgreSQL[24]使用貪婪算法選擇低開銷的關(guān)系對，直到構(gòu)建一個樹。許多商業(yè)產(chǎn)品（例如SQL Server[25]）允許DBA 確定結(jié)構(gòu)約束或在一段時間后結(jié)束枚舉。然而，當代價模型是非線性時，啟發(fā)式算法通常會錯過良好的執(zhí)行計劃[26]。更重要的是，傳統(tǒng)的查詢依賴于靜態(tài)策略，不能從過去的經(jīng)驗中學習，缺乏經(jīng)驗反饋，因此會重復(fù)選擇次優(yōu)計劃。

針對啟發(fā)式方法的缺陷，研究人員將不同的強化學習算法應(yīng)用于連接順序優(yōu)化。強化學習不僅從根本上降低了啟發(fā)式算法的開銷，而且能通過過去的經(jīng)驗訓練模型，應(yīng)用于所有工作負載的連接順序優(yōu)化問題。人工智能賦能的連接順序優(yōu)化方法比較如表2 所示。Marcus 等人提出連接順序枚舉器ReJOIN[26]，使用強化學習中策略梯度算法學習連接選擇策略。ReJOIN中狀態(tài)變量為二元連接子樹結(jié)構(gòu)和連接/選擇謂詞的特征表示向量，利用多層神經(jīng)網(wǎng)絡(luò)輸出當前狀態(tài)對應(yīng)的連接動作發(fā)生的概率分布以選擇下一個連接動作。當所有關(guān)系連接完成時，ReJOIN根據(jù)優(yōu)化器的代價模型對連接順序給出獎勵值。Krishnan等人[27]提出一個基于Q-learning算法的DQ（deep Q-learning）優(yōu)化器。Q-learning是強化學習中基于值的算法，核心為Q(s,a)函數(shù)，即在某一時刻的狀態(tài)s下采取動作a能夠獲得收益的期望。相較于策略學習的強化學習算法，Q-learning 對任意連接子計劃的連接均計算得分而不是直接選擇最優(yōu)連接，能夠使用查詢計劃的多個子計劃進行訓練，極大地降低訓練數(shù)據(jù)量需求。DQ 優(yōu)化器由當前表連接結(jié)果生成的查詢圖作為強化學習狀態(tài)，連接操作作為強化學習動作，使用兩層DNN（deep neural network）表示Q函數(shù)，訓練Q函數(shù)的參數(shù)。在訓練時使用數(shù)據(jù)庫系統(tǒng)代價模型評估動作的獎勵，計算Q函數(shù)值，在查詢時每次選擇DNN輸出Q值最小的連接計劃。

以上兩種方法都依賴于大量的訓練數(shù)據(jù)，即從過去的查詢計劃中學習知識優(yōu)化下一次的查詢。同時，兩種方法都使用基于粗粒度數(shù)據(jù)統(tǒng)計或簡化假設(shè)（數(shù)據(jù)獨立、均勻分布等）的代價模型作為強化學習的獎勵。當模型估計錯誤時，兩種算法的連接計劃可能無法達到最優(yōu)?；谝陨峡紤]，Trummer等人[28]提出一個全新的數(shù)據(jù)庫系統(tǒng)SkinnerDB，不需要任何查詢上下文數(shù)據(jù)及基數(shù)估計模型，即可提供可靠的連接順序選擇。SkinnerDB的框架如圖9所示。查詢時，SkinnerDB的預(yù)處理器首先通過一元謂詞過濾基表，接著由連接處理器生成查詢的連接順序與執(zhí)行結(jié)果，最后調(diào)用后繼處理器對結(jié)果進行分組、聚合與排序等操作。連接處理器包括4個組件，連接處理器將每個連接操作分為多個時間片，每個時間片首先由學習優(yōu)化器選擇連接順序，選中的連接順序由連接執(zhí)行程序執(zhí)行，每次執(zhí)行固定時長，并將執(zhí)行結(jié)果加入結(jié)果集中。執(zhí)行程序可以使用通用的SQL（structured query language）處理器，也可以使用專門的執(zhí)行引擎。進程跟蹤器跟蹤被處理的數(shù)據(jù)，最后由獎勵計算器計算連接順序的得分。當所有數(shù)據(jù)被連接后，完成連接操作。學習優(yōu)化器使用強化學習領(lǐng)域的上限置信區(qū)間算法[29]（upper confidence bound apply to tree，UCT），在每個時間片中根據(jù)連接順序的枚舉空間生成搜索樹，并選擇一條路徑。UCT 算法的特點即不依賴任何具體示例的參數(shù)設(shè)置，能夠適用于較大的搜索空間。

Fig.9 Framework of SkinnerDB proposed by Trummer et al圖9 Trummer等人提出的SkinnerDB框架圖

表3是3種連接順序優(yōu)化算法的實驗結(jié)果對比分析。對于相同的查詢負載數(shù)據(jù)JOB（join order benchmark）[30]，3 種算法分別集成于不同執(zhí)行引擎以達到最低的查詢計劃執(zhí)行時間。在對查詢計劃執(zhí)行時間的改進方面，與PostgreSQL 相比，3 種算法能夠在不同程度上提升連接順序優(yōu)化的效率，降低查詢計劃執(zhí)行時間，其中SkinnerDB 最高能將查詢計劃執(zhí)行時間降低74.7%，但必須依賴于特定的執(zhí)行引擎。在學習收斂性方面，雖然ReJOIN 與DQ 使用相似的強化學習模型，但在訓練中，DQ 僅需要80 次迭代即可超越PostgreSQL 的執(zhí)行時間，而使用ReJOIN需要約8 000 次迭代才能達到PostgreSQL 的查詢開銷。這是由于DQ 優(yōu)化器使用了off-policy gradient的Q-learning方法，將訓練數(shù)據(jù)的利用率提升了兩個數(shù)量級。

Table 2 Comparison of join order optimization methods表2 連接順序優(yōu)化方法比較

Table 3 Experimental comparison of join order optimization methods表3 連接順序優(yōu)化實驗結(jié)果比較

3.2.2 查詢性能預(yù)測與學習代價模型

查詢性能預(yù)測用于預(yù)測查詢延遲，是多種數(shù)據(jù)管理任務(wù)的重要基礎(chǔ)，如訪問控制、資源管理和維護SLA（service-level agreement）等。影響查詢延遲的因素包括查詢計劃、基層數(shù)據(jù)分布等。雖然傳統(tǒng)的查詢優(yōu)化器能夠?qū)蜻x查詢計劃的開銷進行準確的估計，但隨著數(shù)據(jù)庫管理系統(tǒng)的更新和發(fā)展，新的操作符或物理組件將引入新的交互，而某些難以建模的交互將無法準確預(yù)測查詢計劃的執(zhí)行延遲。下面對人工智能賦能的查詢性能預(yù)測與學習代價模型研究展開介紹，相關(guān)文獻比較如表4所示。

Akdere 等人[31]提出基于機器學習的性能預(yù)測技術(shù)，分別在不同粒度對查詢性能建模。粗粒度的計劃級模型利用支持向量機（support vector machine，SVM）、核典型相關(guān)分析（kernel canonical correlation analysis，CCA），根據(jù)查詢計劃中手動選擇的特征向量，估計執(zhí)行計劃的延遲。細粒度的操作符級模型對每類操作符建立兩個獨立的預(yù)測模型：啟動時間模型與運行時間模型。啟動時間模型對應(yīng)于操作符自身運行時間，運行時間模型對應(yīng)于多次嵌套循環(huán)等情況下的總執(zhí)行時間。操作符級模型利用多元線性回歸模型（multiple linear regression，MLR），將單個操作符模型以分層的方式組合，通過特征選擇算法選擇后的操作符特征向量計算任意查詢的延遲時間。然而，兩種粒度的模型對查詢性能預(yù)測都具有缺陷。計劃級模型僅對與訓練數(shù)據(jù)具有類似查詢計劃的場景具有較好的性能，而操作符級模型由于分層結(jié)構(gòu)可能將底層的模型估計錯誤傳播至上層，因此作者提出兩種粒度混合建模方法，適用于普遍的查詢性能預(yù)測問題。

與上述方法類似，現(xiàn)有研究已包含多個利用機器學習和統(tǒng)計方法的性能預(yù)測工作，但解決方法主要集中于手工設(shè)計的指標、基于計劃級信息的訓練模型、基于關(guān)系運算符的數(shù)學模型等[35]。這些方法通常需要人工專家進行大量工作，且隨著數(shù)據(jù)庫管理系統(tǒng)的復(fù)雜性的增加，算法的可擴展性很差。除此之外，由于查詢延遲與查詢計劃結(jié)構(gòu)、中間結(jié)果的特征和操作符相關(guān)，而查詢計劃結(jié)構(gòu)并不固定，因此傳統(tǒng)的靜態(tài)模型，如DNN等，無法對多種基于樹結(jié)構(gòu)的查詢計劃建模。基于以上兩點考慮，研究者們近期提出了基于樹結(jié)構(gòu)的學習模型用于代價估計與預(yù)測。Marcus 等人[32]提出與查詢樹結(jié)構(gòu)完全相同的DNN模型，如圖10（a）、圖10（b）所示。模型為每個邏輯操作符建立一個神經(jīng)網(wǎng)絡(luò)單元，計算該操作符用于基數(shù)估計的數(shù)據(jù)向量與用于代價估計的延遲向量。葉子節(jié)點輸入自身的操作符類型、結(jié)果基數(shù)估計、I/O需求估計的向量，中間節(jié)點接收左右子節(jié)點輸出的數(shù)據(jù)向量與延遲向量，并根據(jù)自身操作符的特征向量計算結(jié)果。根節(jié)點神經(jīng)網(wǎng)絡(luò)單元的延遲預(yù)測作為查詢計劃的延遲。

Table 4 Comparison of query performance prediction methods and learning-based cost models表4 查詢性能預(yù)測方法與學習代價模型比較

Fig.10 Plan-structured DNN proposed by Marcus et al圖10 Marcus等人提出的查詢計劃結(jié)構(gòu)DNN

表5為兩種查詢性能預(yù)測方法的實驗結(jié)果比較，其中SVM 為文獻[31]提出的方法，DNN 為文獻[32]提出的方法。在TPC-H 工作負載下，DNN 的預(yù)測查詢延遲與實際查詢延遲的相對誤差率與平均絕對誤差較SVM分別降低了24個百分點與15 min，證明了手動特征選擇難以獲取操作符之間的復(fù)雜關(guān)系。在模型收斂性方面，DNN需要大于1 000次的迭代才能達到收斂，耗時超過28 h，但當?shù)螖?shù)超過250 次時，DNN的平均絕對誤差即可超過SVM的性能。

Table 5 Experimental comparison of query performance prediction methods表5 查詢性能預(yù)測方法實驗結(jié)果比較

在近期學習代價模型的相關(guān)研究中，Idreos等人[33]將所有操作劃分為細粒度的原語，并為所有操作訓練一個簡單的代價模型，通過原語的組合計算任意復(fù)雜操作的延遲代價。Sun等人[34]使用LSTM對查詢樹進行嵌入，從葉子節(jié)點遞歸地訓練查詢計劃的向量表示。LSTM輸入操作符左右子節(jié)點的表示向量，輸出當前節(jié)點的表示向量。最后將查詢計劃的嵌入輸入一個兩層全連接神經(jīng)網(wǎng)絡(luò)估計基數(shù)與延遲。

對于兩種學習代價模型，雖然文獻[33]未對單獨的代價模型組件性能進行實驗評估，但通過對整個引擎的數(shù)據(jù)存取預(yù)測延遲與真實延遲的對比實驗，可間接證明學習代價模型能夠降低預(yù)測誤差。文獻[34]在多個數(shù)據(jù)集下對比完整模型與不同變體的準確性，驗證了模型設(shè)計的合理性。

3.2.3 基數(shù)估計

在基于代價的查詢優(yōu)化技術(shù)中，基數(shù)估計是評價查詢計劃的重要手段，其任務(wù)是估計查詢執(zhí)行計劃中的每個操作符返回的元組數(shù)量[35]?；鶖?shù)估計的質(zhì)量將直接影響查詢計劃的選擇與查詢優(yōu)化器的性能。因此，高精度的基數(shù)估計十分重要。然而，大多數(shù)傳統(tǒng)的估計方法都是基于如數(shù)據(jù)一致性與獨立性等假設(shè)的統(tǒng)計模型，在真實數(shù)據(jù)集中，數(shù)據(jù)經(jīng)常不滿足假設(shè)，導致基數(shù)估計出現(xiàn)較大的錯誤[30，36-37]，使優(yōu)化器生成次優(yōu)的查詢計劃。為了克服傳統(tǒng)方法的限制，Lakshmi 等人[38]第一個提出基于神經(jīng)網(wǎng)絡(luò)的用戶自定義函數(shù)謂詞基數(shù)估計算法，將自定義函數(shù)謂詞轉(zhuǎn)化為數(shù)值輸入神經(jīng)網(wǎng)絡(luò)，預(yù)測謂詞返回的元組數(shù)量。Malik等人[39]根據(jù)查詢結(jié)構(gòu)（連接條件、謂詞屬性等）利用決策樹對查詢分類，并對每類查詢訓練不同的回歸模型進行基數(shù)估計。受到以上兩個研究的啟發(fā)，以及人工智能技術(shù)在其他查詢優(yōu)化問題的優(yōu)秀表現(xiàn)，研究人員開始探索人工智能在基數(shù)估計問題上的潛力，相關(guān)文獻比較如表6所示。

Liu等人[40]提出了針對選擇謂詞基數(shù)估計的增強神經(jīng)網(wǎng)絡(luò)框架，學習范圍查詢謂詞的上下界與謂詞選擇率之間的映射函數(shù)，選擇率即衡量謂詞降低基數(shù)能力的指標。但選擇率函數(shù)是不連續(xù)的，為了使神經(jīng)網(wǎng)絡(luò)能夠?qū)W習非連續(xù)的選擇率函數(shù)，如圖11 所示，作者改進了傳統(tǒng)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，將隱藏層中的數(shù)據(jù)單元根據(jù)跳轉(zhuǎn)函數(shù)進行分組，在使用時根據(jù)輸入選擇隱藏層中的不同單元。Hasan等人[41]認為非監(jiān)督學習與監(jiān)督學習算法皆可適用于選擇謂詞基數(shù)估計問題。非監(jiān)督學習算法利用傳統(tǒng)的抽樣基數(shù)估計思想，將謂詞選擇率估計建模為一個密度估計問題，使用自回歸模型將數(shù)據(jù)的聯(lián)合分布按照鏈式法則分解為多個條件分布，利用屏蔽自編碼器[45]（masked autoencoder for distribution estimation，MADE）學習多個自回歸條件分布。監(jiān)督學習算法將編碼后的查詢輸入兩層的神經(jīng)網(wǎng)絡(luò)，估計正則化的選擇率。

Table 6 Comparison of cardinality estimation methods表6 基數(shù)估計方法比較

Fig.11 Structure of enhanced NN proposed by Liu et al圖11 Liu等人提出的增強神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖

文獻[40]中的增強神經(jīng)網(wǎng)絡(luò)模型、文獻[41]中的兩種基數(shù)估計算法在實驗中均能夠超越傳統(tǒng)基數(shù)估計算法。其中，在高相關(guān)與傾斜的數(shù)據(jù)下，對于等式謂詞與范圍謂詞的查詢基數(shù)估計，增強神經(jīng)網(wǎng)絡(luò)模型較DB2在Q-error[41]值上分別降低了98.7%與65.0%，但在低相關(guān)與傾斜的數(shù)據(jù)中，增強神經(jīng)網(wǎng)絡(luò)模型基數(shù)估計的準確度可能降至個位數(shù)。文獻[42]提出的兩種基數(shù)估計模型在Census 數(shù)據(jù)集中，平均估計準確度是貝葉斯網(wǎng)絡(luò)算法2倍，最低準確度達到貝葉斯網(wǎng)絡(luò)算法的100倍，且訓練時間降低了93.75%。

Kipf等人[42]發(fā)現(xiàn)查詢的基數(shù)獨立于查詢計劃，因此使用多集卷積神經(jīng)網(wǎng)絡(luò)（multi-set convolutional network，MSCN）模型，有監(jiān)督地估計連接查詢基數(shù)。模型框架如圖12所示，首先對表、連接與選擇謂詞三個集合分別訓練單獨的模型，再對三個集合的輸出進行連接，輸入到最終的DNN 中估計查詢基數(shù)。上層的DNN將獲取集合與基數(shù)估計值之間的相關(guān)性。訓練時，除了用于訓練的查詢語句外，算法還將符合條件的基表的樣本信息特征化，生成表示每個基表符合條件的位圖，將位圖作為深度學習模型的額外輸入訓練模型參數(shù)。

Fig.12 MSCN model proposed by Kipf et al圖12 Kipf等人使用的MSCN模型圖

MSCN 算法對整個數(shù)據(jù)庫視圖創(chuàng)建一個全局學習模型，但是全局學習模型在訓練時容易出現(xiàn)訓練數(shù)據(jù)稀疏的問題。為了克服這一問題，Woltmann 等人[43]提出一種面向局部的建模方法，為數(shù)據(jù)庫建立多個局部模型。每個局部模型對應(yīng)任意數(shù)量的連接和連接組合，輸入操作符和數(shù)值的表示向量，利用DNN進行基數(shù)估計。

Ortiz 等人[44]提出使用強化學習算法的基數(shù)估計方法，能用于同時具有選擇與連接操作的查詢。算法將基數(shù)作為獎勵，學習數(shù)據(jù)庫執(zhí)行查詢計劃的一個操作后新的狀態(tài)向量的函數(shù)NNST以及狀態(tài)向量與基數(shù)的映射函數(shù)NNobserved。如圖13所示，在執(zhí)行時，按照查詢計劃依次利用NNST與NNobserved計算查詢計劃返回的條目數(shù)量。

與PostgreSQL 相比，訓練后的MSCN 與局部建模方法（LOCAL NN）對基數(shù)估計的準確性與執(zhí)行速度上均有很大程度的提升，如表7所示。實驗數(shù)據(jù)證明，MSCN復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)需要較長的訓練時間與執(zhí)行時間。此外，局部建模方法較MSCN的全局學習方法能夠獲取精確的數(shù)據(jù)相關(guān)性，提升估計的準確性。

3.2.4 近似查詢處理引擎

Fig.13 Reinforcement learning model proposed by Ortiz et al圖13 Ortiz等人提出的強化學習模型圖

Table 7 Experimental comparison of cardinality estimation methods表7 基數(shù)估計方法實驗結(jié)果對比

在大數(shù)據(jù)時代，數(shù)據(jù)驅(qū)動的決策已成為超越競爭對手的主要手段，但計算準確的大規(guī)模數(shù)據(jù)庫查詢結(jié)果的開銷極其昂貴。因此，能夠有效進行近似計算且具有高準確性的查詢方法具有很高的研究價值。傳統(tǒng)的近似查詢處理研究大多基于采樣方法，在查詢執(zhí)行過程中對數(shù)據(jù)進行動態(tài)采樣，以回答近似問題，或根據(jù)查詢負載預(yù)測，對表和列進行線下采樣，保存在內(nèi)存中，處理查詢?nèi)蝿?wù)。雖然傳統(tǒng)的近似查詢處理算法能基本處理近似查詢問題，但存在以下三個明顯缺陷：第一，錯誤率高、內(nèi)存開銷大；第二，算法無法支持許多重要的數(shù)據(jù)分析任務(wù)；第三，較低的查詢響應(yīng)時間，傳統(tǒng)的算法要求在大型數(shù)據(jù)分析集群上執(zhí)行并行查詢，但集群的獲取和使用的成本很高。針對以上問題，近期人工智能賦能的近似查詢處理引擎研究相關(guān)文獻比較如表8所示。

Ma等人[46]提出了一種基于機器學習模型的DBEst近似查詢引擎，引擎保證了對部分數(shù)據(jù)的聚集函數(shù)（例如，COUNT、SUM）進行高精度和高效近似查詢。DBEst的框架如圖14所示，DBEst首先離線對部分底層數(shù)據(jù)庫表和屬性采樣，根據(jù)樣本訓練密度估計器和回歸模型。DBEst 使用核密度估計[48]方法作為密度估計器，核密度估計能夠?qū)θ我饩S度的數(shù)據(jù)提供較高精度和較高效率的建模。回歸模型采用增強的回歸樹模型[49-52]，模型能夠從小樣本中構(gòu)建有效的數(shù)據(jù)模型。在查詢時，DBEst首先判斷是否存在模型支持近似查詢，對于模型能夠支持的查詢，DBEst利用密度估計器和回歸模型建立的數(shù)據(jù)分布推斷近似查詢結(jié)果。

Table 8 Comparison of approximate query processing engines表8 近似查詢處理引擎比較

Fig.14 Framework of DBEst proposed by Ma et al圖14 Ma等人提出的DBEst框架圖

Thirumuruganathan 等人[47]利用深度生成模型進行近似查詢處理，通過變分自編碼器（variational autoencoder，VAE）對整個數(shù)據(jù)庫或?qū)Χ鄠€不相交的子數(shù)據(jù)庫建模。在查詢時，DBMS（database management system）不需要訪問底層數(shù)據(jù)集，而根據(jù)深度生成模型生成大量查詢相關(guān)的數(shù)據(jù)樣本，并使用現(xiàn)有的近似查詢處理技術(shù)[53-54]計算查詢結(jié)果。由于生成模型不能準確地學習底層分布，生成的樣本將會產(chǎn)生誤差。為解決這一問題，作者提出一種基于拒絕抽樣的方法[55]縮小模型與真實數(shù)據(jù)的分布偏差，提升近似查詢的準確性。

通過分析兩種近似處理引擎的實驗數(shù)據(jù)，兩種近似處理引擎較當今最先進的近似查詢處理引擎在查詢準確率、查詢速度、查詢空間開銷方面皆存在較大的提升。其中，DBEst 即使只有較少的采樣數(shù)據(jù)，對部分聚集查詢的相對誤差不超過10%，說明模型泛化能力強，能夠從非常小的樣本構(gòu)建模型。同時DBEst的空間開銷比近似查詢處理引擎VerdictDB[56]低1～2個數(shù)量級，證明了模型的緊湊性。但對于復(fù)雜的查詢，文獻[52]提出的VAE模型的準確性更高。這是由于VAE 模型能夠生成任意數(shù)量的樣本，實現(xiàn)較低的查詢誤差。

3.2.5 索引選擇

索引選擇問題是查詢優(yōu)化問題的一部分，為特定數(shù)據(jù)集與查詢計劃確定最合適的索引方法?，F(xiàn)有的索引選擇器[57-61]根據(jù)查詢優(yōu)化器的代價模型，搜索具有最低執(zhí)行代價的索引配置。但由于優(yōu)化器的限制，在很多情況下，索引選擇器推薦的索引配置將提高查詢的執(zhí)行代價。

針對以上索引選擇存在的問題，研究人員引入機器學習方法用于索引選擇。近期人工智能賦能的索引選擇方法比較如表9 所示。Ding 等人[62]對索引選擇過程中面臨的關(guān)鍵問題，如何比較基于不同索引配置的兩個計劃的執(zhí)行代價進行研究。研究者將問題作為三元分類任務(wù)，對給定的兩個查詢計劃，首先提出一種編碼方式將查詢計劃編碼為維度相等的向量，然后利用分類器將代價較高的計劃標記為“退化”，將代價較低的計劃標記為“改進”，其他情況標記為“不確定”。Vu[63]提出使用深度神經(jīng)網(wǎng)絡(luò)建立索引選擇系統(tǒng)。首先計算數(shù)據(jù)集的直方圖矩陣并將其轉(zhuǎn)化為一個向量，然后將向量輸入深度神經(jīng)網(wǎng)絡(luò)模型中，模型根據(jù)索引性能預(yù)測最優(yōu)的數(shù)據(jù)索引。索引的性能指標使用基于抽樣的索引方法作為訓練數(shù)據(jù)。Qiu等人[64]針對基于代價模型的索引選擇方法無法準確估計索引的優(yōu)化效果和維護代價的問題，以及無法利用數(shù)據(jù)分布的缺陷提出了一個面向關(guān)系數(shù)據(jù)庫的智能索引選擇系統(tǒng)。系統(tǒng)由查詢分析、候選索引生成與索引選擇三部分組成。其中索引選擇模塊使用機器學習對索引優(yōu)化效果建模，計算每個候選索引的實用值，并設(shè)計遞歸算法選擇最優(yōu)索引。

Table 9 Comparison of index selection methods表9 索引選擇方法比較

3.2.6 學習查詢優(yōu)化器

以上基于人工智能的查詢優(yōu)化算法都是針對查詢優(yōu)化器的特定組件的研究，如查詢表示、基數(shù)估計、代價模型、連接枚舉器等，但研究大多都依賴于使用啟發(fā)式的優(yōu)化器估計基數(shù)、物理操作符選擇和執(zhí)行代價。文獻[65]提出了一個端到端的基于深度學習的查詢優(yōu)化引擎，利用多種深度學習模型替代傳統(tǒng)優(yōu)化器的多個組件，但以上研究并沒有接近于學習整個優(yōu)化器的方法。雖然這些研究較傳統(tǒng)方法的性能得到大幅度的提高，但并沒有證明以上的查詢優(yōu)化技術(shù)能夠達到最先進的性能。因此，學習整個優(yōu)化器具有較高的研究價值。若訓練后的查詢優(yōu)化器能與商業(yè)系統(tǒng)具有旗鼓相當?shù)膬?yōu)化性能，將大大降低查詢優(yōu)化器所需的開發(fā)與維護時間。

Marcus 等人[66]首次提出用于整個查詢優(yōu)化的端到端學習方法——神經(jīng)優(yōu)化器（Neo），包括連接排序、索引選擇以及物理操作符選擇。Neo的框架如圖15 所示，在Neo 運行之前，Neo 首先利用專家查詢優(yōu)化器（例如Selinger PostgreSQL）生成負載樣例中每個查詢的查詢計劃和查詢延遲，查詢計劃與查詢延遲加入經(jīng)驗數(shù)據(jù)集合中，用于訓練和更新查詢優(yōu)化器值模型。值模型是一個DNN 模型，模型的框架如圖16所示。值模型分別將獨立于查詢計劃的查詢特征與查詢計劃進行編碼和壓縮，合并成擴充樹，利用樹卷積方法[67]預(yù)測查詢計劃的最終執(zhí)行時間。在運行時，Neo 根據(jù)用戶的查詢請求與訓練后的值模型，通過最佳優(yōu)先搜索算法[68]在查詢計劃空間中迭代地搜索最低開銷的執(zhí)行計劃。從強化學習的角度看來，Neo 利用值模型的搜索過程其實是一種值迭代技術(shù)[69]，循環(huán)地評估值函數(shù)，并使用值函數(shù)改進策略。最后，將計劃搜索的結(jié)果輸入數(shù)據(jù)庫執(zhí)行引擎中，并將查詢的真實延遲記錄加入經(jīng)驗數(shù)據(jù)，改進值模型的參數(shù)。

Fig.15 Framework of Neo proposed by Marcus et al圖15 Marcus等人提出的Neo框架圖

Fig.16 Structure of value model proposed by Marcus et al圖16 Marcus等人提出的值模型結(jié)構(gòu)圖

3.2.7 聯(lián)合查詢優(yōu)化

除了以上介紹的查詢處理優(yōu)化新技術(shù)外，Xu 等人[70]也將人工智能技術(shù)用于優(yōu)化聯(lián)合查詢。聯(lián)合查詢是在包含第三方數(shù)據(jù)源的數(shù)據(jù)庫中執(zhí)行的具有跨數(shù)據(jù)庫連接的查詢。與傳統(tǒng)查詢執(zhí)行相似，聯(lián)合查詢首先生成查詢計劃，然后根據(jù)查詢計劃在多個數(shù)據(jù)庫執(zhí)行。查詢計劃在由每個數(shù)據(jù)源執(zhí)行完成后，數(shù)據(jù)庫選擇一個數(shù)據(jù)源作為聯(lián)合引擎執(zhí)行連接等操作。錯誤的聯(lián)合引擎選擇可能導致需要在數(shù)據(jù)源之間大量地移動數(shù)據(jù)，或不恰當?shù)貫槊總€組件分配工作。Xu等人提出基于隨機森林回歸的動態(tài)聯(lián)合引擎選擇，對于每個數(shù)據(jù)源使用大多數(shù)數(shù)據(jù)庫系統(tǒng)都可以提供的EXPLIAN PLAN 數(shù)據(jù)作為輸入，生成計劃運行時間，以此選擇聯(lián)合引擎。

現(xiàn)有AI賦能的查詢優(yōu)化技術(shù)研究主要集中于查詢優(yōu)化器的三個主要部分，連接順序優(yōu)化、代價模型與基數(shù)估計。同時也有部分工作對近似查詢處理、索引選擇、整體查詢優(yōu)化器與聯(lián)合查詢優(yōu)化進行研究。AI賦能的查詢優(yōu)化器結(jié)合機器學習與深度學習算法，根據(jù)查詢優(yōu)化經(jīng)驗、查詢結(jié)果與真實查詢性能改善查詢優(yōu)化策略，提高查詢基數(shù)與代價估計的準確性，在優(yōu)化性能上被證明接近甚至優(yōu)于傳統(tǒng)方法，并且能夠處理傳統(tǒng)方法難以優(yōu)化的復(fù)雜查詢問題。基于以上研究，對于查詢優(yōu)化器的重要部分仍有許多問題值得進一步研究。

針對連接順序優(yōu)化，現(xiàn)有工作的研究思路主要使用強化學習模型學習連接選擇策略，基于強化學習的連接順序優(yōu)化存在以下問題：（1）模型每次迭代根據(jù)查詢延遲真實值作為獎勵值調(diào)整神經(jīng)網(wǎng)絡(luò)參數(shù)，模型收斂的實際計算開銷很大。（2）傳統(tǒng)代價模型無法準確估計查詢代價，影響依賴于傳統(tǒng)代價模型的算法性能。（3）強化學習需要大量的訓練數(shù)據(jù)才能保證模型的性能。因此，無法應(yīng)用于數(shù)據(jù)庫構(gòu)建早期或缺乏訓練數(shù)據(jù)的場景。

針對代價模型，現(xiàn)有工作主要根據(jù)查詢計劃建立操作級或樹結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)模型預(yù)測查詢代價，面臨的主要挑戰(zhàn)是查詢計劃的特征選擇問題，手動特征表示可擴展性差且低質(zhì)量的特征表示將降低算法的性能，如何實現(xiàn)對查詢計劃中多種謂詞、邏輯符號、數(shù)據(jù)類型的自動編碼是亟待解決的問題之一。

針對基數(shù)估計問題，現(xiàn)有工作打破了傳統(tǒng)基數(shù)估計方法對數(shù)據(jù)均勻性、一致性和獨立性的假設(shè)，實現(xiàn)了更好的基數(shù)估計性能，已經(jīng)對數(shù)據(jù)庫性能產(chǎn)生良好的影響。與代價模型類似，基數(shù)估計也存在特征選擇的問題。此外，Sun 等人于文獻[34]提出的同時估計基數(shù)與代價的研究思路也值得進一步的研究。

3.3 智能系統(tǒng)調(diào)優(yōu)技術(shù)

如今，數(shù)據(jù)庫與大數(shù)據(jù)分析系統(tǒng)如Hadoop、Spark等都設(shè)有大量的配置參數(shù)，用于控制內(nèi)存分布、I/O優(yōu)化、并行處理與數(shù)據(jù)壓縮，錯誤的參數(shù)設(shè)置可能導致顯著的性能下降，并對穩(wěn)定性造成影響。而依靠有經(jīng)驗的數(shù)據(jù)管理員（DBA）對功能豐富、結(jié)構(gòu)復(fù)雜的數(shù)據(jù)庫系統(tǒng)進行配置、管理、調(diào)優(yōu)會使系統(tǒng)的總體擁有成本（total cost of ownership，TCO）變得很高。因此，為了有效地降低系統(tǒng)的總體擁有成本，數(shù)據(jù)庫自調(diào)優(yōu)是長久以來的研究問題[71]。配置參數(shù)調(diào)優(yōu)工作主要分為六類：基于規(guī)則的自動調(diào)優(yōu)、基于代價模型的自動調(diào)優(yōu)、基于模擬的自動調(diào)優(yōu)、實驗驅(qū)動的自動調(diào)優(yōu)、基于機器學習的自動調(diào)優(yōu)和自適應(yīng)調(diào)優(yōu)[72]。基于機器學習的自動調(diào)優(yōu)的優(yōu)點在于能夠捕捉復(fù)雜的系統(tǒng)動態(tài)，獨立于系統(tǒng)內(nèi)部和硬件且基于對系統(tǒng)性能的觀察數(shù)據(jù)進行學習。

（1）基于神經(jīng)網(wǎng)絡(luò)的調(diào)優(yōu)。Rodd等人[73]與Zheng等人[74]都提出使用神經(jīng)網(wǎng)絡(luò)估計工作負載的特定配置。前者利用緩存命中率與數(shù)據(jù)表大小通過神經(jīng)網(wǎng)絡(luò)計算緩存大小與共享內(nèi)存池大小。后者將數(shù)據(jù)緩沖區(qū)命中率、庫緩存命中率與內(nèi)存排序率輸入神經(jīng)網(wǎng)絡(luò)，輸出緩存大小、共享內(nèi)存池大小與PGA（process global area）聚合目標的參數(shù)數(shù)值。

（2）基于多種機器學習方法的調(diào)優(yōu)。Van Aken等人[75]提出一個多步驟的調(diào)優(yōu)工具Otter-Tune，通過學習歷史數(shù)據(jù)中DBA的經(jīng)驗值推薦可能的配置參數(shù)設(shè)置。Otter-Tune 首先分析對性能指標最有影響力的配置參數(shù)，并利用因子分析[76]與K-means[77]聚類將高維DBMS指標數(shù)據(jù)轉(zhuǎn)換為低維向量。刪除冗余指標后，Otter-Tune使用正則化的最小二乘法回歸模型Lasso[78]根據(jù)與系統(tǒng)性能的相關(guān)性對配置參數(shù)排序。在自動調(diào)優(yōu)時，Otter-Tune將目標工作負載的指標與已調(diào)優(yōu)的歷史負載的指標進行比較，匹配最相近的歷史負載，然后利用歷史負載訓練高斯過程回歸[79]，推薦配置參數(shù)值。

（3）基于強化學習的調(diào)優(yōu)。由于Otter-Tune采用流水線的學習模型，每步之間存在依賴關(guān)系，前一步的最優(yōu)解無法保證為后一步的最優(yōu)解，因此Zhang等人[80]設(shè)計了一種使用強化學習的端到端自動云數(shù)據(jù)庫調(diào)優(yōu)系統(tǒng)CDBTune。CDBTune使用深度確定性策略梯度（deep deterministic policy gradient，DDPG）模型[81]學習參數(shù)優(yōu)化策略，在高維連續(xù)空間中搜索最優(yōu)的配置參數(shù)值。在CDBTune中，狀態(tài)向量包含63個云數(shù)據(jù)庫的性能指標，獎勵值為執(zhí)行配置參數(shù)修改后的系統(tǒng)性能差異。在訓練中，CDBTune 利用試錯策略，避免了傳統(tǒng)強化學習模型中對大量訓練數(shù)據(jù)的需求，同時降低了陷入局部最優(yōu)的可能性。Li 等人[82]提出查詢敏感的數(shù)據(jù)庫調(diào)優(yōu)系統(tǒng)QTune，提供查詢級、負載級、簇級三種粒度的調(diào)優(yōu)。Li等認為，現(xiàn)有的深度強化學習模型忽略了查詢對環(huán)境狀態(tài)的影響，因此提出了雙狀態(tài)深度確定性策略梯度模型（doublestate deep deterministic policy gradient，DS-DDPG）進行查詢敏感的配置參數(shù)調(diào)優(yōu)。DS-DDPG模型的結(jié)構(gòu)如圖17所示，其中實線表示數(shù)據(jù)輸入，虛線表示調(diào)優(yōu)反饋，模型包括5個組件，其中預(yù)測器、執(zhí)行器與評價器都是深度神經(jīng)網(wǎng)絡(luò)。對于負載中的每個查詢，模型首先將查詢轉(zhuǎn)換為向量，輸入預(yù)測器中。預(yù)測器用于預(yù)測處理查詢前后外部性能指標差異。環(huán)境將指標差異與當前指標相加生成新的觀察值用于模擬查詢執(zhí)行后的性能指標。執(zhí)行器根據(jù)新的性能指標生成調(diào)優(yōu)動作，環(huán)境執(zhí)行動作并生成獎勵值發(fā)送給評價器，用于更新評價器參數(shù)，評價器為執(zhí)行器生成的動作計算得分（Q值），更新執(zhí)行器參數(shù)。DS-DDPG通過同時學習Q函數(shù)與策略解決連續(xù)空間中的最優(yōu)問題。

Fig.17 Structure of DS-DDPG proposed by Li et al圖17 Li等人提出的DS-DDPG模型結(jié)構(gòu)圖

除了有效的自動調(diào)優(yōu)方法外，查詢負載預(yù)測也能幫助數(shù)據(jù)庫系統(tǒng)提前選擇適當?shù)呐渲脜?shù)，適用于不同類型的查詢負載。Ma等人[83]提出QueryBot5000框架用于學習歷史負載數(shù)據(jù)預(yù)測數(shù)據(jù)庫未來工作負載?？蚣馨A(yù)處理、聚簇器與預(yù)測器三部分。預(yù)處理將大量查詢數(shù)據(jù)簡化為通用模板，聚簇器對模板根據(jù)到達率歷史進行聚類，預(yù)測模型使用核回歸與循環(huán)神經(jīng)網(wǎng)絡(luò)模型預(yù)測查詢模板聚類到達率模式作為輸出結(jié)果。

智能系統(tǒng)調(diào)優(yōu)技術(shù)能夠有效利用歷史負載信息與數(shù)據(jù)庫性能表現(xiàn)提高數(shù)據(jù)庫在查詢處理與優(yōu)化等多方面的性能?，F(xiàn)有工作提出了適應(yīng)不同的應(yīng)用場景的調(diào)優(yōu)模型，無需DBA 參與給出最優(yōu)的調(diào)優(yōu)推薦結(jié)果。對于智能系統(tǒng)調(diào)優(yōu)技術(shù)，還存在許多值得研究的問題，如：（1）對于硬件環(huán)境、負載和數(shù)據(jù)庫的動態(tài)變化，自調(diào)優(yōu)技術(shù)需要快速適應(yīng)并推薦參數(shù)配置。（2）模型訓練需要大量高質(zhì)量的樣本采集，如何降低訓練樣本依賴性需要進一步探討。

3.4 AI賦能的數(shù)據(jù)庫系統(tǒng)/原型系統(tǒng)分析

隨著數(shù)據(jù)庫系統(tǒng)的不斷革新，數(shù)據(jù)庫系統(tǒng)已逐漸滿足大數(shù)據(jù)時代的應(yīng)用要求，在多個領(lǐng)域起著舉足輕重的作用。但傳統(tǒng)數(shù)據(jù)庫仍存在諸多局限性亟待解決，如依賴于DBA 維護、缺乏特殊性等。因此，研究人員將人工智能技術(shù)應(yīng)用于數(shù)據(jù)庫系統(tǒng)中，提出了多種AI 賦能的數(shù)據(jù)庫系統(tǒng)與原型系統(tǒng)，利用人工智能技術(shù)優(yōu)化部分或全部數(shù)據(jù)庫系統(tǒng)的功能或組件，以實現(xiàn)數(shù)據(jù)庫系統(tǒng)的自優(yōu)化、自配置、自監(jiān)控等功能[84]。目前，工業(yè)界已發(fā)布了多個AI 賦能的數(shù)據(jù)庫系統(tǒng)，如Oracle自治云數(shù)據(jù)庫[85]、GaussDB[86]等。

近期AI 賦能的數(shù)據(jù)庫系統(tǒng)/原型系統(tǒng)研究如表10所示。Peloton[87]是第1個自主數(shù)據(jù)庫管理系統(tǒng)，無需DBA 指導，利用3.3 節(jié)中介紹的QueryBot5000 框架預(yù)測查詢負載，逐步優(yōu)化查詢延遲，且在部署期間不會對應(yīng)用程序造成明顯的影響。Oracle 自治云數(shù)據(jù)庫內(nèi)置機器學習算法支持基于負載特性的自動緩存、自適應(yīng)索引、高效壓縮與云數(shù)據(jù)加載，提升數(shù)據(jù)庫系統(tǒng)性能。同時，支持自治修補、自治更新、自動安全性管理以保證安全性。GaussDB 采用人工智能技術(shù)融入分布式數(shù)據(jù)庫的全生命周期，實現(xiàn)數(shù)據(jù)庫系統(tǒng)自運維、自管理、自調(diào)優(yōu)、故障自診斷、自愈合，其中自調(diào)優(yōu)性能比同類產(chǎn)品提升60%以上。此外，GaussDB還支持異構(gòu)計算。

Table 10 Comparison of AI-powered database systems/prototyping systems表10 AI賦能的數(shù)據(jù)庫系統(tǒng)/原型系統(tǒng)比較

Kraska等人在文獻[2]中提出了一個全新的數(shù)據(jù)庫原型——學習數(shù)據(jù)庫系統(tǒng)SageDB。SageDB 利用機器學習模型通過程序自動生成數(shù)據(jù)庫系統(tǒng)組件。作者對數(shù)據(jù)庫系統(tǒng)提出了新的展望，如果成功，將產(chǎn)生新一代的大數(shù)據(jù)處理工具，將更好地利用GPU（graphics processing unit）和TPU（tensor processing unit），且在存儲方面具有顯著優(yōu)勢。SageDB 與現(xiàn)代數(shù)據(jù)處理系統(tǒng)重視數(shù)據(jù)、硬件和負載的特性不同。SageDB 的架構(gòu)如圖18 所示，SageDB 主要分成兩部分，分別是機器學習和代碼生成。通過機器學習，對數(shù)據(jù)的分布、工作負載大小以及硬件進行建模，得到數(shù)據(jù)結(jié)構(gòu)、優(yōu)化的訪問方法和查詢計劃。代碼生成將學習的模型嵌入數(shù)據(jù)庫的各組件中。Kraska 等人分別在數(shù)據(jù)存取、查詢執(zhí)行、查詢優(yōu)化、先進分析等組件對SageDB進行初步的設(shè)計和實驗。實驗證明，SageDB 能夠有效提升數(shù)據(jù)庫性能，具有很高的研究價值。

Fig.18 Framework of SageDB proposed by Kraska et al圖18 Kraska等人提出的SageDB的架構(gòu)圖

AI 賦能的數(shù)據(jù)庫研究仍然處于早期階段，現(xiàn)有工作的設(shè)計目標主要針對數(shù)據(jù)庫特定方面的優(yōu)化，且沒有考慮模型之間的配合、通信與參數(shù)配置等問題。AI賦能的數(shù)據(jù)庫研究未來工作的主要目標是設(shè)計并實現(xiàn)具有高效數(shù)據(jù)存取、查詢的自主管理的學習數(shù)據(jù)庫系統(tǒng)。

3.5 小結(jié)

當前人工智能驅(qū)動的查詢處理與優(yōu)化技術(shù)在各方面都取得了一定的進展，但研究大多以對查詢優(yōu)化器中的各組件的優(yōu)化為主，其他組件仍然依賴于傳統(tǒng)數(shù)據(jù)庫系統(tǒng)的優(yōu)化器，而極少考慮整體優(yōu)化器的學習技術(shù)。雖然Marcus等人提出的Neo能夠?qū)W習整體優(yōu)化器，但訓練模型需要基于規(guī)則或代價的傳統(tǒng)優(yōu)化器提供模型的先驗知識，難以實現(xiàn)優(yōu)化器在不同數(shù)據(jù)庫的泛化?？梢?，人工智能驅(qū)動的查詢處理與優(yōu)化技術(shù)有待進一步研究，提高優(yōu)化器的性能。

4 主要挑戰(zhàn)

上述研究成果已在數(shù)據(jù)查詢處理與優(yōu)化的多方面提出了展望性的想法并進行了初步的實現(xiàn)，取得了一定的研究成果。從現(xiàn)有的研究思路與研究成果可以看出，AI 賦能的查詢處理與優(yōu)化技術(shù)研究中主要面臨如下挑戰(zhàn)。

（1）數(shù)據(jù)查詢處理與優(yōu)化問題的建模方法。查詢處理與優(yōu)化作為一個傳統(tǒng)的數(shù)據(jù)庫問題，當前大多數(shù)的數(shù)據(jù)庫系統(tǒng)都使用復(fù)雜的啟發(fā)式算法估計基數(shù)，預(yù)測代價，生成查詢計劃。但傳統(tǒng)的啟發(fā)式算法由于無法總結(jié)過去的經(jīng)驗，可能導致重復(fù)地生成次優(yōu)的查詢計劃。因此，研究者們通過一組SQL 查詢語句與元數(shù)據(jù)，構(gòu)建學習模型，解決查詢處理與優(yōu)化中的相關(guān)問題。在上文中總結(jié)的AI賦能的查詢處理與優(yōu)化新技術(shù)中，研究分別將傳統(tǒng)的查詢處理與優(yōu)化問題建模為不同的機器學習或深度學習問題。其中，不同的建模方式為問題的解決方法帶來了不同的優(yōu)勢。例如文獻[39]中，將選擇估計問題轉(zhuǎn)化為對有限樣本的聯(lián)合概率分布的密度估計問題，能夠有效支持點查詢與范圍查詢的基數(shù)估計，而利用查詢語句與真實基數(shù)估計值訓練的DNN模型則能夠在幾毫秒內(nèi)預(yù)測查詢基數(shù)。除此之外，問題的建模也對訓練開銷及對復(fù)雜查詢的適應(yīng)性產(chǎn)生了影響。因此，如何對不同場景中查詢處理與優(yōu)化問題的建模方法是AI賦能的查詢處理與優(yōu)化技術(shù)的主要挑戰(zhàn)之一。

（2）查詢的特征表示方法。神經(jīng)網(wǎng)絡(luò)等機器學習模型通常使用數(shù)值向量作為輸入，查詢的特征表示用于將查詢語句轉(zhuǎn)化為包含查詢信息與數(shù)據(jù)統(tǒng)計特性的數(shù)值特征向量。隨著研究的發(fā)展，傳統(tǒng)依賴于專家的手工特征選擇方法逐漸被替代，研究者們提出了多種適用于問題模型的特征提取與編碼方式，例如對物理查詢操作、查詢謂詞、元數(shù)據(jù)和數(shù)據(jù)進行one-hot 編碼，或利用學習模型學習查詢謂詞語義，生成嵌入向量等。建立語義豐富的向量化查詢表示作為模型的輸入，能夠有效提高模型的泛化能力。在建模過程中，必須要考慮適當?shù)牟樵兲卣鞅硎痉椒?，以保證模型的質(zhì)量。

（3）學習模型的訓練問題。在現(xiàn)有的AI 賦能的查詢處理與優(yōu)化技術(shù)中，大多數(shù)模型必須進行高質(zhì)量的參數(shù)訓練，但真實數(shù)據(jù)庫中，大規(guī)模的數(shù)據(jù)、多種查詢謂詞、聚合函數(shù)、數(shù)據(jù)表連接將導致稀疏的訓練數(shù)據(jù)采樣，無法獲得高質(zhì)量的訓練數(shù)據(jù)。例如，一數(shù)據(jù)庫中有6個包含5個屬性的數(shù)據(jù)表，每個屬性存在1 000種候選值，數(shù)據(jù)庫僅包含3個謂詞{＜，=，>}，該數(shù)據(jù)庫的采樣空間將包含6 048 000條不同的查詢語句。更重要的是，盡管現(xiàn)有的研究對所提出的方法在多個評價標準上進行了測試，但訓練和測試的場景依然十分有限，無法保證新技術(shù)的通用性。目前，在AI 賦能的查詢處理與優(yōu)化新技術(shù)中，只有少數(shù)研究關(guān)注于訓練過程，模型的訓練問題尚未獲得足夠的重視。

（4）學習模型的維護。目前的研究一般都假設(shè)數(shù)據(jù)庫模式和底層數(shù)據(jù)都是靜態(tài)的。雖然所學習的機器學習或深度學習模型能夠包容數(shù)據(jù)分布和相關(guān)性的細微變化，但是在某些情況下，學習模型必須進行調(diào)整或重新學習。因此，模型維護是當前AI 賦能的查詢處理與優(yōu)化技術(shù)的重要挑戰(zhàn)。模型維護必須研究的核心問題是是否有可能將知識從一個給定的模型轉(zhuǎn)移到另一個具有不同數(shù)據(jù)特征的模型中。學習模型的維護是AI賦能的查詢處理與優(yōu)化新技術(shù)仍需努力的方向。

5 未來研究方向展望

隨著技術(shù)的發(fā)展，機器學習與深度學習在數(shù)據(jù)管理領(lǐng)域被越來越多地研究，AI 賦能的查詢處理與優(yōu)化新技術(shù)引起了廣泛的關(guān)注，并且在多個工作中展現(xiàn)了巨大的潛力。但由于研究時間較短，仍有許多關(guān)鍵性問題值得深入探索。本文將對AI賦能的查詢處理與優(yōu)化技術(shù)總結(jié)為以下5個研究展望。

（1）智能高維數(shù)據(jù)存取新技術(shù)。當前的學習索引研究通過機器學習技術(shù)學習數(shù)據(jù)的分布預(yù)測數(shù)據(jù)所在的存儲位置，主要針對低維數(shù)據(jù)提出設(shè)想并進行測試與評估。然而在真實數(shù)據(jù)庫應(yīng)用中，高維數(shù)據(jù)已成為數(shù)據(jù)存儲的常態(tài)，高維數(shù)據(jù)的高效訪問需求不容小覷。隨著機器學習與深度學習算法的不斷發(fā)展，部分機器學習模型不僅能夠?qū)W習低維數(shù)據(jù)分布，還可以有效地捕捉復(fù)雜的高維數(shù)據(jù)關(guān)系，為高維數(shù)據(jù)存取技術(shù)提供了新的研究思路。因此，未來可針對高維數(shù)據(jù)的智能數(shù)據(jù)存取技術(shù)進行深入研究，將學習索引擴展到高維數(shù)據(jù)中，預(yù)測任意屬性組合的數(shù)據(jù)所在位置。

（2）端到端的學習查詢優(yōu)化器。在近期的人工智能研究中，端到端學習正逐漸成為一種熱門的學習方法。傳統(tǒng)方法通常將問題分解為子問題，例如傳統(tǒng)的圖像識別問題往往將圖像識別問題分解為預(yù)處理、特征提取和選擇、分類器設(shè)計等子問題，然后對子問題分別學習單元模型得到子問題的最優(yōu)解，但子問題的最優(yōu)解并不一定是全局問題的最優(yōu)解。端到端的學習范式則忽略人為的子問題劃分，模型直接學習由原始數(shù)據(jù)到期望輸出的映射函數(shù)。端到端的學習查詢優(yōu)化器能夠避免研究中子問題模型依賴于傳統(tǒng)數(shù)據(jù)庫優(yōu)化器的弊端，并能夠根據(jù)查詢的特征向量生成全局最優(yōu)的查詢計劃。在未來的工作中，探索端到端的學習查詢優(yōu)化器可能會為AI 賦能的查詢處理與優(yōu)化問題提供更多的見解。

（3）AI 賦能的時空數(shù)據(jù)查詢處理與優(yōu)化技術(shù)。隨著移動計算、全球定位系統(tǒng)、GIS 等相關(guān)技術(shù)的發(fā)展，大量現(xiàn)實世界中帶有時空信息的物理對象被存儲在數(shù)據(jù)庫中。時空數(shù)據(jù)作為常見的數(shù)據(jù)類型，常用于趨勢分析、進程建模和預(yù)測分析，應(yīng)用范圍遍及交通、氣象檢測、軍事等多個領(lǐng)域。在時空數(shù)據(jù)庫系統(tǒng)中，時空數(shù)據(jù)存儲與查詢處理是保證對時空對象有效建模的關(guān)鍵技術(shù)，已成為時空數(shù)據(jù)庫研究的焦點。如今，深度學習模型，如CNN 模型與RNN 模型已經(jīng)能夠?qū)臻g的內(nèi)接矩形與時間序列建模，這為智能數(shù)據(jù)存取技術(shù)擴展到時空數(shù)據(jù)提供了契機；而在現(xiàn)有的研究中，深度學習模型也被用于不同的時空問題中，如車流預(yù)測、旅行時間估計與駕駛行為分析等。由此可見，AI 驅(qū)動的時空數(shù)據(jù)查詢處理與優(yōu)化問題是未來具有前景的研究方向之一。

（4）面向圖數(shù)據(jù)庫的智能查詢處理與優(yōu)化技術(shù)。近年來社交、電商、物聯(lián)網(wǎng)等行業(yè)產(chǎn)生了龐大而復(fù)雜的關(guān)系網(wǎng)，傳統(tǒng)數(shù)據(jù)庫難以處理關(guān)系運算，圖數(shù)據(jù)庫應(yīng)運而生。圖數(shù)據(jù)庫使用圖結(jié)構(gòu)進行語義查詢，存儲數(shù)據(jù)含節(jié)點、邊和屬性。圖數(shù)據(jù)庫利用圖結(jié)構(gòu)相關(guān)算法，如最短路徑、節(jié)點度關(guān)系查找等，處理復(fù)雜的關(guān)系數(shù)據(jù)。雖然圖數(shù)據(jù)庫相比關(guān)系數(shù)據(jù)庫能夠有效提升數(shù)據(jù)管理效率，但常見的圖算法往往包含大量的針對整個圖的迭代計算，不利于查詢效率的提升，并增加了計算的開銷。近期，基于圖嵌入表示技術(shù)的圖算法研究已經(jīng)證明了AI技術(shù)在圖處理問題的巨大潛力，相信AI 技術(shù)將為圖數(shù)據(jù)庫的存儲與管理問題提供更優(yōu)的解決方案。

（5）面向云數(shù)據(jù)庫的智能查詢處理與優(yōu)化技術(shù)。第3 章所述的智能查詢處理與優(yōu)化技術(shù)大多數(shù)用于處理裸機服務(wù)器上執(zhí)行的查詢。但在云數(shù)據(jù)庫服務(wù)器中，數(shù)據(jù)庫的軟件與硬件能夠進行動態(tài)擴展，導致數(shù)據(jù)庫服務(wù)器的性能隨之變化，這種性能變化可以看作是隨機變化。為了應(yīng)對數(shù)據(jù)庫系統(tǒng)的動態(tài)變化，未來面向云數(shù)據(jù)庫的智能查詢處理與優(yōu)化技術(shù)研究可以通過獲取系統(tǒng)相對性能（例如，監(jiān)視I/O率、CPU周期等），或提出性能波動的檢測方法，利用遷移學習等技術(shù)降低模型的訓練時間，提升模型的自適應(yīng)性。

6 結(jié)束語

人工智能的發(fā)展為數(shù)據(jù)查詢處理與優(yōu)化技術(shù)帶來新的機遇，AI 賦能的查詢處理與優(yōu)化正在成為數(shù)據(jù)庫領(lǐng)域的一個重要熱點問題。近年來，AI 賦能的查詢處理與優(yōu)化新技術(shù)取得了眾多進展。本文主要圍繞AI 的查詢處理與優(yōu)化新技術(shù)進行介紹，梳理并分析了新的研究成果，總結(jié)了主要挑戰(zhàn)和未來研究方向發(fā)展。AI 賦能的數(shù)據(jù)庫技術(shù)發(fā)展前景廣闊，期望本文對高性能數(shù)據(jù)庫技術(shù)的研究發(fā)展有所助益。