基于強化學習的數據庫多屬性索引推薦

摘 要：傳統關系型數據庫通過人工方式進行索引推薦，已無法適應日益增長的數據需求，而機器學習技術可以有效地解決數據庫索引選擇問題。針對以往僅在靜態數據庫下進行索引推薦且無法及時更新索引配置的局限性，提出了一種基于強化學習算法實現為數據庫數據動態變化情況下的一組工作負載推薦最佳多屬性索引配置的方法（multi-attribute index intelligent recommendation approach，MIRA）。在公開的TPC-H數據集上的實驗結果表明，該方法不僅能有效地為一組工作負載推薦最佳的索引配置，而且優于自定義的比較基線和相關強化學習方法。

關鍵詞：索引優化； 索引推薦； 強化學習； 關系型數據庫； 動態數據庫

中圖分類號：TP391 文獻標志碼：A

文章編號：1001-3695（2023）06-030-1789-05

doi：10.19734/j.issn.1001-3695.2022.11.0536

MIRA：database multi-attribute index recommendation based on reinforcement learning

Yu Wenbo You Jinguo Niu Xiangyu

（a.Faculty of Information Engineering amp; Automation， b.Key Laboratory of Artificial Intelligence in Yunnan Province， Kunming University of Science amp; Technology， Kunming 650500， China）

Abstract：Traditional relational databases use the artificial way to achieve index recommendations that can no longer meet the growing requirement of data， and using machine learning technology can effectively solve the index optimization problem of databases. The limitation that only recommended the index in a static database and couldn’t update the index configuration in time， this paper proposed a multi-attribute index intelligent recommendation approach （MIRA） to recommend multi-attri-bute index configurations for a set of workloads using reinforcement learning under databases with dynamically changing data. Experimental results on TPC-H datasets show that MIRA can effectively recommend the optimal index configuration for workload， and outperforms the defined comparison baselines and related reinforcement learning methods.

Key words：index optimization; index recommendation; reinforcement learning; relational database; dynamic database

0 引言

索引是一種有序的物理存儲的數據結構，存儲于數據庫管理系統（database management system，DBMS）中，可以有效地提高一組工作負載在數據庫中的查詢效率［1，2］。然而，為數據庫中給定的一組工作負載選擇合適的索引配置并不是一項簡單的任務，因為它已經被證明是一個NP-hard問題［3］。簡單來說，索引選擇問題就是在給定的一組工作負載和其他限制的情況下，選擇合適的索引來最大化地提高該組工作負載在數據庫中的查詢性能。索引的建立與否都將直接影響到數據庫的查詢性能。創建合適的索引可以有效地提高數據庫的查詢性能；相反，創建不合適的索引或者過多的索引不僅會降低數據庫的查詢性能，而且還會增加維護索引的成本。雖然目前存在一些主流的數據庫管理系統的最新版本能夠自動地調整索引，如Oracle［4］和Azure SQL［5］數據庫，然而這些數據庫管理系統在大多數情況下只是給出索引優化的建議，最終還是通過數據庫管理員（database administrator，DBA）來決定是否執行，無法真正意義上地實現為數據庫中給定一組工作負載自主地推薦索引。雖然DBA可以根據其專業知識和經驗為關系型數據庫中的一組工作負載選擇合適的索引配置，但是這種依賴于人工進行索引選擇的方式存在著以下三方面的局限性：a）過度依賴于DBA的專業知識與經驗；b）當關系型數據庫中數據或者工作負載發生變化時，DBA往往無法及時地更新索引，從而導致數據庫性能下降；c）DBA需要時刻地維護索引，一旦出現疏忽將會造成巨大損失。

近年來，隨著人工智能（artificial intelligence，AI） 技術的不斷興起，研究人員已經逐漸地將人工智能技術應用于數據庫管理系統的自調優［6～8］領域，其中SQL的自優化也是利用機器學習技術來實現的，例如采用深度強化學習算法來實現SQL的連接順序改寫［9］、使用機器學習的手段來預測不同的索引對用戶查詢優化的效果［10］，以及通過采用強化學習方法來為數據庫中給定的一組工作負載推薦最佳的索引配置［11，12］等。其中文獻［11］設計了一種強化學習算法為數據庫下的一組工作負載推薦最佳的索引配置；文獻［12］則是通過設計五種啟發式規則并將其用于從工作負載中提取索引候選項來減少動作空間與狀態空間的維度大小，同時采用深度強化學習算法實現索引的自主推薦。雖然他們的工作都能成功地為數據庫中給定的一組工作負載選擇合適的索引配置，但是這些使用機器學習來實現索引自優化的方法中仍存在一些改進之處。

