欢迎来到天天文库
浏览记录
ID:33567774
大小:7.44 MB
页数:70页
时间:2019-02-27
《基于超图划分的大数据实时查询优化研究与实现》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、密级:洳多:土哮硕士学位论文论文题目⑧提交日期2014.01.09llUlllIlllIIIIIIIIUlY2512190ADissertationSubmittedtoZhejiangUniversityfortheDegreeofMasterofEngineering一⑧TITLE:HypergraphPartitioningbasedResearchandImplementionofBigDataReal..TimeQueryQ卫鱼堕亘圣西Q坠Author:Supervisor:ProfessorGencaiChenSubject:gQ!!理坠±皇!△p卫!i堡垒!iQ墼至曼堡h旦Q
2、!QgYCollege:£Q!卫卫堕!曼£曼垡i曼塾堡垒坌卫鱼!曼垦h坠Q!QgYSubmittedDate:2014.01.09浙江大学硕士学位论文摘要Impala是为满足BigQuery实时性需求而设计开发的大数据实时查询系统,其采用分布式查询引擎,通过高度的并行化、数据本地化策略,从而降低查询延迟。Impala提供了一些查询优化技术,但不支持连接顺序优化,同时由于目前基于DPhyp(DynamicProgrammingHypergraphs,DPhyp)优化SQL查询的算法存在产生指数运行时间、传统代价模型难以直接适用于Impala大数据实时查询系统等问题,故本文提出基于超图划分的I
3、mpala查询优化方法。首先,构建满足左线性树的搜索策略,缩小整个执行计划的搜索空问;接着,综合考虑数据移动代价及哈希连接算法运行等关键因素,结合提出的代价模型,生成最佳的连接顺序;然后,在生成的连接顺序基础上构建执行计划,执行后返回最终查询结果。最后,深入考虑列式文件读取的特性,在本文提出的代价模型基础之上改进现有表基数的估算方法,进而提高代价估计的准确性。大量实验结果表明,本文提出的基于超图划分的查询优化算法与DPhyp算法生成的连接顺序一致,且前者算法运行效率比后者要快近一倍;另外,基于超图划分的查询优化算法结合提出的代价模型,其比原始的Impala查询响应时间平均要少3~5倍;最后
4、,结合本文提出的修正估算方法能够有效提高代价估计的准确性。关键词:大数据实时查询;查询优化:超图;搜索空间;代价模型浙江大学硕士学位论文AbstractImpalaisabigdatareal·-timequerysystemwhichwasdesignedtomeetreal··timedemandsoftheBigQuery,itusesthedistritutedqueryengineandlowerthequerydelaybyadoptingahi曲degreeofparallelismanddatalocalizationstrategy.Impalaprovidessomeq
5、ueryoptimizationtechniques,butnotsupportingthejoinorderoptimization,meanwhiletherearetwo·problemsthatexistingdynamicprogrammingalgorithmsexhibitedexponentialruntimesuchasDPhypbasedSQLqueryoptimizationalgorithmandtraditionalcostmodelwasdifficulttoapplytotheImpalabigdatareal—timequerysystem.Thus,thi
6、sworkproposedallImpalaqueryoptimizationmethodofhypergraphpartitioningbased.Themethodfirstlyconstructedthesearchstrategyofmeetingleftdeeptreeinordertoreducethesearchspaceofthewholeexecutionplan.ThenconsideringthekeyfactorsthatcombinedthecostofdatatransmissionwithHashjoinalgorithm,andincombinationwi
7、ththecostmodelwhichwasusedtogeneratethebestjoinorder.Afterwards,thesystembuilttheexecutionplanbasedonthegeneratedjoinorder,andreturnedthequeryresultsafterrancompletely.Finally,inordertoimprovetheaccuracyoftheesti
此文档下载收益归作者所有