基于超图划分的大数据实时查询优化研究与实现

《基于超图划分的大数据实时查询优化研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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