文獻［11］的方法僅推薦單屬性索引，忽略了組合索引存在的情況；其次沒有考慮工作負載的特性，忽略了根據工作負載的特性來提取候選項并用于索引推薦。文獻［12］提出的方法無法及時地對數據庫中的索引配置進行更新，該方法只能通過不斷地創建索引來降低工作負載在數據庫中的執行成本，從而提高該組工作負載的查詢效率；其次，該方法沒有模擬實際數據庫生產環境，忽略了數據庫數據動態發生改變的情況。簡單來說，數據庫中某些表的數據可能存在著插入數據與刪除數據兩種操作。為了解決上述問題，本文設計了一種采用強化學習算法為數據庫數據動態變化下的一組工作負載推薦多屬性索引的方法MIRA，主要分為兩步驟：根據啟發式規則［12］從工作負載中提取索引候選項；通過強化學習算法實時地更新索引配置，從而為該組工作負載推薦最佳的索引配置。 本文的主要貢獻如下：a）同時考慮了一組工作負載的特性與數據庫數據實時發生變化的情況，模擬了數據庫的實際生產環境；b）MIRA采用強化學習算法實現對索引配置進行實時更新，有效地防止了性能回歸；c）通過power@size、throughput@size和QphH@size等評價指標來評估所有的實驗效果，證明了MIRA方法的優越性。

1 相關工作

近年來，將機器學習融入到傳統關系型數據庫或非關系型（NoSQL）數據庫中來實現數據庫管理系統中組件的智能化已經成為現代數據庫管理系統的一種發展趨勢。機器學習不僅能幫助數據庫管理系統實現各個功能組件的自優化，還可以協助DBA實現數據的自動管理［13］。通過將AI技術融入到數據庫管理系統中，可以有效地解決當下傳統數據庫管理系統在面臨海量數據存儲時查詢效率低與無法及時調優的局限性，同時也會促進AI4DB ［14］的發展。實現數據庫自調優的方法有很多種，其中包括索引選擇［15，16］、連接順序選擇［9，17］等手段，其中索引調優是實現數據庫自優化的重中之重。然而實現索引的自調優不是一項簡單的任務，往往需要考慮許多方面，例如工作負載的特性以及數據的變化情況等多方面。索引的創建會直接影響到數據庫管理系統的查詢性能與事務負載處理能力［18］。然而，創建索引并不意味著在數據庫中所有的列上都建立索引或在所有的索引候選項上都建立索引，而是要選擇合適的列或索引候選項執行創建索引操作，這樣才能有效地提高數據庫的查詢性能；相反，創建過多的索引反而會造成性能回歸。目前有不少使用傳統方法和強化學習算法來解決數據庫中索引選擇問題的相關工作。文獻［19］比較和歸納了八種傳統推薦索引算法的優劣，分別從不同的層面進行比較，如工作負載執行成本的降低百分比、算法的執行效率等；此外還設計了一個自動化的索引算法選擇系統，可以在不同的場景下選擇最合適的算法為一組工作負載推薦索引。采用強化學習實現索引選擇的工作則有許多，如為分布式集群數據庫推薦索引［20］、NoSQL數據庫索引推薦［21］等，其中也包括文獻［11，12］的方法。本文提出的MIRA方法主要是針對文獻［11，12］中存在的不足進行改進，不僅解決了傳統數據庫采用人工方式進行索引調優時的局限性，而且通過采用強化學習算法實現了為數據庫數據變化下的一組工作負載實時地推薦最佳的多屬性索引配置，極大地提高了查詢效率。

2 MIRA方法

2.1 強化學習概述

2.2 索引選擇問題定義

2.3 索引候選項的生成與動作定義

索引候選項的生成與動作選擇如圖2所示。

