孫洋洋，姚俊萍，李曉軍，范守祥，王自維

（1.火箭軍工程大學(xué) 301教研室，西安 710025；2.中國人民解放66133部隊(duì)，北京 100043；3.火箭軍工程大學(xué) 205教研室，西安 710025）

0 引言

由于全量維護(hù)僅適用于大量數(shù)據(jù)被修改的情形［1］、同步維護(hù)將會降低事務(wù)的速度［2］、定期維護(hù)無法滿足實(shí)時性需求［3］以及混合負(fù)載（Hybrid Transaction/Analytical Processing，HTAP）避免復(fù)雜耗時的抽取-轉(zhuǎn)換-加載（Extract-Transform-Load，ETL）進(jìn)而消除聯(lián)機(jī)分析處理（On-Line Analytical Processing，OLAP）滯后性的優(yōu)勢［4］，因此HTAP 物化視圖異步增量維護(hù)已經(jīng)成為物化視圖維護(hù)研究的熱點(diǎn)。

HTAP 物化視圖異步增量維護(hù)任務(wù)生成是HTAP 物化視圖異步增量維護(hù)的核心步驟，但是現(xiàn)有研究［5］主要為面向多記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成（簡稱為多記錄維護(hù)任務(wù)生成），無法實(shí)現(xiàn)面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成（簡稱為單記錄維護(hù)任務(wù)生成），導(dǎo)致磁盤IO 開銷的增加，進(jìn)而降低HTAP 物化視圖異步增量維護(hù)性能。基于此，本文開展了單記錄維護(hù)任務(wù)生成研究，實(shí)現(xiàn)了面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成，研究成果彌補(bǔ)了現(xiàn)有研究的不足。

1 相關(guān)研究

物化視圖的維護(hù)是在候選視圖物化代價(jià)預(yù)測、物化視圖選擇［6］之后需要解決的第3 個問題，目前已經(jīng)開展了十分豐富的研究。從維護(hù)時機(jī)方面，可以分為同步維護(hù)、異步維護(hù)和定期維護(hù)，后兩者也稱為延遲維護(hù)。在Vinh 等［7］開展的針對結(jié)構(gòu)化查詢語言（Structured Query Language，SQL）遞歸查詢的維護(hù)研究中，不難發(fā)現(xiàn)同步維護(hù)的特征為當(dāng)基表中數(shù)據(jù)變化后維護(hù)任務(wù)立即執(zhí)行。蔡磊等［8］開展的面向區(qū)塊鏈的維護(hù)研究中，在CPU 空閑時依次執(zhí)行維護(hù)任務(wù)隊(duì)列內(nèi)容，當(dāng)查詢到來時優(yōu)先維護(hù)與查詢相關(guān)的物化視圖，因此異步維護(hù)的特點(diǎn)是將維護(hù)任務(wù)推遲至合適時機(jī)執(zhí)行。定期維護(hù)在一段固定的時間后執(zhí)行，例如一天執(zhí)行一次維護(hù)［3］。從維護(hù)技術(shù)方面，可以分為全量維護(hù)和增量維護(hù)。全量維護(hù)是增量維護(hù)的替代方案，全量維護(hù)意味著一旦基表發(fā)生變化，物化視圖需要被完全覆蓋，因此僅僅適用于大量數(shù)據(jù)被修改的情形［1］。從Solank［9］基于輔助關(guān)系設(shè)計(jì)的維護(hù)過程中，可以得出增量維護(hù)的特點(diǎn)是僅僅維護(hù)“凈更改（net changes）”對應(yīng)的物化視圖。從服務(wù)對象方面，可以分為服務(wù)于OLAP 的維護(hù)和服務(wù)于HTAP 的維護(hù)。傳統(tǒng)的物化視圖維護(hù)任務(wù)是服務(wù)于OLAP 的，但是此時聯(lián)機(jī)事務(wù)處理（On-Line Transaction Processing，OLTP）與OLAP 之間存在隔閡，需要ETL 實(shí)現(xiàn)兩者的連接，導(dǎo)致OLAP 及其采用的物化視圖存在滯后性［10］。隨著工業(yè)界與學(xué)術(shù)界研究的不斷深入，同時支持OLTP 與OLAP 的HTAP 的出現(xiàn)解決了上述問題［11］。綜上，鑒于同步維護(hù)將會降低事務(wù)的速度［2］、定期維護(hù)無法滿足實(shí)時性需求［3］、全量維護(hù)僅適用于大量數(shù)據(jù)被修改的情形［1］以及HTAP 消除OLAP 滯后性的優(yōu)勢［4］，HTAP 物化視圖異步增量維護(hù)已經(jīng)成為物化視圖維護(hù)研究的熱點(diǎn)。

