Execution Plan Selection for Parallel Queries Using Graph Neural Networks

doi:10.3778/j.issn.1002-8331.2208-0300

Abstract

Abstract: Queries constitute the largest proportion of workload of database systems（DBS）, and their efficiency affects the performance of DBS. The execution of a query is affected by other parallel queries, resulting in query interaction（QI）, which is the main factor that makes it difficult for query optimizers to select a good execution plan for parallel queries. An encoding scheme called features of plans based on operator（FPO） is proposed to represent execution plans. QI is reflected by data sharing and resource competition between operators. The plan selection model based on graph（PSG） is proposed. PSG takes operators as nodes, operator features as node features, and relations between operators as edges to generate heterogeneous graphs as inputs of the model. Considering that there are many kinds of relations between operators with different functions, relational graph convolutional network（RGCN） is used to aggregate information, obtain a graph representation of a query mix, and extract its QI. Through fully connected layers（FC）, an execution plan is selected for a query. The average accuracy of PSG is 47.3?percentage points higher than that of query optimizers in PostgreSQL.

Key words: query optimization, query interaction, execution plan selection, graph neural network

摘要： 查询作为数据库系统（database system，DBS）占比最大的操作，其效率在很大程度上影响着DBS的性能，为查询选择一个较优的执行计划、提高查询效率是提高DBS效率的关键。查询执行受到其他查询的影响产生查询交互（query interaction，QI），是查询优化器难以为并行查询选择较优执行计划的主要因素。提出一种以操作为单位表示查询执行计划的编码方式（features of plans based on operator，FPO），并用操作之间的数据共享关系以及资源竞争关系反映QI；在此基础上，提出基于图神经网络的查询执行计划选择模型（plan selection based on graph，PSG）。PSG将操作作为节点，操作特征作为节点特征，操作间的关系作为边，生成异构图，作为模型的输入；考虑到操作间的关系有多种、作用不同，使用关系图卷积网络（relational graph convolutional network，RGCN）聚合信息，得到查询组合的图表示，提取其QI，通过全连接层（fully connected layers，FC），为查询选择执行计划。在PostgreSQL上的实验表明，PSG的平均准确率比查询优化器提高了47.3个百分点。

关键词: 查询优化, 查询交互, 选择执行计划, 图神经网络

TAO Wenxia, NIU Baoning, LIU Haonan. Execution Plan Selection for Parallel Queries Using Graph Neural Networks[J]. Computer Engineering and Applications, 2023, 59(13): 259-265.

陶温霞, 牛保宁, 柳浩楠. 使用图神经网络选择并行查询的执行计划[J]. 计算机工程与应用, 2023, 59(13): 259-265.

References

[1] 章彬慧，宋春花，牛保宁，等.基于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.
[2] MARCUS R，NEGI P，MAO H Z，et al.NEO：a learned query optimizer[J].Proceedings of the VLDB Endowment，2019，12（11）：1705-1718.
[3] 孙振兴，向阳，刘增宝.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.
[4] 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.
[5] 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.
[6] AHMAD M.Query interactions in database systems[D].Waterloo：University of Waterloo，2013.
[7] 柳浩楠，牛保宁，程永强.并行查询交互度量及执行计划选择[J].计算机工程与应用，2022，58（17）：72-80.
LIU H N，NIU B N，CHENG Y Q.Measurement for parallel query interaction and execution plan selection[J].Computer Engineering and Applications，2022，58（17）：72-80.
[8] 张青峰，许静，李珊珊.一种交互感知的并行查询调度策略[J].吉林大学学报，2015，45（1）：252-260.
ZHANG Q F，XU J，LI S S.Interaction-aware parallel query scheduling strategy[J].Journal of Jilin University，2015，45（1）：252-260.
[9] 裴泽锋，牛保宁，张锦文，等.并行查询下查询执行计划的选择[J].计算机应用，2020，40（2）：420-425.
PEI Z F，NIU B N，ZHANG J W，et al.Query execution plan selection under concurrent query[J].Journal of Computer Applications，2020，40（2）：420-425.
[10] 张锦文，牛保宁，李爱萍.查询交互响应时间预测模型的采样优化[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.
[11] 刘云生，迟岩.基于遗传算法的实时内存数据库查询优化[J].小型微型计算机系统，2005（3）：466-469.
LIU Y S，CHI Y.Query optimization based on GA in a RTMMDB[J].Journal of Chinese Computer Systems，2005（3）：466-469.
[12] LAN H，BAO Z F，PENG Y W.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.
[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] JI S，LI G L.An end-to-end learning-based cost estimator[J].Proceedings of the VLDB Endowment，2019，13（3）：307-319.
[15] YANG Z H，LIANG E，KAMSETTY A，et al.Deep unsupervised cardinality estimation[J].Proceedings of the VLDB Endowment，2019，13（3）：279-292.
[16] LI G L，ZHOU X H，LI S F，et al.QTune：a query-aware database tuning system with deep reinforcement learning[J].Proceedings of the VLDB Endowment，2019，12（12）：2118-2130.
[17] 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.
[18] 毕里缘，伍赛，陈刚.基于循环神经网络的数据库查询开销预测[J].软件学报，2018，29（3）：799-810.
BI L Y，WU S，CHEN G.Database query cost prediction using recurrent neural network[J].Journal of Software，2018，29（3）：799-820.
[19] 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.
[20] WANG S，ZHONG Y，WANG C P.Attention relational graph convolution networks for relation prediction in knowledge graphs[J].Journal of Physics：Conference Series，2021，1848：012073.
[21] KIPF T N，WELLING M.Semi-supervised classification with graph convolutional networks[J].arXiv：1609.02907，2016.
[22] 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.