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

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng)110169

1 引言

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

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

相比通用的數(shù)據(jù)查詢處理與優(yōu)化技術(shù)，人工智能賦能的查詢處理與優(yōu)化技術(shù)在執(zhí)行效率與性能方面具有明顯優(yōu)勢(shì)。在執(zhí)行效率方面，隨著硬件的計(jì)算能力的巨大提升，越來(lái)越多的設(shè)備配置了專門(mén)用于機(jī)器學(xué)習(xí)的硬件，例如，iphone的“Neural Engine”，谷歌手機(jī)的“Visual Core”，谷歌云的云端TPU以及微軟開(kāi)發(fā)的BrainWave等[2]。強(qiáng)大的計(jì)算能力大大降低了模型訓(xùn)練與運(yùn)行時(shí)間。從當(dāng)前的發(fā)展趨勢(shì)可以預(yù)見(jiàn)，機(jī)器學(xué)習(xí)、深度學(xué)習(xí)等技術(shù)的開(kāi)銷在未來(lái)可能忽略不計(jì)。因此，人工智能賦能的查詢處理與優(yōu)化新技術(shù)將提高數(shù)據(jù)查詢的執(zhí)行效率，降低時(shí)間開(kāi)銷。在性能方面，機(jī)器學(xué)習(xí)方法將自動(dòng)選擇使數(shù)據(jù)庫(kù)表現(xiàn)達(dá)到最優(yōu)的查詢計(jì)劃、配置參數(shù)或數(shù)據(jù)索引等，與數(shù)據(jù)庫(kù)管理員（database administrator，DBA）的手動(dòng)調(diào)優(yōu)相比，人工智能方法能夠解決有經(jīng)驗(yàn)的DBA 無(wú)法解決的問(wèn)題，同時(shí)避免了大量的手動(dòng)操作。與復(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)綜述工作中，文獻(xiàn)[3]對(duì)深度學(xué)習(xí)與數(shù)據(jù)庫(kù)領(lǐng)域的交叉問(wèn)題進(jìn)行了總結(jié)，分析了部分深度學(xué)習(xí)模型應(yīng)用于查詢接口、查詢計(jì)劃、眾包與知識(shí)庫(kù)、時(shí)空數(shù)據(jù)等數(shù)據(jù)庫(kù)應(yīng)用的可能性。文獻(xiàn)[4]總結(jié)了人工智能技術(shù)在數(shù)據(jù)庫(kù)系統(tǒng)的實(shí)現(xiàn)方式和存在問(wèn)題，選取有代表性的研究成果介紹了人工智能在數(shù)據(jù)庫(kù)多個(gè)方面的研究進(jìn)展并提出未來(lái)研究方向。文獻(xiàn)[5]概述了機(jī)器學(xué)習(xí)技術(shù)與數(shù)據(jù)庫(kù)關(guān)鍵組件中具體問(wèn)題的結(jié)合方式與存在的問(wèn)題，并分析了現(xiàn)有的問(wèn)題解決方式，對(duì)進(jìn)一步融合機(jī)器學(xué)習(xí)與數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)給出展望。文獻(xiàn)[6]從存儲(chǔ)管理、查詢優(yōu)化、自動(dòng)化數(shù)據(jù)庫(kù)管理系統(tǒng)三方面對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的機(jī)器學(xué)習(xí)化研究進(jìn)行歸納，分析已有技術(shù)并指出了未來(lái)研究方向及可能面臨的問(wèn)題與挑戰(zhàn)。

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

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

2 人工智能技術(shù)

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

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

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

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

2.2 強(qiáng)化學(xué)習(xí)

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

Fig.3 Example of reinforcement learning圖3 強(qiáng)化學(xué)習(xí)示意圖

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

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

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

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