HTAP 物化視圖異步增量維護(hù)任務(wù)生成是HTAP 物化視圖異步增量維護(hù)的核心步驟，相關(guān)研究尚處于起步階段，目前僅有華東師范大學(xué)的Duan 等［5］于2020 年開展了相關(guān)研究，他們基于貪心算法在每一輪迭代中對多記錄維護(hù)任務(wù)生成所需的訪問任務(wù)（簡稱為多記錄訪問任務(wù)，單記錄維護(hù)任務(wù)生成所需的訪問任務(wù)簡稱為單記錄訪問任務(wù)）進(jìn)行匹配，目標(biāo)是發(fā)現(xiàn)磁盤訪問范圍最為相似即多記錄維護(hù)任務(wù)生成效益最高的一組多記錄訪問任務(wù)和事務(wù)。Duan 等的研究［5］實(shí)現(xiàn)了在執(zhí)行成本增長約束下盡可能多地合并執(zhí)行多記錄訪問任務(wù)和事務(wù)，一定程度上減少了磁盤IO 開銷，提高了HTAP 物化視圖異步增量維護(hù)性能；但是當(dāng)訪問任務(wù)和事務(wù)涉及單記錄時，Duan 等的研究［5］無法根據(jù)訪問范圍計(jì)算維護(hù)任務(wù)生成代價(jià)，訪問任務(wù)和事務(wù)的獨(dú)立執(zhí)行消耗大量的磁盤IO 開銷，進(jìn)而降低HTAP 物化視圖異步增量維護(hù)性能，因此，單記錄維護(hù)任務(wù)生成已經(jīng)成為HTAP 物化視圖異步增量維護(hù)任務(wù)的研究重點(diǎn)。

已有多記錄維護(hù)任務(wù)生成算法主要基于貪心算法［5］，貪心算法靜態(tài)設(shè)置的約束條件無法適應(yīng)維護(hù)任務(wù)生成過程中存在的HTAP 的變化、數(shù)據(jù)量的增減和硬件的更新等負(fù)載和環(huán)境的動態(tài)變化。隨著強(qiáng)化學(xué)習(xí)的不斷發(fā)展，數(shù)據(jù)庫領(lǐng)域與強(qiáng)化學(xué)習(xí)相結(jié)合已經(jīng)成為必然的趨勢；因此將單記錄維護(hù)任務(wù)生成過程建模為馬爾可夫決策過程（Markov Decision Process，MDP）并基于智能體與環(huán)境交互實(shí)現(xiàn)自適應(yīng)負(fù)載和環(huán)境的動態(tài)變化，將是單記錄維護(hù)任務(wù)生成未來十分具有前景的研究方向。

強(qiáng)化學(xué)習(xí)是與無監(jiān)督學(xué)習(xí)、有監(jiān)督學(xué)習(xí)并列的第三種機(jī)器學(xué)習(xí)范式，具體可以分為無模型強(qiáng)化學(xué)習(xí)［12］和模型化強(qiáng)化學(xué)習(xí)［13］。模型化強(qiáng)化學(xué)習(xí)首先利用智能體與環(huán)境交互獲得的數(shù)據(jù)建立環(huán)境模型［14］，然后利用環(huán)境模型決定下一步動作。當(dāng)面對的問題具有復(fù)雜的狀態(tài)動作空間時，準(zhǔn)確估計(jì)環(huán)境模型存在巨大挑戰(zhàn)［15］，無模型強(qiáng)化學(xué)習(xí)中智能體通過與未知環(huán)境交互并根據(jù)反饋決定下一步動作，因此無需提前擬合出環(huán)境模型。無模型強(qiáng)化學(xué)習(xí)具體可以分為基于策略梯度和基于價(jià)值函數(shù)兩種類型［16］?；诓呗蕴荻鹊臒o模型強(qiáng)化學(xué)習(xí)廣泛應(yīng)用于連續(xù)型強(qiáng)化學(xué)習(xí)問題之中［17］，并不適用于具有離散動作空間的單記錄維護(hù)任務(wù)生成問題；基于價(jià)值函數(shù)的無模型強(qiáng)化學(xué)習(xí)主要分為狀態(tài)-動作-獎勵-狀態(tài)-動 作（State-Action-Reward-State-Action，SARSA）算法和Q-learning 算法［15］。SARSA 算法于1994 年提出，是一種同軌策略算法，采用ε-貪心算法更新動作與價(jià)值函數(shù)［18］；Q-learning 算法最早由Watkins［19］于1989 年提出，是一種離軌策略算法，采用ε-貪心算法更新動作，采用貪心算法更新價(jià)值函數(shù)。SARSA 算法和Q-learning 算法的區(qū)別在于價(jià)值函數(shù)的更新［20］：前者采用ε-貪心算法，后者采用貪心算法。雖然SARSA 算法具有更快的收斂速度，但是其容易陷入局部最優(yōu)解［21］，因此本文采用Q-learning 算法進(jìn)行單記錄維護(hù)任務(wù)生成研究。

