Survey on Database Index Tuning Techniques

Lai Sichao; Wu Xiaoying; Peng Yuwei; Peng Zhiyong

doi:10.7544/issn1000-1239.202220931

Journal of Computer Research and Development > 2024 > 61(4): 929-954. > DOI: 10.7544/issn1000-1239.202220931 CSTR: 32373.14.issn1000-1239.202220931

Lai Sichao, Wu Xiaoying, Peng Yuwei, Peng Zhiyong. Survey on Database Index Tuning Techniques[J]. Journal of Computer Research and Development, 2024, 61(4): 929-954. DOI: 10.7544/issn1000-1239.202220931

Citation:

PDF (1238 KB)

Survey on Database Index Tuning Techniques

1.
School of Computer Science, Wuhan University, Wuhan 430072
2.
Big Data Institute, Wuhan University, Wuhan 430072

Funds: This work was supported by the National Natural Science Foundation of China (U1811263) and the CCF-Huawei Database Innovation Research Program (CCF-HuaweiDBIR003A).

More Information

Author Bio:
Lai Sichao: born in 1993. PhD candidate. Student member of CCF. His main research interests include database tuning, database indexes, and AI4DB

Wu Xiaoying: born in 1973. PhD, associate professor. Member of CCF. Her main research interests include data management, data processing and optimization, keyword search, pattern mining, web net, and data integration

Peng Yuwei: born in 1980. PhD, associate professor. Member of CCF. His main research interests include database systems and digital watermarks

Peng Zhiyong: born in 1963. PhD, professor. Fellow of CCF. His main research interests include databases, big data management and analysis, trusted data management, and complex data management
Received Date: November 10, 2022
Revised Date: June 12, 2023
Available Online: January 29, 2024

Graphical Abstract

Abstract

Abstract

Index tuning is an important problem in database performance tuning and has been studied consistently by worldwide researchers. Due to the theoretical complexity of index tuning as well as the advent of the big data era, manual tuning by DBA is no longer feasible for modern database systems, hence automated and intelligent solutions have been developed. With the development of machine learning techniques, more and more index tuning solutions have integrated with machine learning techniques for better performance and significant progress has been made recently. In this survey, we formulate the problem of index tuning under a search-based paradigm, and under this context, we analyze the main tasks and challenges of this problem. We categorize relevant studies into three main components of the search-based paradigm, namely the generation of the index configurations’ search space, the evaluation of specific index configurations, and the enumeration or the search of index configurations. Then we discuss and compare the related work in each category. We further identify and analyze new challenges for the online index tuning problem where the workload is ad hoc, dynamic, and shifting. We summarize the existing solutions under the online feedback control loop framework. Finally, we discuss the state-of-the-art index tuning tools. Hopefully, with the thorough discussion and evaluation of current research, this survey can provide insights to interested researchers and conclude with future research directions for index tuning.
- database index,
- index selection,
- index tuning,
- performance tuning,
- machine learning

FullText(HTML)

References (137)

References