a）索引候選項的提取。查詢語句被解析成查詢解析樹，然后對其屬于同一個表上的字段組合，其任意字段的組合都可以作為候選索引。然而， 對所有的字段進行組合會生成巨大的索引候選空間，并且不是所有的組合都會提升查詢性能。因此采用文獻［11］提出的啟發式規則對解析后的查詢樹進行索引候選項的提取，并添加到索引候選集（索引候選項1，…，索引候選項N）中。

b）動作定義。索引候選項包括兩種動作，即創建索引和刪除索引。智能體基于ε-greedy策略選中索引候選項N，然后根據N的狀態標志符執行相應的動作。例如，當狀態標志符為0時，表示該索引候選項未建立索引，智能體執行創建索引動作；如果對應的狀態標志符為1，表示該索引候選項已建立索引，智能體執行刪除索引動作。

2.4 多屬性索引智能推薦方法

2.4.1 概述

本文提出了一種使用強化學習算法為數據庫數據動態變化下給定的一組工作負載推薦多屬性索引的方法，有效地解決了文獻［11，12］方法中的不足并對其進行了改進。MIRA主要考慮了以下三個方面：a）數據庫中某些表的數據時刻在發生改變，通過設置刷新函數1（refresh function 1，RF1）和刷新函數2（RF2）實時地對Orders、Lineitem表進行隨機插入數據操作和刪除數據操作來模擬實際生產環境下的數據庫數據發生變化的情況;b）利用啟發式規則［12］來提取一組工作負載中的索引候選項并將其融入到MIRA算法中，而不是僅考慮在數據庫的單列上創建索引［11］;c）采用強化學習算法實時地對索引配置進行更新，充分地考慮了不同索引之間存在的交互性，極大地提高了數據庫的查詢效率。

2.4.2 獎勵函數

2.4.3 體系架構

2.4.4 多屬性索引智能推薦算法

數據庫的索引選擇問題本質上是一個NP-hard問題［3］，當索引候選項個數為N時，其解空間大小為2^N，解的數量呈現指數爆炸式增長，為其找到最優解變得十分困難。傳統的機器學習算法無法對如此龐大的解空間求解最優解，而強化學習算法則可以通過搜索龐大的解空間有效地解決索引選擇問題。因此本文提出了一種采用強化學習算法為數據庫數據變化下的一組工作負載推薦最佳的多屬性索引的方法MIRA。

3 實驗及分析

3.1 實驗設置

3.2 基線方法

3.3 實驗結果與分析

MIRA的訓練輪次為50輪，每一輪的訓練步數為500步，并取其最后一輪訓練的最大獎勵所對應的索引配置作為最佳索引配置。此外，在相同的實驗環境下分別運行Initial_State、Expert_Based、PF_Indexed、All_Indexed、ALL_Workload五種方法各50次，去掉其中的最大值與最小值并對其剩余結果取平均值作為最終結果。其中SmartIX、rCOREIL會使用模型訓練的最后一輪的最大獎勵所對應的索引配置作為結果。

3.3.1 性能提升比分析

本節將對比其他方法的基線配置相較于Initial_State時的性能提升百分比，并對其實驗結果進行比較分析，具體如圖4所示。從圖4的實驗結果來看，建立索引與不建立索引帶來的性能差距較大，性能提高了40.80%～115.28%。造成性能提升差異不同的原因主要有兩點：建立的索引數量不同；建立了能有效提升數據庫查詢性能的索引。Expert_Based、All_Indexed等基線配置的性能提升相較于PF_Indexed提高了19.32%以上，這是因為其他方法不僅在主鍵與外鍵上建立了索引，而且在數據庫中其他的列上也建立了索引，因此極大地提升了數據庫的查詢性能；SmartIX的性能提升比All_Indexed要高3.49%的原因是由于SmartIX通過使用強化學習算法來自主地選擇索引，而非在全部的列上都創建索引，這樣能一定程度地避免數據庫的性能回歸，從而推薦更好的索引配置。此外，MIRA性能提升遠高于SmartIX、rCOREIL等方法，說明了該方法的有效性。原因分析如下：a）MIRA同時占據了上述兩點原因，合理地為數據庫建立了一定數量且能有效提高數據庫查詢性能的索引；b）MIRA充分地考慮了不同索引之間的交互性影響，從而為工作負載推薦出更好的索引配置。