CNN的主要優(yōu)勢(shì)在于：（1）能夠較好地適應(yīng)圖像的結(jié)構(gòu)；（2）同時(shí)進(jìn)行特征提取和分類，使特征提取有助于特征分類；（3）權(quán)值共享能夠減少網(wǎng)絡(luò)的訓(xùn)練參數(shù)，簡(jiǎn)化神經(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ù)“人的認(rèn)知是基于過(guò)往的經(jīng)驗(yàn)和記憶”這一觀點(diǎn)提出的特殊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。RNN以序列數(shù)據(jù)作為輸入，節(jié)點(diǎn)之間按時(shí)間順序連接成一個(gè)有向圖。RNN具有記憶性、權(quán)值共享并且圖靈完備，因此能以很高的效率對(duì)序列的非線性特征進(jìn)行學(xué)習(xí)。如今，RNN已成功地用于自然語(yǔ)言處理中[11]。

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

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

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

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)有的機(jī)器學(xué)習(xí)算法應(yīng)用到數(shù)據(jù)查詢的各個(gè)階段，要充分考慮這些特點(diǎn)和挑戰(zhàn)，甚至要探索新的定制化機(jī)器學(xué)習(xí)算法來(lái)滿足這些特殊需求。數(shù)據(jù)查詢處理與優(yōu)化任務(wù)區(qū)別于傳統(tǒng)AI 任務(wù)，主要包括以下四個(gè)技術(shù)挑戰(zhàn)。

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

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

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

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

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

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

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

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

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

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

3.1.1 基于B樹(shù)的混合型學(xué)習(xí)索引

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

Table 1 Learning indexes classification表1 學(xué)習(xí)索引研究分類

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

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

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

3.1.2 基于深度模型的學(xué)習(xí)索引

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

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

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

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

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

Fig.8 Improved learning Bloom filter proposed by Mitzenmacher圖8 Mitzenmacher提出的改進(jìn)的學(xué)習(xí)Bloom過(guò)濾器

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.2 查詢性能預(yù)測(cè)與學(xué)習(xí)代價(jià)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.4 近似查詢處理引擎

Fig.13 Reinforcement learning model proposed by Ortiz et al圖13 Ortiz等人提出的強(qiáng)化學(xué)習(xí)模型圖

Table 7 Experimental comparison of cardinality estimation methods表7 基數(shù)估計(jì)方法實(shí)驗(yàn)結(jié)果對(duì)比

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

Ma等人[46]提出了一種基于機(jī)器學(xué)習(xí)模型的DBEst近似查詢引擎，引擎保證了對(duì)部分?jǐn)?shù)據(jù)的聚集函數(shù)（例如，COUNT、SUM）進(jìn)行高精度和高效近似查詢。DBEst的框架如圖14所示，DBEst首先離線對(duì)部分底層數(shù)據(jù)庫(kù)表和屬性采樣，根據(jù)樣本訓(xùn)練密度估計(jì)器和回歸模型。DBEst 使用核密度估計(jì)[48]方法作為密度估計(jì)器，核密度估計(jì)能夠?qū)θ我饩S度的數(shù)據(jù)提供較高精度和較高效率的建模。回歸模型采用增強(qiáng)的回歸樹(shù)模型[49-52]，模型能夠從小樣本中構(gòu)建有效的數(shù)據(jù)模型。在查詢時(shí)，DBEst首先判斷是否存在模型支持近似查詢，對(duì)于模型能夠支持的查詢，DBEst利用密度估計(jì)器和回歸模型建立的數(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]利用深度生成模型進(jìn)行近似查詢處理，通過(guò)變分自編碼器（variational autoencoder，VAE）對(duì)整個(gè)數(shù)據(jù)庫(kù)或?qū)Χ鄠€(gè)不相交的子數(shù)據(jù)庫(kù)建模。在查詢時(shí)，DBMS（database management system）不需要訪問(wèn)底層數(shù)據(jù)集，而根據(jù)深度生成模型生成大量查詢相關(guān)的數(shù)據(jù)樣本，并使用現(xiàn)有的近似查詢處理技術(shù)[53-54]計(jì)算查詢結(jié)果。由于生成模型不能準(zhǔn)確地學(xué)習(xí)底層分布，生成的樣本將會(huì)產(chǎn)生誤差。為解決這一問(wèn)題，作者提出一種基于拒絕抽樣的方法[55]縮小模型與真實(shí)數(shù)據(jù)的分布偏差，提升近似查詢的準(zhǔn)確性。

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

