MapReduce中迭代查询的最优化是怎样的

12次阅读
没有评论

本篇文章为大家展示了 MapReduce 中迭代查询的最优化是怎样的,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

MapReduce 中迭代查询的最优化

摘要:

  提出术语 OptIQ:在分布式环境中迭代查询的一种查询优化的方法。(全自动化的)

    用到的方法:view materialization and incremental view evaluation.

  物化视图和增量视图评估

  作用:减少了不同迭代过程中的重复计算

1. INTRODUCTION

            几种新的技术:

  Spark Haloop REX  查询优化都不是自动化和框架化的,需要程序员指出那些数据需要重用以及手动的指定那些数据如何存储。

  OptIQ:为辨别迭代查询中出现的重复计算提出了一个总体框架,应用了在传统数据库领域中的物化视图和增量试图评估和编译器领域中的程序分析和转换的技术。

  流程:1、把迭代查询分为变和不变的视图,并且不变的视图将会用到下次的迭代过程中去。

2、通过跳过评估那些收敛的元组来增量化变化的视图。

2、为迭代查询定义 SQL 语句

包括三部分

MapReduce 中迭代查询的最优化是怎样的

  Local table  保存当前的迭代中的数据   存在本地磁盘中  let 语句

  Global table  保存上一次迭代的数据   存在分布式文件系统。set 语句

  判断是否收敛时跟新表中(update table)的所有的元组都要进行比较。

MapReduce 中迭代查询的最优化是怎样的

  R 和 S 是输入表,schema(R)表示 R 表的属性,T(list)表示 T 表中有一个 list 属性,表示一个命题公式。

  投影操作(projection)投影输入表中特殊的属性集

        选择操作(selection)选择满足输入表中满足的元组

  连接操作(join)提取两个输入表的叉积满足 ^2 的元组

Group-by 操作重组元组和计算聚集函数

PageRank:

三个表,定义的查询语句如下

MapReduce 中迭代查询的最优化是怎样的

Src 当前节点  Dest  目的节点  Score 相当于 PR 值  count 表示节点的出度

MapReduce 中迭代查询的最优化是怎样的

K-means:

两个表

MapReduce 中迭代查询的最优化是怎样的

Point 数据点,Centro 聚集的中心点

定义的语句

MapReduce 中迭代查询的最优化是怎样的

3、查询优化:

  view materialization and incremental view evaluation.(物化视图和增量视图评估)

  物化视图重用了未修改属性子查询的结果

  增量视图评估重用了未修改元组的结果

  为了进行物化视图 ——- 表分解

  把表分解成变和不变的视图,重复使用不变的视图。

  为了进行自动的增量 ——– 增量表(delta table)

  根据收敛条件减少元组数目。

MapReduce 中迭代查询的最优化是怎样的

    OptIQ 概述图

  如何物化视图

1、把 update table  分解成变和不变的视图,重写迭代查询语句,把 update table  用变化的视图表示 (变和不变的视图有一个相同的视图,最后可以用来进行 join 操作)

2、物化查询过程中不变的视图,重写和简化迭代过程重要使用的不变视图

如 PageRank

  将 Graph(src,dest,score)分解成  VI(src,score)和 IT(src,dest)

MapReduce 中迭代查询的最优化是怎样的

  子查询的提升(在上面的基础上继续优化)如利用分解的表在形成另外一个可以物化的表 IT_count

  IT_Count = select IT.src,IT.dest,Count.count

  from IT, Count

  where IT.src = Count.src.

        VT 表和 score 表可以相互替换

  loop invariant code motion(循环不变量)

物化视图最后优化的语句

MapReduce 中迭代查询的最优化是怎样的

  Automatic incrementalization

  1、跟新操作 Update operations

  Update 操作执行的频率大于 Insert 和 delete 操作

  2、检测增量表 Detecting delta tables

  3、得到增量查询 Deriving incremental queries

  刚开始比较常规的语句

  T 是 update table,q(T) 相当于查询语句,φ(ΔT ) 是收敛条件

  set T = q(T ⊕ ΔT )

  假设:q(T ⊕ ΔT) = q(T) ⊗ q(ΔT ).

  Dscore 是 score 表的一个增量表

  研究聚集函数中的增量计算,能够很大程度的提高性能

  Sum 函数

  Count 函数和 sum 函数有相同的分布规律,average 函数可以分解为 count 函数和 sum 函数

  Max 和 min 函数

加了 incrementalization 之后的语句:

实验

Hadoop 和 spark 上使用 OptIQ

PageRank

反应时间和迭代次数减少

K-means

View 并没有增加效率,优化过程中磁盘读写增加了。

物化视图:  物化视图(Meterialized View)提供了强大的功能,可以用于预先计算,并且保存表连接或者表聚集等耗时比较多的操作的结果,这样子,在执行查询的时候,就可以避免这些耗时的操作,从而快速的得到结果。

空间换时间

如何能够保证 IO 开销,即消耗空间换取的时间能不能抵消掉读磁盘产生的 IO 开销。

上述内容就是 MapReduce 中迭代查询的最优化是怎样的,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注丸趣 TV 行业资讯频道。