Measurement for Parallel Query Interaction and Execution Plan Selection

doi:10.3778/j.issn.1002-8331.2112-0521

Abstract

Abstract: Query is the main load of the database system, and the execution efficiency of the query directly affects the performance of the system. At present, due to the mutual complex and changeable influence between queries called query interaction（QI）, the query optimizer cannot accurately evaluate the impact of queries entering the system, and it is difficult to choose a better execution plan for parallel queries. It regards mean response time, mean execution time, mean I/O time, and mean buffer hit ratio as QI parameters to measure QI. It proposes a multi-dimensional measurement of query interaction（MMQI） model and an execution plan selection（EPS） model, using a deep neural network, and on the basis of measuring QI, taking QI as the main factor of a better execution plan selection for parallel queries. Considering that the query execution plan is composed of a series of relational operations, and QI has time sequential characteristics, MMQI uses bidirectional long-short term memory（Bi-LSTM） to measure QI and extracts features of execution plan as the input of Bi-LSTM and take the change of QI parameters as the output of the model. EPS combines the predicted change of QI parameters and features of candidate plan（FCP） as the input of another Bi-LSTM to dynamically select a better execution plan for the query. Experiments on PostgreSQL show that the average accuracy of MMQI-EPS is 38.6 percentage points higher than the query optimizer in selecting a better execution plan.

Key words: query interaction, parallel query, multi-dimensional measurement of query interaction-execution plan selection（MMQI-EPS）, better execution plan, neural network

摘要： 查询是数据库系统的主要负载，查询的执行效率直接影响着系统的性能。目前，由于查询交互（query interaction，QI）复杂多变，查询优化器不能准确地评估查询进入系统产生的影响，很难为并行查询选择较优执行计划。将查询的平均响应时间、平均执行时间、平均I/O时间和平均缓冲区命中率作为QI的特征参数，表示QI；提出多维度查询交互度量（multi-dimensional measurement of query interaction，MMQI）模型和执行计划选择（execution plan selection，EPS）模型，采用深度神经网络，在度量QI的基础上，把QI作为主要因素，为并行查询选择较优执行计划。考虑到查询执行计划是由一系列关系运算组成的，以及QI具有时域特性，MMQI采用双向长短期记忆神经网络（bidirectional long-short term memory，Bi-LSTM）度量QI，从查询执行计划提取特征作为输入，将QI特征参数的改变作为输出，预测查询采用不同执行计划进入系统后QI特征参数的改变；EPS把预测到的查询特征参数的改变作为查询交互特征（feature of query interaction，FQI），与查询候选执行计划特征（features of candidate plan，FCP）融合，作为另一个Bi-LSTM的输入，为查询动态地选择较优执行计划。在PostgreSQL上的实验表明，MMQI-EPS比查询优化器选择较优执行计划的平均准确率提高38.6个百分点。

关键词: 查询交互, 并行查询, 多维度查询交互度量-执行计划选择（MMQI-EPS）, 较优执行计划, 神经网络

LIU Haonan, NIU Baoning, CHENG Yongqiang. Measurement for Parallel Query Interaction and Execution Plan Selection[J]. Computer Engineering and Applications, 2022, 58(17): 72-80.

柳浩楠, 牛保宁, 程永强. 并行查询交互度量及执行计划选择[J]. 计算机工程与应用, 2022, 58(17): 72-80.

References