3.2.5 索引選擇

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

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

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

3.2.6 學(xué)習(xí)查詢優(yōu)化器

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

Marcus 等人[66]首次提出用于整個(gè)查詢優(yōu)化的端到端學(xué)習(xí)方法——神經(jīng)優(yōu)化器（Neo），包括連接排序、索引選擇以及物理操作符選擇。Neo的框架如圖15 所示，在Neo 運(yùn)行之前，Neo 首先利用專家查詢優(yōu)化器（例如Selinger PostgreSQL）生成負(fù)載樣例中每個(gè)查詢的查詢計(jì)劃和查詢延遲，查詢計(jì)劃與查詢延遲加入經(jīng)驗(yàn)數(shù)據(jù)集合中，用于訓(xùn)練和更新查詢優(yōu)化器值模型。值模型是一個(gè)DNN 模型，模型的框架如圖16所示。值模型分別將獨(dú)立于查詢計(jì)劃的查詢特征與查詢計(jì)劃進(jìn)行編碼和壓縮，合并成擴(kuò)充樹(shù)，利用樹(shù)卷積方法[67]預(yù)測(cè)查詢計(jì)劃的最終執(zhí)行時(shí)間。在運(yùn)行時(shí)，Neo 根據(jù)用戶的查詢請(qǐng)求與訓(xùn)練后的值模型，通過(guò)最佳優(yōu)先搜索算法[68]在查詢計(jì)劃空間中迭代地搜索最低開(kāi)銷的執(zhí)行計(jì)劃。從強(qiáng)化學(xué)習(xí)的角度看來(lái)，Neo 利用值模型的搜索過(guò)程其實(shí)是一種值迭代技術(shù)[69]，循環(huán)地評(píng)估值函數(shù)，并使用值函數(shù)改進(jìn)策略。最后，將計(jì)劃搜索的結(jié)果輸入數(shù)據(jù)庫(kù)執(zhí)行引擎中，并將查詢的真實(shí)延遲記錄加入經(jīng)驗(yàn)數(shù)據(jù)，改進(jìn)值模型的參數(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ù)庫(kù)中執(zhí)行的具有跨數(shù)據(jù)庫(kù)連接的查詢。與傳統(tǒng)查詢執(zhí)行相似，聯(lián)合查詢首先生成查詢計(jì)劃，然后根據(jù)查詢計(jì)劃在多個(gè)數(shù)據(jù)庫(kù)執(zhí)行。查詢計(jì)劃在由每個(gè)數(shù)據(jù)源執(zhí)行完成后，數(shù)據(jù)庫(kù)選擇一個(gè)數(shù)據(jù)源作為聯(lián)合引擎執(zhí)行連接等操作。錯(cuò)誤的聯(lián)合引擎選擇可能導(dǎo)致需要在數(shù)據(jù)源之間大量地移動(dòng)數(shù)據(jù)，或不恰當(dāng)?shù)貫槊總€(gè)組件分配工作。Xu等人提出基于隨機(jī)森林回歸的動(dòng)態(tài)聯(lián)合引擎選擇，對(duì)于每個(gè)數(shù)據(jù)源使用大多數(shù)數(shù)據(jù)庫(kù)系統(tǒng)都可以提供的EXPLIAN PLAN 數(shù)據(jù)作為輸入，生成計(jì)劃運(yùn)行時(shí)間，以此選擇聯(lián)合引擎。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 小結(jié)

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

4 主要挑戰(zhàn)

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

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

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

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

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

5 未來(lái)研究方向展望

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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