3.3.2 每小時查詢性能與索引空間分析

本節分析比較了每小時的查詢性能指標與索引空間大小，結果如圖5、6所示。從圖5的實驗結果可以發現，MIRA的效果最好，其次是ALL_Workload、rCOREIL和SmartIX等。MIRA算法分別比Expert_Based、SmartIX和rCOREIL等方法的查詢性能提高了34.45%、28.35%和8.49%。從圖6的實驗結果可以發現，雖然MIRA比其他強化學習算法消耗了更多的索引存儲空間，但是仍遠小于ALL_Workload的空間消耗。MIRA算法帶來查詢性能上的提升主要由于兩點：a）MIRA可以在數據庫數據動態變化的情況下為一組工作負載推薦多屬性索引配置，充分地考慮了數據庫的實際生產環境；b）該方法將強化學習融入到索引選擇問題中來實現索引的自推薦，能夠實時地對索引配置進行更新，從而推薦出更好的索引配置。而MIRA索引存儲空間的消耗比SmarIX和rCOREIL更多的原因主要是因為建立了更多的索引，從而導致占用了更多存儲空間。

3.3.3 TPC-H性能分析

為了進一步分析MIRA算法的優勢，本節將分別對各個方法進行TPC-H性能基準測試實驗，具體實驗結果如表3所示。

從表3可以看出，當在數據庫中執行創建索引操作會同時造成power@size和throughput@size性能評價指標的提升，從而導致QphH@size的提升。此外，對表3中的All_Indexed和SmartIX、ALL_Workload和MIRA的實驗數據進行比較可以發現，當為數據庫創建合適的索引項比為數據庫中全部列或索引候選項都建立索引有更好的性能表現。因為SmartIX和MIRA算法都采用強化學習方法來探索最佳的索引配置，有效地避免了為數據庫創建無用的索引，從而提高了查詢效率。

通過表3的實驗數據可以發現，MIRA算法相較于SmartIX算法的性能提升主要體現在throughput@100 MB與power@100 MB這兩方面上，其分別提升了51.26%與8.92%，這是由于MIRA推薦的索引配置中包含的組合屬性索引極大地提高了數據庫中工作負載的查詢效率。

4 結束語

本文提出一種針對工作負載特性和模擬數據庫數據動態變化情況下進行多屬性索引配置推薦的算法MIRA，不僅改進了文獻［11］算法模型中僅推薦單屬性索引配置的局限性，還將文獻［12］的啟發式規則融入其中從而實現推薦最佳索引配置。在TPC-H公開標準數據集上的實驗結果分析表明，MIRA方法能有效地在數據庫數據動態變化的情況下為給定的一組工作負載推薦最佳的多屬性索引配置，并且優于其比較方法。此外，MIRA算法存在消耗過大的索引存儲空間的不足之處，因此可以將在保證查詢性能的同時進一步地降低索引存儲空間作為未來的研究方向。

參考文獻：

[1]Silberschatz A， Korth H F， Sudarshan S. Database system concepts［M］.New York：McGraw-Hill，2002.

［2]Schwartz B， Zaitsev P， Tkachenko V. High performance MySQL：optimization， backups，and replication［M］.3rd ed. Sebastopol，CA：O’Reilly Media，Inc.，2012.

［3]Piatetsky-Shapiro G. The optimal selection of secondary indices is NP-complete［J］.ACM SIGMOD Record，1983，13（2）：72-75.

［4]Olofson C W. Ensuring a fast， reliable， and secure database through automation： oracle autonomous database［R］.Framingham，MA：IDC Research，Inc.，2020.

［5]Popovic J. Automatic tuning-SQL Server［EB/OL］.https：//learn.microsoft.com/en-us/sql/relational-databases/automatic-tuning/automatic-tuning？view=sql-server-ver16.

［6]李國良，周煊赫.軒轅：AI原生數據庫系統［J］.軟件學報，2020，31（3）：831-844.（Li Guoliang， Zhou Xuanhe. XuanYuan： an AI-native database systems［J］.Journal of Software，2020，31（3）：831-844.）