[1]	Van Aken D, Pavlo A, Gordon G J, et al. Automatic database management system tuning through large-scale machine learning [C] //Proc of the 2017 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2017: 1009–1024
[2]	崔跃生,张勇,曾春,等. 数据库物理结构优化技术[J]. 软件学报,2013,24(4):761−780 Cui Yuesheng, Zhang Yong, Zeng Chun, et al. Database physical structure optimization technology[J]. Journal of Software, 2013, 24(4): 761−780 (in Chinese)
[3]	Chaudhuri S, Narasayya V R. An efficient cost-driven index selection tool for Microsoft SQL Server [C] //Proc of the 23rd Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 1997: 146–155
[4]	Lum V Y, Ling H. An optimization problem on the selection of secondary keys [C] //Proc of the 26th Annual Conf. New York: ACM, 1971: 349–356
[5]	Bayer R, McCreight E. Organization and maintenance of large ordered indices [C] //Proc of the 1970 ACM SIGFIDET Workshop on Data Description, Access and Control. New York: ACM, 1970: 107–141
[6]	Lum V Y. Multi-attribute retrieval with combined indexes[J]. Communications of the ACM, 1970, 13(11): 660−665 doi: 10.1145/362790.362794
[7]	Stonebraker M. The choice of partial inversions and combined indices[J]. International Journal of Computer & Information Sciences, 1974, 3(2): 167−188
[8]	Comer D. The difficulty of optimum index selection[J]. ACM Transactions on Database Systems, 1978, 3(4): 440−445 doi: 10.1145/320289.320296
[9]	Chaudhuri S, Datar M, Narasayya V. Index selection for databases: A hardness study and a principled heuristic solution[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 1313−1323 doi: 10.1109/TKDE.2004.75
[10]	Agrawal S, Chaudhuri S, Kollar L, et al. Database tuning advisor for Microsoft SQL Server 2005 [C] //Proc of the 30th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2004: 1110–1121
[11]	Valentin G, Zuliani M, Zilio D C, et al. DB2Advisor: An optimizer smart enough to recommend its own indexes [C] //Proc of the 16th Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2000: 101–110
[12]	Zilio D C, Rao Jun, Lightstone S, et al. DB2 design advisor: Integrated automatic physical database design [C] //Proc of the 30th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2004: 1087–1097
[13]	Dageville B, Das D, Dias K, et al. Automatic SQL tuning in Oracle 10g [C] //Proc of the 30th Int Conf on Very Large Data bases. San Francisco, CA: Morgan Kaufmann, 2004: 1098–1109
[14]	李国良,周煊赫,孙佶,等. 基于机器学习的数据库技术综述[J]. 计算机学报,2020,43(11):2019−2049 Li Guoliang, Zhou Xuanhe, Sun Ji, et. al. A survey of machine learning based database techniques[J]. Chinese Journal of Computers, 2020, 43(11): 2019−2049 (in Chinese)
[15]	Sadri Z, Gruenwald L, Lead E. DRLindex: Deep reinforcement learning index advisor for a cluster database [C/OL] //Proc of the 24th Symp on Int Database Engineering & Applications. New York: ACM, 2020[2022-09-01].https://dl.acm.org/doi/10.1145/3410566.3410603
[16]	Das S, Grbic M, Ilic I, et al. Automatically indexing millions of databases in Microsoft Azure SQL database [C] //Proc of the 2019 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2019: 666–679
[17]	Idreos S, Kersten M L, Manegold S. Database cracking [C/OL] //Proc of the 3rd Biennial Conf on Innovative Data Systems Research. 2007[2020-09-01].https://www.cidrdb.org/cidr2007/
[18]	Graefe G, Kuno H. Adaptive indexing for relational keys [C] //Proc of the 26th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2010: 69–74
[19]	Graefe G, Idreos S, Kuno H, et al. Benchmarking adaptive indexing [G]//LNPSE 6417: Proc of the 2nd Technology Conf on Performance Evaluation and Benchmarking. Berlin: Springer, 2011: 169–184
[20]	Bruno N. Automated Physical Database Design and Tuning [M]. 1st ed. Boca Raton, FL: CRC Press, 2011
[21]	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(11): 2382−2395
[22]	Faerber F, Kemper A, Larson P Å, et al. Main memory database systems[J]. Foundations and Trends in Databases, 2017, 8(1/2): 1−130
[23]	Schlosser R, Kossmann J, Boissier M. Efficient scalable multi-attribute index selection using recursive strategies [C] //Proc of the 35th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2019: 1238–1249
[24]	Weikum G, Moenkeberg A, Hasse C, et al. Self-tuning database technology and information services: From wishful thinking to viable engineering [C] //Proc of the 28th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2002: 20–31
[25]	Chaudhuri S, Narasayya V. AutoAdmin “what-if” index analysis utility [C] //Proc of the 1998 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1998: 367–378
[26]	Dias K, Ramacher M, Shaft U, et al. Automatic performance diagnosis and tuning in Oracle [C/OL] //Proc of the 2nd Biennial Conf on Innovative Data Systems Research. 2005[2022-09-01].https://www.cidrdb.org/cidr2005/
[27]	Chaudhuri S, Narasayya V, Weikum G. Database tuning using combinatorial search [M]//Encyclopedia of Database Systems. New York: Springer Press, 2018: 985–989
[28]	Bruno N, Nehme R V. Configuration-parametric query optimization for physical design tuning [C] //Proc of the 2008 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2008: 941−952
[29]	Ding Bailu, Das S, Marcus R, et al. AI meets AI: Leveraging query executions to improve index recommendations [C] //Proc of the 2019 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2019: 1241–1258
[30]	Schnaitter K, Polyzotis N, Getoor L. Index interactions in physical design tuning: Modeling, analysis, and applications[J]. Proceedings of the VLDB Endowment, 2009, 2(1): 1234−1245 doi: 10.14778/1687627.1687766
[31]	Finkelstein S, Schkolnick M, Tiberio P. Physical database design for relational databases[J]. ACM Transactions on Database Systems, 1988, 13(1): 91−128 doi: 10.1145/42201.42205
[32]	Siddiqui T, Jo S, Wu Wentao, et al. ISUM: Efficiently compressing large and complex workloads for scalable index tuning [C] //Proc of the 2022 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2022: 660–673
[33]	Sattler K-U, Schallehn E, Geist I. Autonomous query-driven index tuning [C] //Proc of the 8th Int Database Engineering and Applications Symp. Los Alamitos, CA: IEEE Computer Society, 2004: 439–448
[34]	Schnaitter K, Abiteboul S, Milo T, et al. On-line index selection for shifting workloads [C] //Proc of the 23rd Int Conf on Data Engineering Workshop. Piscataway, NJ: IEEE, 2007: 459–468
[35]	Jimenez I, Sanchez H, Tran Q T, et al. Kaizen: A semi-automatic index advisor [C] //Proc of the 2012 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2012: 685−688
[36]	Bruno N, Chaudhuri S. Automatic physical database tuning: A relaxation-based approach [C] //Proc of the 2005 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2005: 227–238
[37]	Bruno N, Chaudhuri S. To tune or not to tune? A lightweight physical design alerter [C] //Proc of the 32nd Int Conf on Very Large Data Bases. New York: ACM, 2006: 499–510
[38]	Hammer M, Chan A. Index selection in a self-adaptive data base management system [C] //Proc of the 1976 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1976: 1–8
[39]	Whang K Y. Index selection in relational databases [C] //Proc of the 2nd Int Conf on Foundations of Data Organization. New York: Plenum, 1985: 487–500
[40]	Schkolnick M. The optimal selection of secondary indices for files[J]. Information Systems, 1975, 1(4): 141−146 doi: 10.1016/0306-4379(75)90003-4
[41]	Ip M Y L, Saxton L V, Raghavan V V. On the selection of an optimal set of indexes[J]. IEEE Transactions on Software Engineering, 1983, SE-9(2): 135−143 doi: 10.1109/TSE.1983.236458
[42]	Chaudhuri S, Narasayya V. Index merging [C] //Proc of the 15th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 1999: 296–303
[43]	Nehme R, Bruno N. Automated partitioning design in parallel database systems [C] //Proc of the 2011 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 1137–1148
[44]	Bruno N, Chaudhuri S. Physical design refinement: The ‘merge-reduce’ approach[J]. ACM Transactions on Database Systems, 2007, 32(4): 28−71 doi: 10.1145/1292609.1292618
[45]	Deep S, Gruenheid A, Koutris P, et al. Comprehensive and efficient workload compression[J]. Proceedings of the VLDB Endowment, 2020, 14(3): 418−430
[46]	Chaudhuri S, Gupta A K, Narasayya V. Compressing SQL workloads [C] //Proc of the 2002 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2002: 488–499
[47]	Kołaczkowski P. Compressing very large database workloads for continuous online index selection [G]//LNISA 5181: Proc of the 19th Int Conf on Database and Expert Systems Applications. Berlin: Springer, 2008: 791–799
[48]	Ma Lin, Van Aken D, Hefny A, et al. Query-based workload forecasting for self-driving database management systems [C] //Proc of the 2018 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2018: 631–645
[49]	Perera R M, Oetomo B, Rubinstein B I P, et al. DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees [C] //Proc of the 37th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2021: 600–611
[50]	Kossmann J, Kastius A, Schlosser R. SWIRL: Selection of workload-aware indexes using reinforcement learning [C/OL] //Proc of the 25th Int Conf on Extending Database Technology. 2022[2022-12-01].https://openproceedings.org/2022/conf/edbt/
[51]	Zhou Xuanhe, Liu Luyang, Li Wenbo, et al. AutoIndex: An incremental index management system for dynamic workloads [C] //Proc of the 38th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2022: 2196–2208
[52]	Dash D, Polyzotis N, Ailamaki A. CoPhy: A scalable, portable, and interactive index advisor for large workloads[J]. Proceedings of the VLDB Endowment, 2011, 4(6): 362−372 doi: 10.14778/1978665.1978668
[53]	Jain S, Howe B, Yan Jiaqi, et al. Query2Vec: An evaluation of NLP techniques for generalized workload analytics [J]. arXiv preprint, arXiv: 1801.05613, 2018
[54]	Chaudhuri S, Ganesan P, Narasayya V R. Primitives for workload summarization and implications for SQL [C] //Proc of the 29th Int Conf on Very Large Data Bases. San Diego, CA: Morgan Kaufmann, 2003: 730–741
[55]	Kul G, Luong D, Xie T, et al. Ettu: Analyzing query intents in corporate databases [C] //Proc of the 25th Int Conf Companion on World Wide Web. Geneva: Int World Wide Web Conf Steering Committee, 2016: 463−466
[56]	Whang K Y, Wiederhold, Sagalowicz. Separability—An approach to physical database design[J]. IEEE Transactions on Computers, 1984, 33(3): 209−222
[57]	Choenni S, Blanken H M, Chang T. On the selection of secondary indices in relational databases[J]. Data & Knowledge Engineering, 1993, 11(3): 207−233
[58]	Papadomanolakis S, Dash D, Ailamaki A. Efficient use of the query optimizer for automated physical design [C] //Proc of the 33rd Int Conf on Very Large Data Bases. New York: ACM, 2007: 1093–1104
[59]	Papadomanolakis S, Ailamaki A. An integer linear programming approach to database design [C] //Proc of the 23rd Int Conf on Data Engineering Workshop. Piscataway, NJ: IEEE, 2007: 442–449
[60]	Chaudhuri S, Narasayya V. Anytime algorithm of database tuning advisor for Microsoft SQL Server [EB/OL]. [2020–11–11]. https://www.microsoft.com/en-us/research/publication/anytime-algorithm-of-database-tuning-advisor-for-microsoft-sql-server/
[61]	Konig A C, Nabar S U. Scalable exploration of physical database design [C] //Proc of the 22nd Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2006: 37–37
[62]	孟小峰,马超红,杨晨. 机器学习化数据库系统研究综述[J]. 计算机研究与发展,2019,56(9):1803−1820 doi: 10.7544/issn1000-1239.2019.20190446 Meng Xiaofeng, Ma Chaohong, Yang Chen. Survey on machine learning for database systems[J]. Journal of Computer Research and Development, 2019, 56(9): 1803−1820 (in Chinese) doi: 10.7544/issn1000-1239.2019.20190446
[63]	Leis V, Gubichev A, Mirchev A, et al. How good are query optimizers, really?[J]. Proceedings of the VLDB Endowment, 2015, 9(3): 204−215 doi: 10.14778/2850583.2850594
[64]	Wang Xiaoying, Qu Changbo, Wu Weiyuan, et al. Are we ready for learned cardinality estimation?[J]. Proceedings of the VLDB Endowment, 2021, 14(9): 1640−1654 doi: 10.14778/3461535.3461552
[65]	Kipf A, Kipf T, Radke B, et al. Learned cardinalities: Estimating correlated joins with deep learning [C/OL] //Proc of the 9th Biennial Conf on Innovative Data Systems Research. 2019[2022-09-01]. https://www.cidrdb.org/cidr2019/
[66]	Sun Ji, Li Guoliang. An end-to-end learning-based cost estimator[J]. Proceedings of the VLDB Endowment, 2019, 13(3): 307−319 doi: 10.14778/3368289.3368296
[67]	Siddiqui T, Wu Wentao, Narasayya V, et al. DISTILL: Low-overhead data-driven techniques for filtering and costing indexes for scalable index tuning[J]. Proceedings of the VLDB Endowment, 2022, 15(10): 2019−2031 doi: 10.14778/3547305.3547309
[68]	Gao Jianling, Zhao Nan, Wang Ning, et al. Automatic index selection with learned cost estimator[J]. Information Sciences, 2022, 612: 706−723 doi: 10.1016/j.ins.2022.08.051
[69]	Yuan Haitao, Li Guoliang, Feng Ling, et al. Automatic view generation with deep learning and reinforcement learning [C] //Proc of the 36th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2020: 1501–1512
[70]	Kimura H, Huo G, Rasin A, et al. CORADD: Correlation aware database designer for materialized views and indexes[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2): 1103−1113
[71]	Bruno N, Chaudhuri S. An online approach to physical design tuning [C] //Proc of the 23rd Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2007: 826–835
[72]	Bruno N, Chaudhuri S. Constrained physical design tuning[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 4−15 doi: 10.14778/1453856.1453863
[73]	Caprara A, Fischetti M, Maio D. Exact and approximate algorithms for the index selection problem in physical database design[J]. IEEE Transactions on Knowledge and Data Engineering, 1995, 7(6): 955−967 doi: 10.1109/69.476501
[74]	Frank M R, Omiecinski E, Navathe S B. Adaptive and automated index selection in RDBMS [G]//LNCS 580: Proc of the 3rd Int Conf on Extending Database Technology. Berlin: Springer, 1992: 277–292
[75]	Gurobi. Gurobi optimizer [EB/OL]. [2022-09-01].https://www.gurobi.com
[76]	IBM. IBM ILOG CPLEX optimizer [EB/OL]. [2022-09-01].https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer
[77]	Li Guoliang, Zhou Xuanhe, Li Shifu, et al. QTune: A query-aware database tuning system with deep reinforcement learning[J]. Proceedings of the VLDB Endowment, 2019, 12(12): 2118−2130 doi: 10.14778/3352063.3352129
[78]	Zhang Ji, Zhou Ke, Li Guoliang, et al. CDBTune+: An efficient deep reinforcement learning-based automatic cloud database tuning system[J]. The VLDB Journal, 2021, 30(6): 959−987 doi: 10.1007/s00778-021-00670-9
[79]	Hilprecht B, Binnig C, Roehm U. Learning a partitioning advisor with deep reinforcement learning [J]. arXiv preprint, arXiv: 1904.01279, 2019
[80]	Heitz J, Stockinger K. Join query optimization with deep reinforcement learning algorithms [J]. arXiv preprint, arXiv: 1911.11689, 2019
[81]	Krishnan S, Yang Z, Goldberg K, et al. Learning to optimize join queries with deep reinforcement learning [J]. arXiv preprint, arXiv: 1808.03196, 2019
[82]	Marcus R, Papaemmanouil O. Deep reinforcement learning for join order enumeration [C/OL] //Proc of the 1st Int Workshop on Exploiting Artificial Intelligence Techniques for Data Management. New York: ACM, 2018[2020-09-01].https://dl.acm.org/doi/10.1145/3211954.3211957
[83]	Liang Xi, Elmore A J, Krishnan S. Opportunistic view materialization with deep reinforcement learning [J]. arXiv preprint, arXiv: 1903.01363, 2019
[84]	Basu D, Lin Qian, Chen Weidong, et al. Regularized cost-model oblivious database tuning with reinforcement learning [J]. Transactions on Large-Scale Data-and Knowledge-Centered Systems XXVIII. Berlin: Springer, 2016: 96–132
[85]	Sharma A, Schuhknecht F M, Dittrich J. The case for automatic database administration using deep reinforcement learning [J]. arXiv preprint, arXiv: 1801.05643, 2018
[86]	Lan Hai, Bao Zhifeng, Peng Yuwei. An index advisor using deep reinforcement learning [C] //Proc of the 29th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2020: 2105–2108
[87]	Lai Sichao, Wu Xiaoying, Wang Senyang, et al. Learning an index advisor with deep reinforcement learning [G] // LNISA 12859: Proc of the 5th APWeb and WAIM Joint Int Conf on Web and Big Data. Berlin: Springer, 2021: 178–185
[88]	Wu Wentao, Wang Chi, Siddiqui T, et al. Budget-aware index tuning with reinforcement learning [C] //Proc of the 2022 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2022: 1528–1541
[89]	Schaarschmidt M, Kuhnle A, Ellis B, et al. LIFT: Reinforcement learning in computer systems by learning from demonstrations [J]. arXiv preprint, arXiv: 1808.07903, 2018
[90]	Sutton R S, Barto A G. Reinforcement Learning: An Introduction [M]. 2nd ed. Cambridge, MA: MIT Press, 2018
[91]	Licks G P, Couto J C, Miehe P F, et al. SmartIX: A database indexing agent based on reinforcement learning[J]. Applied Intelligence, 2020, 50(8): 2575−2588 doi: 10.1007/s10489-020-01674-8
[92]	Mnih V, Kavukcuoglu K, Silver D, et al. Playing Atari with deep reinforcement learning [J]. arXiv preprint, arXiv: 1312.5602, 2013
[93]	TPC. TPC-H benchmark [EB/OL]. [2022-09-01].https://www.tpc.org/tpch
[94]	TPC. TPC-DS benchmark [EB/OL]. [2022-09-01].https://www.tpc.org/tpcds
[95]	Schnaitter K, Polyzotis N. A benchmark for online index selection [C] //Proc of the 25th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2009: 1701–1708
[96]	Stillger M, Lohman G M, Markl V, et al. LEO-DB2’s learning optimizer [C] //Proc of the 27th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2001: 19–28
[97]	Holze M, Ritter N. Towards workload shift detection and prediction for autonomic databases [C]//Proc of the 1st ACM PhD Workshop in CIKM. New York: ACM, 2007: 109–116
[98]	Schnaitter K, Polyzotis N. Semi-automatic index tuning: Keeping DBAs in the loop[J]. Proceedings of the VLDB Endowment, 2012, 5(5): 478−489 doi: 10.14778/2140436.2140444
[99]	Bruno N, Chaudhuri S. Interactive physical design tuning [C] //Proc of the 26th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2010: 1161–1164
[100]	Chaudhuri S, Konig A C, Narasayya V. SQLCM: A continuous monitoring framework for relational database engines [C] //Proc of the 20th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2004: 473–484
[101]	Thiem A, Sattler K U. An integrated approach to performance monitoring for autonomous tuning [C] //Proc of the 25th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2009: 1671–1678
[102]	Calzarossa M, Serazzi G. Workload characterization: A survey[J]. Proceedings of the IEEE, 1993, 81(8): 1136−1150 doi: 10.1109/5.236191
[103]	Yu P S, Chen M S, Heiss H U, et al. On workload characterization of relational database environments[J]. IEEE Transactions on Software Engineering, 1992, 18(4): 347−355 doi: 10.1109/32.129222
[104]	Elnaffar S, Martin P, Schiefer B, et al. Is it DSS or OLTP: Automatically identifying DBMS workloads[J]. Journal of Intelligent Information Systems, 2008, 30(3): 249−271 doi: 10.1007/s10844-006-0036-6
[105]	Wasserman T J, Martin P, Skillicorn D B, et al. Developing a characterization of business intelligence workloads for sizing new database systems [C] //Proc of the 7th ACM Int Workshop on Data Warehousing and OLAP. New York: ACM, 2004: 7–13
[106]	Jain S, Yan Jiaqi, Cruanes T, et al. Database-agnostic workload management [C/OL] //Proc of the 9th Biennial Conf on Innovative Data Systems Research. 2019[2022-09-01]. www. cidrdb. org/cidr2019/
[107]	Paul D, Cao Jie, Li Feifei, et al. Database workload characterization with query plan encoders[J]. Proceedings of the VLDB Endowment, 2021, 15(4): 923−935 doi: 10.14778/3503585.3503600
[108]	Elnaffar S S, Martin P. An intelligent framework for predicting shifts in the workloads of autonomic database management systems [C/OL] //Proc of the 2004 IEEE Int Conf on Advances in Intelligent Systems–Theory and Applications. Los Alamitos, CA. IEEE Computer Society, 2004[2022-09-01].https://research.cs.queensu.ca/home/cords2/aista04.pdf
[109]	Holze M, Ritter N. Autonomic databases: Detection of workload shifts with n-Gram-Models [G] // LNISA 5207: Proc of the 12th East European Conf on Advances in Databases and Information Systems. Berlin: Springer, 2008: 127–142
[110]	Huang Xiangji, Peng Fuchun, An Aijun, et al. Dynamic web log session identification with statistical language models[J]. Journal of the American Society for Information Science and Technology, 2004, 55(14): 1290−1303 doi: 10.1002/asi.20084
[111]	Yao Qingsong, An Aijun, Huang Xiangqi. Finding and analyzing database user sessions [G] // LNISA 3453: Proc of the 10th Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2005: 851–862
[112]	Luhring M, Sattler K U, Schmidt K, et al. Autonomous management of soft indexes [C] //Proc of the 23rd Int Conf on Data Engineering Workshop. Piscataway, NJ: IEEE, 2007: 450–458
[113]	Sattler K U, Geist I, Schallehn E. QUIET: Continuous query-driven index tuning [C] //Proc of the 29th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2003: 1129–1132
[114]	Deerwester S, Dumais S T, Furnas G W, et al. Indexing by latent semantic analysis[J]. Journal of the American Society for Information Science, 1990, 41(6): 391−407 doi: 10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9
[115]	Agrawal S, Chu E, Narasayya V. Automatic physical design tuning: workload as a sequence [C] //Proc of the 2006 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2006: 683–694
[116]	Kimura H, Coffrin C, Rasin A, et al. Optimizing index deployment order for evolving OLAP [C] //Proc of the 15th Int Conf on Extending Database Technology. New York: ACM, 2012: 276–287
[117]	Agrawal S, Chaudhuri S, Narasayya V R. Automated selection of materialized views and indexes in SQL databases [C] //Proc of the 26th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 2000: 496–505
[118]	Microsoft. AutoAdmin project [EB/OL]. [2022-09-01].https://www.microsoft.com/research/project/autoadmin
[119]	IBM. db2advis: Tools for designing indexes [EB/OL]. [2022-09-01].https://www.ibm.com/docs/en/db2/11.5?topic=indexes-tools-designing
[120]	Percona. pt-index-usage: Percona toolkit documentation [EB/OL]. [2022-09-01].https://docs.percona.com/percona-toolkit/pt-index-usage.html
[121]	ankane. dexter: The automatic indexer for Postgres [EB/OL]. [2022-09-01].https://github.com/ankane/dexter
[122]	powa-team. PoWA: PostgreSQL workload analyzer [EB/OL]. [2022-09-01].https://github.com/powa-team/powa
[123]	Duboce Labs, Inc. Index advisor (in-app in pganalyze) [EB/OL]. [2022-09-01].https://pganalyze.com/docs/index-advisor
[124]	EnterpriseDB. EDB Postgres advanced server guide: Index advisor [EB/OL]. [2022-09-01].https://www.enterprisedb.com/docs/epas/latest/epas_guide/03_database_administration/02_index_advisor
[125]	EverSQL. Online PostgreSQL/MySQL index advisor: Automatic indexing recommendations [EB/OL]. [2022-09-01].https://www.eversql.com/index-advisor-automatic-indexing-recommendations/
[126]	Oracle. Oracle database performance tuning guide: Release 21 [EB/OL]. [2022-09-01]. https://docs.oracle.com/en/database/oracle/oracle-database/21/tdppt/index.html
[127]	Microsoft. Automatic tuning [EB/OL]. [2022-09-01]. https://learn.microsoft.com/sql/relational-databases/automatic-tuning/automatic-tuning
[128]	openGauss. Index advisor: Index recommendation [EB/OL]. [2023-01-25]. https://docs.opengauss.org/en/docs/3.1.0/docs/Developerguide/index-advisor-index-recommendation.html
[129]	OtterTune. Index recommendations [EB/OL]. [2023-01-25].https://docs.ottertune.com/documentation/database-instance-dashboard-and-recommendations/recommendations/index-recommendations
[130]	Alibaba Cloud. Database autonomy service [EB/OL]. [2023-01-25].https://www.alibabacloud.com/help/en/database-autonomy-service
[131]	Microsoft. Azure SQL — Family of SQL cloud databases [DB/OL]. [2022-09-01].https://azure.microsoft.com/en-us/products/azure-sql/
[132]	Oracle. Oracle Exadata [DB/OL]. [2022-09-01].https://www.oracle.com/engineered-systems/exadata
[133]	IBM. IBM Cloud database solutions [DB/OL]. [2022-09-01].https://www.ibm.com/cloud/databases
[134]	Kraska T, Alizadeh M, Beutel A, et al. SageDB: A learned database system [C/OL] //Proc of the 9th Biennial Conf on Innovative Data Systems Research. 2019[2022-09-01]. http://www.cidrdb.org/cidr2019
[135]	Marcus R, Negi P, Mao Hongzi, et al. Bao: Making learned query optimization practical[J]. ACM SIGMOD Record, 2022, 51(1): 6−13 doi: 10.1145/3542700.3542703
[136]	Chockchowwat S. Tuning hierarchical learned indexes on disk and beyond [C] //Proc of the 2022 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2022: 2515–2517
[137]	Abu-Libdeh H, Altınbüken D, Beutel A, et al. Learned indexes for a Google-scale disk-based database [J]. arXiv preprint, arXiv: 2012.12501, 2020

[1]	Gu Tianlong, Gao Hui, Li Long, Bao Xuguang, Li Yunhui. An Approach for Training Moral Agents via Reinforcement Learning[J]. Journal of Computer Research and Development, 2022, 59(9): 2039-2050. DOI: 10.7544/issn1000-1239.20210474
[2]	Ma Ang, Yu Yanhua, Yang Shengli, Shi Chuan, Li Jie, Cai Xiuxiu. Survey of Knowledge Graph Based on Reinforcement Learning[J]. Journal of Computer Research and Development, 2022, 59(8): 1694-1722. DOI: 10.7544/issn1000-1239.20211264
[3]	Qi Faxin, Tong Xiangrong, Yu Lei. Agent Trust Boost via Reinforcement Learning DQN[J]. Journal of Computer Research and Development, 2020, 57(6): 1227-1238. DOI: 10.7544/issn1000-1239.2020.20190403
[4]	Fan Hao, Xu Guangping, Xue Yanbing, Gao Zan, Zhang Hua. An Energy Consumption Optimization and Evaluation for Hybrid Cache Based on Reinforcement Learning[J]. Journal of Computer Research and Development, 2020, 57(6): 1125-1139. DOI: 10.7544/issn1000-1239.2020.20200010
[5]	Zhang Wentao, Wang Lu, Cheng Yaodong. Performance Optimization of Lustre File System Based on Reinforcement Learning[J]. Journal of Computer Research and Development, 2019, 56(7): 1578-1586. DOI: 10.7544/issn1000-1239.2019.20180797
[6]	Zhang Kaifeng, Yu Yang. Methodologies for Imitation Learning via Inverse Reinforcement Learning: A Review[J]. Journal of Computer Research and Development, 2019, 56(2): 254-261. DOI: 10.7544/issn1000-1239.2019.20170578
[7]	Zhao Fengfei and Qin Zheng. A Multi-Motive Reinforcement Learning Framework[J]. Journal of Computer Research and Development, 2013, 50(2): 240-247.
[8]	Lin Fen, Shi Chuan, Luo Jiewen, Shi Zhongzhi. Dual Reinforcement Learning Based on Bias Learning[J]. Journal of Computer Research and Development, 2008, 45(9): 1455-1462.
[9]	Shi Chuan, Shi Zhongzhi, Wang Maoguang. Online Hierarchical Reinforcement Learning Based on Path-matching[J]. Journal of Computer Research and Development, 2008, 45(9).
[10]	Chen Zonghai, Wen Feng, Nie Jianbin, and Wu Xiaoshu. A Reinforcement Learning Method Based on Node-Growing k-Means Clustering Algorithm[J]. Journal of Computer Research and Development, 2006, 43(4): 661-666.