2 面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成效益模型

本文研究的目標(biāo)為通過合并執(zhí)行單記錄訪問任務(wù)和事務(wù)來減少磁盤IO 開銷，因此在2.1 節(jié)首先需要對基于單記錄訪問任務(wù)和事務(wù)生成單記錄維護(hù)任務(wù)過程進(jìn)行形式化；與此同時，單記錄訪問任務(wù)和事務(wù)的匹配是否合理，需要相關(guān)效益模型進(jìn)行量化評價(jià)，因此在2.2 節(jié)對單記錄維護(hù)任務(wù)生成效益模型進(jìn)行詳細(xì)闡述。

2.1 形式化基于單記錄訪問任務(wù)和事務(wù)生成單記錄維護(hù)任務(wù)過程

在實(shí)際應(yīng)用中，物化視圖往往基于多個基表構(gòu)建，第x個查詢Qx可以表示為：

其中：??表示連接運(yùn)算。對于包含GROUP、LIMIT 等運(yùn)算類型的查詢，可以在式（1）的基礎(chǔ)上進(jìn)行元素的豐富，例如包含GROUP 的查詢可以表示為：

其中：Gx表示Qx中GROUP 部分包含的元素。結(jié)合式（1），物化視圖Mx表示為：

其中：π表示投影運(yùn)算。結(jié)合式（2），可以將式（4）改寫為：

1）插入事務(wù)觸發(fā)的單記錄維護(hù)任務(wù)生成。

當(dāng)向基表中的i位置插入記錄時，的增量出現(xiàn)，此時表示為：

此時基表的集合Tx產(chǎn)生的增量dnewTx代表著插入事務(wù)觸發(fā)生成的單記錄維護(hù)任務(wù)，表示為：

2）刪除事務(wù)觸發(fā)的單記錄維護(hù)任務(wù)生成。

此時Tx產(chǎn)生的增量doldTx代表著刪除事務(wù)觸發(fā)生成的單記錄維護(hù)任務(wù)，表示為：

3）更新事務(wù)觸發(fā)的單記錄維護(hù)任務(wù)生成。

此時Tx產(chǎn)生的增量dupdTx代表著更新事務(wù)觸發(fā)生成的單記錄維護(hù)任務(wù)，表示為：

2.2 單記錄維護(hù)任務(wù)生成效益模型

結(jié)合式（7）（9）和（11），基于多個基表構(gòu)建的物化視圖在單個或多個基表發(fā)生插入、刪除和更新時失效，此時單個基表的增量并不等價(jià)于單記錄維護(hù)任務(wù)，還需要訪問其他基表與對應(yīng)的部分，此時單記錄訪問任務(wù)產(chǎn)生。對于大量的單記錄訪問任務(wù)，可以通過在處理后續(xù)事務(wù)的過程中順帶完成，即通過合并執(zhí)行單記錄訪問任務(wù)與事務(wù)，實(shí)現(xiàn)共享磁盤IO，進(jìn)而提高HTAP 物化視圖異步增量維護(hù)性能。

本文研究的目標(biāo)為通過匹配執(zhí)行單記錄訪問任務(wù)和事務(wù)減少磁盤IO 開銷。每秒進(jìn)行讀寫操作次數(shù)（Input/output Operations Per Second，IOPS）是衡量磁盤IO 開銷的主要指標(biāo)，IOPS 越低，單記錄訪問任務(wù)和事務(wù)合并執(zhí)行后占用的系統(tǒng)資源越低。IOPS 的計(jì)算方式［22］如下：

