Parallel Query Execution Plan Selection for Fused Relational Graph Attention Networks

doi:10.3778/j.issn.1002-8331.2308-0347

Abstract

Abstract: As one of the most important functions in database systems, the execution efficiency of queries directly determines the performance of the system. In parallel scenarios, query interaction (QI) essentially represents the interaction between operations, which is the key to accurately selecting a query execution plan. Existing models that measure QI at the operational granularity fail to describe the dynamics of interactions and only extract operational features to reflect QI, making it difficult to provide accurate QI measures for selecting execution plans in parallel scenarios. To this end, for the representation of QI, a query mix heterogeneous graph is proposed, with each operation as a node and each interaction type between two operations as an edge, to achieve a dynamic, operationally granular, and multi-interaction type representation of QI; for the feature extraction of QI, the multi-edge type weight calculation (MTWC) model is proposed to calculate the edge weight, which is used as the relationship feature to reflect the strength of interactions; for the selection of execution plans, query-mix heterogeneous graph classification (QHGC) model based on relational graph attention network (R-GAT) is proposed to select an execution plan for parallel queries. Experiments on PostgreSQL show that QHGC selects execution plans for queries with an accuracy of 90.4%, an average accuracy improvement of 48.2 percentage points over the query optimizer and 6.9 percentage points over the existing state-of-the-art model PSG.

Key words: query interaction, operation level, multi-edge type weight calculation (MTWC), execution plan, relational graph attention network (R-GAT)

摘要： 查询作为数据库系统中最重要的功能之一，它的执行效率直接决定系统的性能。并行场景下，查询交互（query interaction，QI）本质上表现为操作间的相互作用，是准确选择查询执行计划的关键。现有在操作粒度上度量QI的模型未能描述交互的动态性，只提取操作特征来反映QI，难以为并行场景下的执行计划选择提供准确的QI度量。为此，在QI的表示上，提出查询组合异构图，以操作为节点，操作间的交互关系为边，实现动态、操作粒度、多交互类型的QI表示；在QI特征提取上，提出多边类型权重计算（multi-edge type weight calculation，MTWC）模型用于计算边权重，并将其作为关系特征，体现交互的强弱程度；在执行计划的选择上，提出一种基于关系图注意力网络（relational graph attention network，R-GAT）的查询组合异构图分类模型（query-mix heterogeneous graph classification，QHGC），为并行查询选择执行计划。在PostgreSQL上的实验表明，QHGC为查询选择执行计划的准确率达90.4%，平均准确率比查询优化器提高48.2个百分点，比现有最先进的模型PSG提高6.9个百分点。

关键词: 查询交互, 操作级, 多边类型权重计算（MTWC）, 执行计划, 关系图注意力网络（R-GAT）

GUO Mengtao, NIU Baoning, YANG Rong. Parallel Query Execution Plan Selection for Fused Relational Graph Attention Networks[J]. Computer Engineering and Applications, 204, 60(17): 243-251.

郭梦涛, 牛保宁, 杨茸. 融合关系图注意力网络的并行查询执行计划选择[J]. 计算机工程与应用, 204, 60(17): 243-251.

References

[1] 张树杰. 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.
[2] AHMAD M. Query interactions in database systems[D]. Ontario, Canada: University of Waterloo, 2013: 1-6.
[3] 张锦文, 牛保宁, 李爱萍. 查询交互响应时间预测模型的采样优化[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.
[4] LAN F P, ZHANG J W, NIU B N. Predicting response time of concurrent queries with similarity models[J]. Big Data Research, 2021, 25(4): 100207.
[5] ZHANG J W, NIU B N. A clustering-based sampling method for building query response time models[J]. International Journal on Computer Systems Science & Engineering, 2017, 32(4): 319-331.
[6] 裴泽锋, 牛保宁, 张锦文, 等. 并行查询下查询执行计划的选择[J]. 计算机应用, 2020, 40(2): 420-425.
PEI Z F, NIU B N, ZHANG J W, et al. The choice of query execution plan under concurrent query[J]. Journal of Computer Applications, 2020, 40(2): 420-425.
[7] 章彬慧, 宋春花, 牛保宁, 等. 基于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.
[8] 柳浩楠, 牛保宁, 程永强. 并行查询交互度量及执行计划选择[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.
[9] 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.
[10] ZHOU X H, SUN J, 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.
[11] 陶温霞, 牛保宁, 柳浩楠. 使用图神经网络选择并行查询的执行计划[J]. 计算机工程与应用, 2023, 59(13): 259-265.
TAO W X, NIU B N, LIU H N. Execution plan selection for parallel queries using graph neural networks[J]. Computer Engineering and Applications, 2023, 59(13): 259-265.
[12] SUN J, LI G L. An end-to-end learning-based cost estimator[J]. Proceedings of the VLDB Endowment, 2019, 13(3): 307-319.
[13] ZHU Y, LIU J, GUO M, et al. BestConfig: tapping the per- formance potential of systems via automatic configuration tuning[C]//Proceedings of the 2017 Symposium on Cloud Computing, 2017: 338-350.
[14] KUNJIR M, BABU S. Black or white? how to develop an autotuner for memory-based analytics[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020: 1667-1683.
[15] KANELLIS K, DING C, KROTH B, et al. LlamaTune: sample-efficient DBMS configuration tuning[J]. Proceedings of the VLDB Endowment, 2022, 15(11): 2953-2965.
[16] WANG S, ZHONG Y, WANG C. Attention relational graph convolution networks for relation prediction in knowledge graphs[C]//Proceedings of the 2021 4th International Conference on Advanced Algorithms and Control Engineering, 2021.
[17] WANG X, BO D, SHI C, et al. A survey on heterogeneous graph embedding: methods, techniques, applications and sources[J]. IEEE Transactions on Big Data, 2022, 9(2): 415-436.
[18] DRESELER M, BOISSIER M, RABL T, et al. Quantifying TPC-H choke points and their optimizations[J]. Proceedings of the VLDB Endowment, 2020, 13(8): 1206-1220.
[19] 毕里缘, 伍赛, 陈刚, 等. 基于循环神经网络的数据库查询开销预测[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.
[20] DAI G Q, WANG X Z, ZOU X Y, et al. MRGAT: multi-relational graph attention network for knowledge graph completion[J]. Neural Networks, 2022, 154: 234-245.
[21] ZHAO Y, ZHOU H, ZHANG A, et al. Connecting embeddings based on multiplex relational graph attention networks for knowledge graph entity typing[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(5): 4608-4620.