[1] 李桂杰，梅红.多关系SQL查询中连接顺序的优化[J].杭州电子科技大学学报，2006，26（2）：31-34.
LI G J，MEI H.Join order optimization in multi-relation SQL query[J].Journal of Hangzhou Dianzi University，2006，26（2）：31-34.
[2] SIMON E，LLIRBAT F，FABRET F，et al.Query plan reformulation：U.S. Patent 8，688，683[P].2014-04-01.
[3] AHMAD M.Query interactions in database systems[D].University of Waterloo，2013.
[4] AHMAD M，ABOULNAGA A，BABU S，et al.Modeling and exploiting query interactions in database systems[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management，2008：183-192.
[5] 张锦文，牛保宁，李爱萍.查询交互响应时间预测模型的采样优化[J].小型微型计算机系统，2015，36（10）：2240-2244.
ZHANG J W，NIU B N，LI A P.An optimized sampling method for query interaction aware respond time modeling[J].Journal of Chinese Computer Systems，2015，36（10）：2240-2244.
[6] 裴泽锋，牛保宁，张锦文，等.并行查询下查询执行计划的选择[J].计算机应用，2020，40（2）：420-425.
PEI Z F，NIU B N，ZHANG J W.The choice of query execution plan under concurrent query[J].Journal of Computer Applications，2020，40（2）：420-425.
[7] DUGGAN J，CETINTEMEL U，PAPAEMMANOUIL O，et al.Performance prediction for concurrent database workloads[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data，2011：337-348.
[8] 张树杰.PostgreSQL技术内幕：查询优化深度探索[M].北京：电子工业出版社，2018：3-32.
ZHANG S J.PostgreSQL technical insider：in-depth exploration of query optimization[M].Beijing：Publishing House of Electronic Industry，2018：3-32.
[9] 孙振兴，向阳，刘增宝.PostgreSQL查询优化器分析研究[J].计算机技术与发展，2011，21（8）：141-144.
SUN Z X，XIANG Y，LIU Z B.Analysis and research on optimizer of PostgreSQL[J].Computer Technology and Development，2011，21（8）：141-144.
[10] GHOSH A，PARIKH J，SENGAR V S，et al.Plan selection based on query clustering[C]//Proceedings of the 28th International Conference on Very Large Databases，2002：179-190.
[11] JI S，LI G L.An end-to-end learning-based cost estimator[J].Proceedings of the VLDB Endowment，2019，13（3）：307-319.
[12] YANG Z H，LIANG E，KAMSETTY A，et al.Deep unsupervised cardinality estimation[J].Proceedings of the VLDB Endowment，2019，13（3）：279-292.
[13] WANG W，ZHANG M，CHEN G，et al.Database meets deep learning：challenges and opportunities[J].ACM SIGMOD Record，2016，45（2）：17-22.
[14] SHETIYA S，THIRUMURUGANATHAN S，KOUDAS N，et al.Astrid：accurate selectivity estimation for string predicates using deep learning[J].Proceedings of the VLDB Endowment，2020，14（4）：471-484.
[15] MARCUS R，NEGI P，MAO H Z，et al.Neo：a learned query optimizer[J].Proceedings of the VLDB Endowment，2020，12（11）：1705-1718.
[16] MARCUS R，PAPAEMMANOUIL O.Plan-structured deep neural network models for query performance prediction[J].Proceedings of the VLDB Endowment，2019，12（11）：1733-1746.
[17] ZHOU X H，JI S，LI G L，et al.Query performance prediction for concurrent queries using graph embedding[J].Proceedings of the VLDB Endowment，2020，13（9）：1416-1428.
[18] 毕里缘，伍赛，陈刚.基于循环神经网络的数据库查询开销预测[J].软件学报，2018，29（3）：799-810.
BI L Y，WU S，CHEN G，et al.Database query cost prediction using recurrent neural network[J].Journal of Software，2018，29（3）：799-810.
[19] 章彬慧，宋春花，牛保宁，等.基于LSTM-FCN的并发查询执行计划选择[J].计算机工程与应用，2022，58（2）：86-94.
ZHANG B H，SONG C H，NIU B N，et al.Selecting execution plan for concurrent queries using LSTM-FCN[J].Computer Engineering and Applications，2022，58（2）：86-94.
[20] SUN Q，JANKOVIC M V，BALLY L，et al.Predicting blood glucose with an LSTM and Bi-LSTM based deep neural network[C]//14th Symposium on Neural Networks and Applications（NEUREL），2018：1-5.
[21] DRESELER M，BOISSIER M，RABL T，et al.Quantifying TPC-H choke points and their optimizations[J].Proceedings of the VLDB Endowment，2020，13（10）：1206-1220.