其中：Tseek代表尋道時間，Trotation代表旋轉(zhuǎn)延遲。因此面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成效益模型可以表示為：

3 基于Q-learning 的面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成算法

3.1 Q-learning算法

Q-learning 算法主 要由環(huán) 境（Environment）、智能體（Agent）、狀態(tài)（State）、動作（Action）和獎勵（Reward）這5 部分組成，如圖1 所示。

圖1 Q-learning算法結(jié)構(gòu)Fig.1 Structure of Q-learning algorithm

Agent 做 出Action，Environment 的State 發(fā)生轉(zhuǎn) 移，Environment 隨后對Agent 的Action 給予Reward。Agent 通 過不斷地與Environment 進(jìn)行交互，從每個State 的累積收益值中選擇最大值對應(yīng)的Action 形成其最優(yōu)策略。接下來詳述Q-learning 算法的各個組成部分［23］。

1）Environment。

本文通過單記錄訪問任務(wù)與事務(wù)的匹配生成單記錄維護(hù)任務(wù)，由于單記錄訪問任務(wù)和事務(wù)發(fā)生在數(shù)據(jù)庫之中，因此本文將支持HTAP 和物化視圖的數(shù)據(jù)庫作為Environment。

2）Agent。

單記錄維護(hù)任務(wù)生成本質(zhì)上屬于計(jì)算機(jī)操作系統(tǒng)（Operating System，OS）的磁盤存儲器管理問題。當(dāng)進(jìn)程即本文中的單記錄訪問任務(wù)和事務(wù)試圖從磁盤訪問數(shù)據(jù)時，OS 使用磁盤調(diào)度算法將磁頭從當(dāng)前位置移動到包含所需扇區(qū)的磁盤面。由于磁頭的Action 是唯一可以與Environment進(jìn)行交互的元素，因此本文將磁頭設(shè)置為Agent。

3）Action。

Agent 負(fù)責(zé)做出Action，即磁頭負(fù)責(zé)在各個扇區(qū)移動，實(shí)現(xiàn)了單記錄訪問任務(wù)和事務(wù)的合并執(zhí)行，進(jìn)而決定了單記錄維護(hù)任務(wù)的生成；因此是否將單記錄訪問任務(wù)和事務(wù)進(jìn)行的合并是Agent 的Action，即Action=｛合并，不合并｝。

4）State。

Agent 做出Action，Environment 的State 發(fā)生轉(zhuǎn)移，State 所發(fā)生的轉(zhuǎn)移本質(zhì)上是單記錄訪問任務(wù)和事務(wù)的匹配情況，因此本文將單記錄訪問任務(wù)和事務(wù)的匹配情況視為State。

5）Reward。

Environment 的State 發(fā)生轉(zhuǎn)移，Environment 隨后對Agent的Action 給予Reward，本文將單記錄維護(hù)任務(wù)生成效益即式（13）等價(jià)于Reward。

3.2 MVM_QL

通過將單記錄維護(hù)任務(wù)生成過程建模為MDP?；赒-learning 的面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成算法（Materialized View Asynchronous Incremental Maintenance Task Generation Algorithm under HTAP for Single Record based on Q-learning，MVAIMTGAHTAPSRQ）為便于表述，本文后續(xù)部分將MVAIMTGAHTAPSRQ 簡寫為MVM_QL。MVM_QL 可以基于智能體與環(huán)境的交互，實(shí)現(xiàn)自適應(yīng)HTAP的變化、數(shù)據(jù)量的增減和硬件的更新等負(fù)載和環(huán)境的動態(tài)變化。MVM_QL 的具體流程如算法1 所示。

算法1 MVM_QL。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 參數(shù)設(shè)置

實(shí)驗(yàn)采用的數(shù)據(jù)倉庫為某云服務(wù)供應(yīng)商提供的支持HTAP 的AnalyticDB PostgreSQL，參數(shù)設(shè)置見表1。實(shí)驗(yàn)采用的數(shù)據(jù)來源于美國交易處理效能委員會提供的商業(yè)智能計(jì)算測試數(shù)據(jù)集TPC-H。

表1 AnalyticDB PostgreSQL 參數(shù)設(shè)置Tab.1 Parameter setting of AnalyticDB PostgreSQL

MVM_QL 的回合數(shù)max_episodes、學(xué)習(xí)率α、折扣因子γ、貪婪度ε等參數(shù)設(shè)置如表2 所示。