［7]鈕澤平，李國良.數據庫內AI模型優化［J］.軟件學報，2021，32（3）：622-635.（Niu Zeping， Li Guoliang. In-database AI model optimization［J］.Journal of Software，2021，32（3）：622-635.）

［8]裴威，李戰懷，潘巍.GPU數據庫核心技術綜述［J］.軟件學報，2021，32（3）：859-885.（Pei Wei， Li Zhanhuai， Pan Wei. Survey of key technologies in GPU database system［J］.Journal of Software，2021，32（3）：859-885.）

［9]Marcus R， Papaemmanouil O. Deep reinforcement learning for join order enumeration［C］//Proc of the 1st International Workshop on Exploiting Artificial Intelligence Techniques for Data Management.New York：ACM Press，2018：article No.3.

［10]邱濤，王斌，舒昭維，等.面向關系數據庫的智能索引調優方法［J］.軟件學報，2020，31（3）：634-647.（Qiu Tao， Wang Bin， Shu Zhaowei.Intelligent index tuning approach for relational databases［J］.Journal of Software，2020，31（3）：634-647.）

［11]Licks G P， Couto J C， De Fátima M P， et al. SMARTIX：a database indexing agent based on reinforcement learning［J］.Applied Intelligence，2020，50（8）：2575-2588.

［12]Lan Hai， Bao Zhifeng， Peng Yuwei. An index advisor using deep reinforcement learning［C］//Proc of the 29th ACM International Conference on Information amp; Knowledge Management.New York：ACM Press，2020：2105-2108.

［13]李國良，周煊赫.面向AI的數據管理技術綜述［J］.軟件學報，2021，32（1）：21-40.（Li Guoliang， Zhou Xuanhe. Survey of data management techniques for supporting artificial intelligence［J］.Journal of Software，2021，32（1）：21-40.）

［14]Li Guoliang， Zhou Xuanhe， Cao Lei. AI meets database： AI4DB and DB4AI［C］//Proc of International Conference on Management of Data.New York： ACM Press，2021：2859-2866.

［15]Brown D P， Chaware J， Koppuravuri M. Index selection in a database system：US，US7499907 B2［P］.2011.

［16]Choenni S， Blanken H， Chang T. Index selection in relational databases［C］//Proc of the 5th International Conference on Computing and Information. Piscataway，NJ：IEEE Press，1993：491-496.

［17]Yu Xiang， Li Guoliang， Chai Chengliang， et al. Reinforcement learning with tree-LSTM for join order selection［C］//Proc of the 36th IEEE International Conference on Data Engineering.Piscataway，NJ：IEEE Press，2020：1297-1308.

［18]Lan Hai， Bao Zhifeng， Peng Yuwei. A survey on advancing the DBMS query optimizer： cardinality estimation， cost model， and plan enumeration［J］.Data Science and Engineering，2021，6（1）：86-101.

［19]Kossmann J， Halfpap S， Jankrift M， et al. Magic mirror in my hand， which is the best in the land？ An experimental evaluation of index selection algorithms［J］.Proceedings of the VLDB Endowment，2020，13（12）：2382-2395.

［20]Sadri Z， Gruenwald L， Lead E. DRLindex： deep reinforcement learning index advisor for a cluster database［C］//Proc of the 24th Symposium on International Database Engineering amp; Applications.New York：ACM Press，2020：1-8.

［21]Yan Yu， Yao Shun， Wang Hongzhi， et al. Index selection for NoSQL database with deep reinforcement learning［J］.Information Sciences，2021，561（6）：20-30.

［22]Sutton R， Barto A. Reinforcement learning：an introduction［M］.Cambridge，MA：MIT Press，1998.

［23]Thanopoulou A， Carreira P， Galhardas H. Benchmarking with TPC-H on off-the-shelf hardware［C］//Proc of the 14th International Confe-rence on Enterprise Information Systems.2012：205-208.

［24]Basu D， Lin Qian， Chen Weidong， et al. Regularized cost-model oblivious database tuning with reinforcement learning［M］//Transactions on Large-Scale Data and Knowledge-Centered Systems XXVⅢ.Berlin：Springer-Verlag，2016：96-132.