• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 7
    • 下载费用:30 金币  

    重庆时时彩冷热走势: 一种基于超图和动态规划的大数据实时查询优化方法.pdf

    关 键 词:
    一种 基于 超图 动态 规划 数据 实时 查询 优化 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201310716665.8

    申请日:

    2013.12.16

    公开号:

    CN103793467A

    公开日:

    2014.05.14

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20131216|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 浙江鸿程计算机系统有限公司
    发明人: 陈岭; 周强; 吴勇; 阎孝文
    地址: 310053 浙江省杭州市滨江区浦沿街道伟业路1号2幢浙江鸿程计算机系统有限公司
    优先权: 2013.09.10 CN 201310421001.9
    专利代理机构: 代理人:
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201310716665.8

    授权公告号:

    ||||||

    法律状态公告日:

    2017.01.25|||2014.06.11|||2014.05.14

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明涉及大数据实时查询技术领域,尤其涉及一种基于超图和动态规划的大数据实时查询优化方法,该方法通过采用基于最佳代价的连接顺序优化方法来提升查询效率,在大数据环境下满足用户的实时查询需求。本发明的有益效果在于:针对执行计划搜索空间过大的问题,构建满足左线性树的搜索策略,大大降低了搜索的空间,提升了基于超图和动态计划算法运行的效率;构建满足大数据环境的最佳代价模型,综合考虑了大数据环境下传输代价及哈希连接算法运行特性等因素,确保了优化方法生成的计划是最佳的。

    权利要求书

    权利要求书
    1.  一种基于超图和动态计划的大数据实时查询优化方法,其特征在于包括:最佳代价模型构建过程和执行计划空间搜索过程,最佳代价模型构建过程包括以下步骤:
    1)分析元数据服务器中表数据,构建生成细粒度的列级统计信息直方图,并将其存储在元数据服务器中;
    2)利用统计信息,构建相应最佳的代价模型供生成计划时使用;执行计划空间搜索过程包括以下步骤:
    1)解析数据库查询语句,将结果保存于查询超图G=(V,E)数据结构中,查询超图G=(V,E)满足两个条件:第一,V是一个非空的顶点集,即所有参与连接的关系的集合;第二,E是一组超边集合,即代表关系间连接操作的集合,其中超边是一个无序对(u,v),u和v是属于顶点集V的非空子集,并且
    2)为单个关系初始化设置执行计划,将其保存在相应动态计划表中,其它元素值全部置为
    3)定义好计算枚举策略:每个连通子图及连通补集对只被生成一次;
    4)通过计算领域以枚举连通子图;
    5)为每个连通子图找到合适的连通补集;
    6)为每对连通子图和连通补集构成的执行计划计算其代价,依照代价模型更新其相应执行计划;
    7)重复执行步骤4)——步骤7),直到整个左线性树构成的执行计划空间搜索完毕,生成执行计划树。

    说明书

    说明书一种基于超图和动态规划的大数据实时查询优化方法
    技术领域
    本发明涉及大数据实时查询技术领域,尤其涉及一种基于超图和动态计划的大数据实时查询优化方法。 
    背景技术
    大数据实时查询是重要的大数据技术,现有的大数据查询系统有Google Dremel、Cloudera Impala、Berkeley Shark、Apache Drill等。大数据实时查询一般采用分布式计算架构,由于弱化了对事务等功能的支持,所以相对于关系型数据库集群具有更高的可扩展性。同时由于大数据实时查询能很好的满足实时查询的用户需求,因此其在互联网、智慧城市等领域有广阔的应用空间。 
    查询优化是数据库管理系统的重要组成部分,查询优化方法一般由代价模型和优化方法两部分组成。一般的代价模型需要考虑I/O、数据传输代价及具体连接算法运行特性等因素,但实际的查询优化中为了简化模型的构建通常只是考虑单个因素,现有的代价模型如对Hive查询性能进行优化工作时采用的基于连接结果和最小化的代价模型,其能够很好的应用于Hive数据仓库并一定程度的优化其查询效率。但是其只考虑连接中间结果读写产生的I/O代价这一因素,因此存在很大的系统局限性,这样便很难保证产生高效的执行计划,从而影响查询的实时响应能力。 
    现有的优化方法可以分为两类:一类是获得最优查询计划的方法;如基于记忆的优化方法及基于动态计划的优化方法?;诩且涞挠呕椒?,其工作原理是以一种自顶向下的方式生成计划,如自顶向下分区搜索方法,该方法的核心是利用最小割集以一种自顶向下的形式生成连通子图,由于在枚举过程中结合了一些搜索策略如分支限界进行剪枝,故其算法的执行效率有很大程度的提升。但是其只能处理简单的二值连接谓词及内连接,而不能处理外连接以及反连接?;诙苹挠呕椒?,由于能够有效的处理复杂的连接谓词,所以能解决自顶向下优化方法存在的问题,但是一般动态计划方法存在搜索空间会随着关系数的增加而指数增长的问题。 
    另一类是获得次优查询计划的方法,如基于遗传算法的优化方法?;谝糯惴ǖ姆椒?,其工作原理是从一组随机产生的种群开始搜索,种群中的每个个体都是问题的一个解,其根据适应值的大小选择部分后代同时淘汰部分后代,算法不断迭代直到收敛,该方法虽然较高效,但找到的解一般是次优解,同时存在过早收敛等问题。 
    发明内容
    本发明为克服上述的不足之处,目的在于提供一种基于超图和动态计划的大数据实时查询优化方法,通过采用基于最佳代价的连接顺序优化方法来提升查询效率,在大数据环境下满足用户的实时查询需求。 
    本发明是通过以下技术方案达到上述目的: 
    1、一种基于超图和动态计划的大数据实时查询优化方法,包括最佳代价模型构建过程和执行计划空间搜索过程,最佳代价模型构建两过程包括以下步骤: 
    1)分析元数据服务器中表数据,构建生成细粒度的列级统计信息直方图,并将其存储在元数据服务器中; 
    2)利用统计信息,构建相应最佳的代价模型供生成计划时使用。 
    执行计划空间搜索过程包括以下步骤: 
    1)解析数据库查询语句,将结果保存于查询超图G=(V,E)数据结构中,查询超图G=(V,E)满足两个条件:第一,V是一个非空的顶点集,即所有参与连接的关系的集合;第二,E是一组超边集合,即代表关系间连接操作的集合,其中超边是一个无序对(u,v),u和v是属于顶点集V的非空子集,并且
    2)为单个关系初始化设置执行计划,将其保存在相应动态计划表中,其它元素值全部置为
    3)定义好计算枚举策略:每个连通子图及连通补集对只被生成一次; 
    4)通过计算领域以枚举连通子图; 
    5)为每个连通子图找到合适的连通补集; 
    6)为每对连通子图和连通补集构成的执行计划计算其代价,依照代价模型更新其相应执行计划; 
    7)重复执行步骤4)——步骤7),直到整个左线性树构成的执行计划空间搜索完毕,生成执行计划树。 
    本发明的有益效果在于: 
    1)针对执行计划搜索空间过大的问题,构建满足左线性树的搜索策略,大大降低了搜索的空间,提升了基于超图和动态计划算法运行的效率; 
    2)构建满足大数据环境的最佳代价模型,综合考虑了大数据环境下传输代价及哈希连接算法运行特性等因素,确保了优化方法生成的计划是最佳的。 
    附图说明
    图1:基于超图和动态计划的大数据实时查询优化方法查询优化总体流程图; 
    图2:连通子图枚举流程图; 
    图3:执行计划生成流程图。 
    具体实施方式
    本发明提出了基于超图和动态计划的大数据实时查询优化方法,该查询优化方法的总体流程如图1所示,以查询超图为输入参数,通过元数据服务器获取相关表统计信息,并以此构建代价模型;其利用左线性树构建执行计划,而不是使用浓密树构建执行计划,动态计划算法迭代中无需扩展右子树,从而避免不必要的连接顺序空间搜索带来的巨大开销,每次都将一个单一关系作为右子树,与已生成的左子树进行连接,将其连接构成的连接顺序树作为下一次扩展连接顺序的左子树。生成计划树的过程中,选择满足构建的代价模型的最佳计划,直至整个计划树生成完毕,即找到了最佳的连接顺序,最后生成执行计划树。 
    本发明提出的方法分为最佳代价模型构建过程和执行计划空间搜索过程,最佳代价模型构建过程的主要步骤包括: 
    1)元数据服务器通过分析表相关统计信息,生成直方图; 
    本步骤主要通过统计分析表相关的聚合信息,以此构建生成细粒度的列级统计信息直方图,并将其存储在元数据服务器中。 
    2)利用相关统计信息,构建相应最佳的代价模型供生成计划时使用。 
    为了得到最佳的连接顺序,不采用只考虑由中间结果写入或读取所带来的I/O开销这一因素的传统代价模型,如式(2)所示。式中n代表参与连接的关系数,Ti-1代表左子树,Ti代表右子树。 

    而是采用本发明提出的代价模型,其综合考虑大数据环境下数据传输代价及哈希连接算法执行等特点,并根据已生成的统计信息直方图,构建适用于大数据实时查询系统的代价模型,作为基于超图和动态计划获得最佳计划的动态计划状态转移方程,其具体模型如式(3)所示。 

    其中,i∈[1,n-1],n代表参与连接的关系数,Ti代表已经计算出代价的一棵子树,Rj表示可以与Ti能够进行连接且不在Ti子树中的一个关系。表示左右子树连接后得到的中间结果,具体实现中取其最大值作为连接顺序优化算法的代价模型。 
    执行计划空间搜索过程包括以下步骤: 
    1)解析数据库查询语句,将分析后的结果保存于查询超图G=(V,E)数据结构中。其中,满足以下两个条件的图称为查询超图G=(V,E):第 一,V是一个非空的顶点集,即所有参与连接的关系的集合;第二,E是一组超边集合,即代表关系间连接操作的集合,其中超边是一个无序对(u,v),u和v是属于顶点集V的非空子集,并且对于一条超边(u,v)若满足|u|=|v|=1时,则该超边就是简单的边,当超图所有的超边都是简单的边时,则该超图也是简单图,即普通的无向图。 
    2)为单个关系初始化设置执行计划,将其保存在相应动态计划表中,其它元素值全部置为
    3)定义好计算枚举策略:每个连通子图及连通补集对只被生成一次。为了确保整个枚举过程中不会出现重复的情况,所有的关系需要按照一定的策略排好序,即每个(连通子图,连通补集)对只被生成一次,与其对称的在枚举过程中不会被再次生成。其中,连通子图G’=(V’,E’)中的同时E’构成的超边顶点均属于V’;对于一个查询超图G,假设V’和V”是V的两个子集,并且有当超边(u,v)∈E同时则V”就是V’一个连通补集。 
    4)通过计算领域以枚举连通子图,如图2所示, 
    a)对于给定的连通子集V’及排斥集X,计算V’的领域。其中,V’的领域为可以从V’可达(可达:即存在一条超边(u,v)∈E,的领域)但不在排斥集X中所有的关系集构成,排斥集中的关系被排除在领域计算之外; 
    b)对于所有在领域中的关系N,且如果V’∪N在动态计划表中的值则将V’∪N作为新扩展出的连通子图;否则继续循环判断直到遍历完; 
    c)对于所有在领域中的关系N,且则继续以V’∪N作为需要扩展的连通子集、X∪V’的领域作为排斥集继续重复a)~c)过程进一步枚举连图子图,直到遍历结束。 
    5)为每个连通子图找到合适的连通补集。 
    a)对于给定的连通子图,其顶点集为V’,找到其相应的排斥集X; 
    b)计算(V’,X)相应的领域; 
    c)对于其领域中的每个关系v,令V”={v},如果存在超边(u,v)∈E,并有那么则以(V’,V”)对生成相应的执行计划。这里令V”为单元素集合,而不继续扩展V”,这样确保生成的执行计划满足左线性树的特征,其搜索空间为n!,避免整个浓密树构成的计划空间过大的问题,浓密树构成的计划空间大小如式(1)所示,从而建立在左线性树之上的搜索策略能够极大的提升算法执行的效率,从算法层次上满足实时查询的需求。 
    2(n-1)n-1(n-1)!---(1)]]>
    6)为每对连通子图和连通补集构成的执行计划计算其代价,依照代价模型更新其相应执行计划; 
    7)重复执行步骤4)——步骤7),直到整个左线性树构成的执行计划空间搜索完毕,生成执行计划树。 
    该过程的执行流程如图3所示: 
    a)对于给定连通子集V’及相应的连通补集V”,生成包含两者的集合S=V’∪V”,并计算S中所有的连接谓词p,即在E中的超边; 
    b)从动态计划表中分别获取与V’和V”相关的执行计划plan’、plan”; 
    c)根据连接谓词p,生成S的新执行计划
    d)根据最佳代价模型,计算新的执行计划所需的代价,并与动态计划表中的代价比较,如果原来S相应的代价为或没有新执行计划好则更新,反之则不变; 
    e)重复2~4等步骤,直到整个左线性树构成的计划空间搜索完毕。 
    以上的所述乃是本发明的具体实施例及所运用的技术原理,若依本发明的构想所作的改变,其所产生的功能作用仍未超出说明书及附图所涵盖的精神时,仍应属本发明的?;し段?。 

    关于本文
    本文标题:一种基于超图和动态规划的大数据实时查询优化方法.pdf
    链接地址://www.4mum.com.cn/p-6185347.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 湖北快3破解预测软件 中国象棋玩法图解 赚钱是一门科学 百练赛输了好多 大乐透杀号16法 彩票选号技巧 高频彩快三计划软件 湖北十一选五开奖结果 二分pk拾精准计划 98捕鱼游戏官方网站 药材公司怎么赚钱 新疆时时三星跨度 彩票好卖吗 现场抽奖软件 捕鱼游戏赢现金 竞技游戏大全