表2 MVM_QL參數(shù)設(shè)置Tab.2 Parameter setting of MVM_QL

為了模擬HTAP 的變化，本文開展了10 組實(shí)驗(yàn)，每組實(shí)驗(yàn)需要完成隨機(jī)生成的7 個單記錄訪問任務(wù)和7 個事務(wù)的匹配。為了模擬硬件的更新，1、3、5、7 和9 號實(shí)驗(yàn)硬件配置為2C16GB，2、4、6、8 和10 號實(shí)驗(yàn)硬件配置為4C32GB。為了研究MVM_QL 在不同數(shù)據(jù)量下的性能，實(shí)驗(yàn)采用的TPC-H 基表的數(shù)據(jù)量依次為0.03 GB、0.09 GB、0.15 GB、0.21 GB 和0.27 GB。實(shí)驗(yàn)過程中數(shù)據(jù)量與環(huán)境的設(shè)置見表3。

表3 數(shù)據(jù)量與環(huán)境的設(shè)置Tab.3 Setting of data size and environment

4.2 結(jié)果分析

表4 展示了基于MVM_QL 與無算法指導(dǎo)的單記錄維護(hù)任務(wù)生成在平均IOPS 方面的對比，MVM_QL 整體上顯著優(yōu)于無算法。

表4 平均IOPSTab.4 Average IOPS

平均IOPS 的最大值和最小值方面，MVM_QL 次數(shù)分別為8.85 和8.22，無算法次數(shù)分別為18.65 和17.31，因此在平均IOPS 的最大值和最小值方面MVM_QL 仍然顯著優(yōu)于無算法。id 為7 的實(shí)驗(yàn)中，MVM_QL 展現(xiàn)出了最優(yōu)性能，低于無算法10.07 次。綜上，本研究已經(jīng)取得了較好的效果。

同時對CPU 利用率進(jìn)行了觀察，表5 展示了基于MVM_QL 與無算法指導(dǎo)的單記錄維護(hù)任務(wù)生成在平均CPU（2 核）利用率方面的對比，MVM_QL 整體上顯著優(yōu)于無算法。

表5 平均CPU（2核）利用率 單位：%Tab.5 Average utilization of CPU（2-core） unit：%

平均CPU（2 核）利用率的最大值和最小值方面，MVM_QL 分別為1.81%和1.45%，無算法分別為4.00%和3.49%，因此在平均CPU（2 核）利用率的最大值和最小值方面MVM_QL 仍然顯著優(yōu)于無算法。id 為7 的實(shí)驗(yàn)中，MVM_QL 展現(xiàn)出了最優(yōu)性能，低于無算法2.19 個百分點(diǎn)。MVM_QL 和無算法的平均CPU（2 核）利用率隨著數(shù)據(jù)量的增加而明顯上升。

表6 展示了基于MVM_QL 與無算法指導(dǎo)的單記錄維護(hù)任務(wù)生成在平均CPU（4 核）利用率方面的對比，MVM_QL 整體上顯著優(yōu)于無算法。

表6 平均CPU（4核）利用率 單位：%Tab.6 Average utilization of CPU（4-core）unit：%

平均CPU（4 核）利用率的最大值和最小值方面，MVM_QL 分別為0.89%和0.71%，無算法分別為1.91%和1.73%，因此在平均CPU（4 核）利用率的最大值和最小值方面MVM_QL 仍然顯著優(yōu)于無算法。id 為2 的實(shí)驗(yàn)中，MVM_QL 展現(xiàn)出了最優(yōu)性能，低于無算法1.08 個百分點(diǎn)。

5 結(jié)語

本文建立了面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成的效益模型，設(shè)計(jì)了基于Q-learning 的面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成算法。實(shí)驗(yàn)結(jié)果表明，本文提出的MVM_QL 實(shí)現(xiàn)了面向單記錄的HTAP 物化視圖異步增量維護(hù)任務(wù)生成，減小了IOPS、CPU 利用率等系統(tǒng)資源利用率，減少了磁盤IO，對于進(jìn)一步提升HTAP 物化視圖異步增量維護(hù)性能具有的重要理論和應(yīng)用價(jià)值。本文僅采用IOPS 作為評價(jià)生成的單記錄維護(hù)任務(wù)優(yōu)劣的指標(biāo)，因此發(fā)掘IOPS、內(nèi)存利用率、CPU 利用率等內(nèi)在關(guān)系并建立多元評價(jià)模型，將是下一步的研究重點(diǎn)。