使用图神经网络选择并行查询的执行计划_陶温霞.pdf
《使用图神经网络选择并行查询的执行计划_陶温霞.pdf》由会员分享,可在线阅读,更多相关《使用图神经网络选择并行查询的执行计划_陶温霞.pdf(7页珍藏版)》请在咨信网上搜索。
1、2023,59(13)数据库系统(database systems,DBS)可以高效地存储和管理数据。查询在DBS的操作中占比最大,为查询寻找较优的执行计划是提高DBS效率和应用效率的关键1。执行计划2描述的是查询执行的具体过程。查询优化器基于表的访问方式、连接顺序以及连接方式3,为查询生成若干候选执行计划,这些因素导致不同候选计划使用的资源量不同,即这些计划的成本不同,优化器估算这些候选计划的成本,从中选出合适的执行计划。现有选择执行计划方法存在以下问题:(1)没有充分考虑4查询之间的相互影响。实际应用中,若干查询并行执行,构成查询组合,共享资源,一个查询受到其他查询的影响,这种影响被称为查
2、询交互5-6(query inter-action,QI)。QI导致查询按候选执行计划执行时,等待使用图神经网络选择并行查询的执行计划陶温霞,牛保宁,柳浩楠太原理工大学 信息与计算机学院,山西 晋中 030600摘要:查询作为数据库系统(database system,DBS)占比最大的操作,其效率在很大程度上影响着DBS的性能,为查询选择一个较优的执行计划、提高查询效率是提高DBS效率的关键。查询执行受到其他查询的影响产生查询交互(query interaction,QI),是查询优化器难以为并行查询选择较优执行计划的主要因素。提出一种以操作为单位表示查询执行计划的编码方式(features
3、 of plans based on operator,FPO),并用操作之间的数据共享关系以及资源竞争关系反映 QI;在此基础上,提出基于图神经网络的查询执行计划选择模型(plan selection based on graph,PSG)。PSG将操作作为节点,操作特征作为节点特征,操作间的关系作为边,生成异构图,作为模型的输入;考虑到操作间的关系有多种、作用不同,使用关系图卷积网络(relational graph convolutional network,RGCN)聚合信息,得到查询组合的图表示,提取其QI,通过全连接层(fully connected layers,FC),为查询选
4、择执行计划。在PostgreSQL上的实验表明,PSG的平均准确率比查询优化器提高了47.3个百分点。关键词:查询优化;查询交互;选择执行计划;图神经网络文献标志码:A中图分类号:TP392doi:10.3778/j.issn.1002-8331.2208-0300Execution Plan Selection for Parallel Queries Using Graph Neural NetworksTAO Wenxia,NIU Baoning,LIU HaonanCollege of Information and Computer,Taiyuan University of Tec
5、hnology,Jinzhong,Shanxi 030600,ChinaAbstract:Queries constitute the largest proportion of workload of database systems(DBS),and their efficiency affectsthe performance of DBS.The execution of a query is affected by other parallel queries,resulting in query interaction(QI),which is the main factor th
6、at 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 isreflected by data sharing and resource competition between operators.The plan selection mode
7、l based on graph(PSG)isproposed.PSG takes operators as nodes,operator features as node features,and relations between operators as edges togenerate heterogeneous graphs as inputs of the model.Considering that there are many kinds of relations between opera-tors with different functions,relational gr
8、aph convolutional network(RGCN)is used to aggregate information,obtaina graph representation of a query mix,and extract its QI.Through fully connected layers(FC),an execution plan is selectedfor a query.The average accuracy of PSG is 47.3 percentage points higher than that of query optimizers in Pos
9、tgreSQL.Key words:query optimization;query interaction;execution plan selection;graph neural network基金项目:国家自然科学基金(61572345,62072326)。作者简介:陶温霞(1997),女,硕士研究生,CCF会员,研究方向为数据库查询优化,E-mail:;牛保宁(1964),男,博士,教授,CCF会员,研究方向为数据库系统性能管理、区块链、智能大数据管理与分析、云计算;柳浩楠(1997),男,硕士研究生,CCF会员,研究方向为数据库查询优化。收稿日期:2022-08-19修回日期:20
10、22-11-02文章编号:1002-8331(2023)13-0259-07Computer Engineering and Applications计算机工程与应用259Computer Engineering and Applications计算机工程与应用2023,59(13)资源时间与使用资源时间7的改变,即候选执行计划代价的改变。查询优化器难以考量这种改变,为查询选择的执行计划很可能不是较优执行计划,甚至是严重影响DBS性能的执行计划。(2)对于QI的表示,现有方法通常以查询为单位,基于查询响应时间度量1,7-10,无法体现操作粒度的QI,不能更好地度量QI。本文提出以查询的操作为单
11、位,用亲子关系来表示查询内部操作之间的关系,用数据共享关系以及资源竞争关系来表示不同查询之间的操作相互作用的关系;在操作粒度上表示QI,并在此基础上为查询选择执行计划。本文的创新点如下:(1)提出一种可以表示查询大组合的QI的异构图(graphs of large query mixes,GLQM),节点表示查询操作,边表示操作之间的亲子关系、数据共享关系、资源竞争关系,操作特征(features of operators,FO)作为节点特征。用操作之间的数据共享边以及资源竞争边来表示QI。表示不同查询的节点为不同类型,表示不同关系的边为不同类型。(2)提出一种基于图神经网络选择查询执行计划的
12、模型(plan selection based on graphs,PSG)。用GLQM来表示查询大组合,将图作为模型的输入,采用关系图卷积网络(relational graph convolutional networks,RGCN)以及全连接层(fully connected layers,FC)来为查询组合中指定查询选择执行计划。(3)提出一种用于表示查询执行计划的编码方式(features of plans based on operators,FPO)。查询可以看作一个操作集合,由操作种类、表、列、返回行的行宽、共享缓冲区命中数,实际运行时间构成FO,操作集合中所有操作的特征可以表示
13、查询的执行计划。1相关工作本文研究的重点是通过准确表示QI,把QI作为主要因素,用于为并行查询选择执行计划。与之相关的研究包括:查询优化器为查询选择执行计划的方法、查询交互的表示方法,以及基于QI选择执行计划的方法。(1)查询优化器及其改进查询优化器为查询生成候选执行计划后,使用动态规划3(dynamic programming,DP)和遗传算法11(geneticalgorithm,GA)等方法,选择出成本最小的执行计划,作为查询的较优执行计划。动态规划算法先求解两张表的最优解,从下向上,依次求解,直至得到所有表的最优解。遗传算法将表作为基因,对其编号、组合,产生多个候选执行计划,并计算其成
14、本,淘汰成本高的候选计划,将成本低的计划交叉得到新的计划,不断进行淘汰与交叉,直到得到较优的执行计划。模拟退火算法对GA进行了改进,一定程度上减少了查询的响应时间。这些方法基于成本估算12-14,统计信息15的不准确会造成成本估算的不准确,而且因为QI的影响,查询组合中指定查询的候选执行计划的代价会发生不同程度的变化,查询优化器通过静态的系统参数16来体现QI,难以表示这种动态的变化,导致为查询选择较优执行计划的准确率大大降低。(2)QI的表示为并行查询选择执行计划需要考虑QI,现有的QI表示方法如下:BAL17用查询的平均页读取时间度量QI。QueryRating10用查询并行与查询单独运行
15、的响应时间的比值来度量QI,适用于2个查询并行的场景,即并行度(multi-programming level,MPL)为2。QIs9改进了 query rating,将适用场景扩展为MPL=n(n2)。MMQI7用查询的平均响应时间、平均执行时间、平均缓冲区命中率、平均I/O时间来度量QI。(3)基于QI为查询选择执行计划TRating9基于QIs、可以反映QI持续时间的基准值Fac,为并行查询选择较优的执行计划。TRating是一种统计型建模,受限于数学模型本身,随着查询组合的复杂化,不能很好地表示QI,模型的准确率下降。LSTM-FCN1和 MMQI-EPS7是两种基于深度学习的方法。L
16、STM-FCN将QueryRating作为交互特征,并结合执行计划特征,利用LSTM18与全连接层构成的模型,为并行查询选择执行计划。MMQI-EPS用MMQI度量QI,结合查询的执行计划特征,为查询选择执行计划。TRating、LSTM-FCN和MMQI-EPS都是查询级别的方法。2方法把QI作为主要因素选择执行计划的整体思路是:使用何种关系来表示QI,在图中如何体现这些关系,如何构建合适的网络模型以及如何构造节点特征。根据这一思路,本章首先是问题定义,然后介绍查询交互的表示,以及模型 PSG,包括图构建以及网络模型构建,接着介绍节点特征的编码方式,最后是介绍输出标签的设计。本文的相关符号定
17、义如表1所示。表1符号定义Table 1Definition of symbols符号tqitqiqjqi_aZZxZcomtqiZxQi定义查询qi单独运行的响应时间查询qi和qj并行运行时qi的响应时间查询qi按第a个计划执行查询组合q1,q2,qn,即并行运行的n个查询为Z生成的查询组合q1,q2,qn_x,其中qn以qn_x执行查询大组合,即为Z生成的所有查询组合的并集Zx运行时,qi的响应时间查询模板i2602023,59(13)2.1问题定义为并行查询选择执行计划的常见场景可以定义为如下的问题:查询组合Z=q1,q2,qn-1正在运行,新查询qn到来,qn与Z构成新的查询组合Z=Z
18、,qn,为qn从它的候选执行计划集合Pln=qn_1,qn_2,qn_m中挑出使目标函数最小的执行计划qn_k。其中目标函数即为本文对较优执行计划的定义:argminx=1,2,m(tqn_xZxtqn_xtqn_xZxtZx+j=1n-1tqjZxtqjtqjZxtZx)(1)其中,tZx为Zx的响应时间,tqn_x、tqj分别为qn_x、qj单独运行的响应时间;tqn_xZx、tqjZx分别为qn_x、qj在Zx中运行的响应时间。tqjZxtqj表示qj在Zx中运行与qj单独运行的响应时间变化程度,当tqjZxtqj1,表示qj受到消极影响,当tqjZxtqj1,表示qj受到积极影响,tq
19、jZxtqj越小,表示qj受到消极影响越小或积极影响越大;tqjZxtZx表示qj在Zx中占据的比重,tqjZxtZx越大,表示qj的变化越重要;两者相乘反映qj在qn_x加入查询组合Z后的变化。同理可得qn_x加入Z后,qn_x的变化(与qn_x单独运行相比)。对这n个查询的变化求和,和越小,表示查询组合Zx整体受到的消极影响越小或积极影响越大,即查询组合Zx整体最高效。找到使和最小的qn_k,记为qn在Z中的较优执行计划。2.2QI的表示为并行查询选择执行计划,需要考虑 QI。若干查询并行执行时,共享资源导致的查询效率的改变,即为QI。这种改变分为好的变化和坏的变化。查询间的交互源于查询操
20、作之间的交互,因此本文以操作之间的不同关系来表示QI,不同的关系包括数据共享以及资源竞争19。数据共享产生好的变化,主要包括表共享、索引共享以及中间结果共享。表共享:某个操作将表的数据加载到内存中,其他操作使用缓存的数据,从而节省了从外存读入数据的时间,产生了积极影响。索引共享:某个操作使用索引且缓存了数据,则与其使用相同索引的其他操作可以使用缓存的数据。中间结果共享:若某个操作,其中间结果被缓存,则与其有相同中间结果的操作可以使用缓存的数据。资源竞争导致坏的变化,当操作执行时,与其同时执行的操作会因其占用资源(CPU、内存等),效率降低,比如查询执行排序操作时,若其他查询已占用部分内存,导致
21、排序占用的内存变小,IO变多,执行时间变长。本文通过表示查询操作之间的上述关系来反映QI。2.3基于图神经网络选择执行计划(PSG)本文尝试从操作粒度表示 QI,用操作之间的数据共享和资源竞争表示QI。与现有方法相比,更细粒度地描述了QI,可以选择出较优的执行计划,后续实验也已证明。操作之间的关系交错复杂,用图可以恰当地表示QI。(1)PSG的图构建(GLQM)执行计划树可以形象地表示查询的执行计划,如图1所示,其中节点为操作,描述的是如何访问表以及表的连接方式等,后序遍历此树可以得到一个操作集合11O=Seq Scan,Hash,Index Scan,Hash Join,Aggregate。
22、基于此,本文尝试从执行计划树出发,构建一个节点为操作、边为操作间关系的图,用来表示查询大组合。给定MPL=n的查询组合Z=q1,q2,qn,其中查询qn有m个候选执行计划Pln=qn_1,qn_2,qn_m,则为Z生成m个查询组合Z1,Z2,Zm,其中Zx=q1,q2,qn_x,对m个查询组合求并集得到一个查询大组合Zcom=Z1Z2Zm。为了便于对比学习,将m个查询组合放于一张图,即用一张图来表示查询大组合。获取每个查询的操作集合Oi=oi_1,oi_2,oi_si,将操作作为节点,属于不同查询的节点为不同类型的节点。对于操作oi_ p和oj_q,如果oi_ p和oj_q之间存在某种关系,则
23、在oi_ p和oj_q之间添加一条边,操作之间的关系包括亲子关系P、数据共享关系S以及资源竞争关系C。因为不同的关系对操作的影响不同,所以边代表的关系不同,则边的类型不同。最后生成的图结构如图2所示,该图以MPL=3为例,表示Zcom=Z1Z2Z3,其中Z1=q1,q2,q3_1,Z2=q1,q2,q3_2,Z3=q1,q2,q3_3,红色表示q3_1,绿色表示q3_2,黑色表示q3_3,表示q3分别按照 3种执行计划执行,紫色表示q1,蓝色表示q2,不同颜色的节点为不同类型,不同颜色、不同形状的边为不同类型,关系P表图1执行计划树Fig.1Execution plan treeAggrega
24、teHash joinHashIndex scanSeq scan陶温霞,等:使用图神经网络选择并行查询的执行计划261Computer Engineering and Applications计算机工程与应用2023,59(13)示查询内部操作之间的关系,关系S以及关系C表示不同查询之间的操作间关系。删去了冗余的q1、q2,这是因为当q3_1、q3_2、q3_3分别加入q1,q2后,q1、q2之间的 QI 的变化较小,本文忽略这种变化,重要的是q3_1、q3_2、q3_3分别于q1、q2之间的QI的变化。图中关系表示不完全,仅表示了部分边。(2)PSG的网络模型构建因为使用的是多种节点和多种
25、边的异构图,所以模型使用关系图卷积网络20(RGCN)来得到新的图表示。公式(2)是操作在普通图卷积网络21(GCN)的隐藏层表示的计算方式,用与操作oi_ p有关系的操作oj_q在l层的信息进行聚合,得到操作节点oi_p在(l+1)层的表示,这里所有关系共享权重w。hl+1i_ p=(jNi_ p1ci_ pw(l)h(l)j_ p)(2)hl+1i_ p=(w(l)0h(l)i_ p+rRjNri_ p1ci_ p,rw(l)rh(l)j_q(3)公式(3)为操作在RGCN隐藏层表示的计算方式,由公式(2)和公式(3)可以看出,与GCN不同的是,RGCN中操作oi_ p和操作oj_q之间的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 使用 神经网络 选择 并行 查询 执行 计划 陶温霞
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。