RBOIRA: Integrating Rules and Reinforcement Learning to Improve Index Recommendation

Wenbo Yu; Jinguo  You; Xiangyu  Niu; Jianfeng  He; Yunwei  Zhang

doi:10.4108/eetsis.3822

Authors

Wenbo Yu Kunming University of Science and Technology
Jinguo You Kunming University of Science and Technology
Xiangyu Niu Kunming University of Science and Technology
Jianfeng He Kunming University of Science and Technology
Yunwei Zhang Kunming University of Science and Technology

DOI:

https://doi.org/10.4108/eetsis.3822

Keywords:

index recommendation, heuristic rules, dynamic database, reinforcement learning

Abstract

INTRODUCTION: The index is one of the most effective ways to improve the database query performance. The expert-based index recommendation approach cannot adjust the index configuration in real time. At the same time, reinforcement learning can automatically update the index and improve the recommended configuration by leveraging expert experience.

OBJECTIVES: This paper proposes the RBOIRA, which combines rules and reinforcement learning to recommend the optimal index configuration for a set of workloads in a dynamic database.

METHODS: Firstly, RBOIRA designed three heuristic rules for pruning index candidates. Secondly, it uses reinforcement learning to recommend the optimal index configuration for a set of workloads in the database. Finally, we conducted extensive experiments to evaluate RBOIRA using the TPC-H database benchmark.

RESULTS: RBOIRA recommends index configurations with superior performance compared to the baselines we define and other reinforcement learning methods used in related work and also has robustness in different database sizes.

References

Ramakrishnan R, Gehrke J. Database management systems(3. ed.)[M]. DBLP,2003.

Li Y. Deep Reinforcement Learning: An Overview[J].2017.

Lahdenmaki T, Leach M. Relational Database Index Design and the Optimizers: DB2, Oracle, SQL Server. John Wiley& Sons, 2005.

Tan J, Zhang T, Li F, et al. ibtune: Individualized buffertuning for large-scale cloud databases[J]. Proceedings of the VLDB Endowment, 2019, 12(10): 1221-1234.

Marcus R, Papaemmanouil O. Deep reinforcement learningfor join order enumeration[C]//Proceedings of the FirstInternational Workshop on Exploiting ArtificialIntelligence Techniques for Data Management. 2018: 1-4.

Paludo Licks G, Colleoni Couto J, de Fátima Miehe P, et al.SMARTIX: A database indexing agent based onreinforcement learning [J]. Applied Intelligence, 2020,50(8):2575-2588.

Lan Hai, Bao Zhifeng, Peng Yuwei. An Index AdvisorUsing Deep Reinforcement Learning. CIKM ’20: The 29thACM International Conference on Information andKnowledge Management. ACM, 2020.

Sultana K, Ahmed K, Gu B, et al. Elastic Optimization forStragglers in Edge Federated Learning[J]. Big Data Miningand Analytics, 2023, 6(4): 404-420.

Ge Y F, Bertino E, Wang H, et al. Distributed CooperativeCoevolution of Data Publishing Privacy andTransparency[J]. ACM Transactions on KnowledgeDiscovery from Data, 2023, 18(1): 1-23.

Wang Bin, Zhu Rui, Luo Shiying, et al. H-MRST: A NovelFramework for Supporting Probability Degree Range Query using Extreme Learning Machine[J]. CognitiveComputation, 2017, 9(1): 68-80.

Li Guoliang, Zhou Xuanhe, Cao Lei. AI Meets Database:AI4DB and DB4AI. Proceedings of the 2021 InternationalConference on Management of Data. 2021: 2859-2866.

Li GL, Zhou XH. XuanYuan: An AI-native DatabaseSystems[J]. Journal of Software, 2020, 31(3): 831-844.

Yan Yu, Yao Shun, Wang Hongzhi, et al. Index Selectionfor NoSQL Database with Deep Reinforcement Learning[J]. Information Sciences, 2021, 561: 20-30.

Pei W, Li Z H, Pan W. Survey of key technologies in GPUdatabase system. Ruan Jian Xue Bao[J]. Journal ofSoftware, 2021, 32(3): 859-885.

Van Aken D, Pavlo A, Gordon G J, et al. AutomaticDatabase Management System Tuning Through Large-scale Machine Learning. Acm International Conference on Management of Data. ACM, 2017:1009-1024.

Pavlo A, Butrovich M, Joshi A, et al. External vs. Internal:An Essay on Machine Learning Agents for AutonomousDatabase Management Systems[J]. IEEE bulletin, 2019,42(2).

Welborn J, Schaarschmidt M, Yoneki E. Learning IndexSelection with Structured Action Spaces[J]. arXiv preprintarXiv:1909.07440, 2019.

Basu D, Lin Q, Chen W, et al. Regularized cost-modeloblivious database tuning with reinforcement learning[J].Transactions on Large-Scale Data and Knowledge-CenteredSystems XXVIII: Special Issue on Database-and Expert-Systems Applications, 2016: 96-132.

Ge Y F, Wang H, Bertino E, et al. Evolutionary dynamicdatabase partitioning optimization for privacy and utility[J].IEEE Transactions on Dependable and Secure Computing,2023.

Lan Hai, Bao Zhifeng, Peng Yuwei. A Survey onAdvancing the DBMS Query Optimizer: Cardinalityestimation, cost model, and plan enumeration[J]. DataScience and Engineering, 2021, 6(1): 86-101.

Gani A, Siddiqa A, Shamshirband S, et al. A Survey onIndexing Techniques for Big Data: Taxonomy andPerformance Evaluation[J]. Knowledge and informationsystems, 2016, 46(2): 241-284.

Kossmann J, Halfpap S, Jankrift M, et al. Magic Mirror inMy Hand, Which is The Best in the Land? An ExperimentalEvaluation of Index Selection Algorithms[J]. Proceedingsof the VLDB Endowment, 2020, 13(12): 2382-2395.

Ding Bailu, Das S, Marcus R, et al. Ai Meets Ai: Leveraging Query Executions to Improve Index Recommendations.Proceedings of the 2019 International Conference onManagement of Data. 2019: 1241-1258.

Sadri Z, Gruenwald L, Lead E. DRLindex: DeepReinforcement Learning Index Advisor for A ClusterDatabase. Proceedings of the 24th Symposium onInternational Database Engineering and Applications. 2020: 1-8.

Sharma V, Dyreson C, Flann N. MANTIS: Multiple Typeand Attribute Index Selection using Deep ReinforcementLearning. 25th International Database Engineering andApplications Symposium. 2021: 56-64.

Thanopoulou A, Carreira P, Galhardas H. Benchmarkingwith TPC-H on off-the-shelf hardware[J]. ICEIS (1), 2012:205-208.

Graefe G. B-tree Indexes for High Update Rates[J]. ACMSIGMOD Record, 2005, 35(1): 39-44.

POWA (2019) PostgreSQL workload analyzer.https://powa.readthedocs.io/

Pedrozo W G, Nievola J C, Ribeiro D C. An adaptiveapproach for index tuning with learning classifier systemson hybrid storage environments[C]//Hybrid ArtificialIntelligent Systems: 13th International Conference, HAIS2018, Oviedo, Spain, June 20-22, 2018, Proceedings 13.Springer International Publishing, 2018: 716-729.