文档章节

MapReduce中迭代查询的最优化

huser_YJ
 huser_YJ
发布于 2014/09/22 16:38
字数 1167
阅读 13
收藏 0

MapReduce中迭代查询的最优化

 

摘要:

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

 

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

           物化视图和增量视图评估

 

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

 

1. INTRODUCTION

            几种新的技术:

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

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

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

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

 

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

包括三部分


 

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

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

 

 

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


               RS是输入表,schemaR)表示R表的属性,Tlist)表示T表中有一个list属性,表示一个命题公式。

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

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

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

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

PageRank:

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


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


K-means:

两个表


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

定义的语句


3、查询优化:

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

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

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

 

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

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

 

         为了进行自动的增量--------增量表(delta table

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


         OptIQ概述图

          如何物化视图

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

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

PageRank

              将Graphsrcdestscore)分解成 VIsrcscore)和ITsrcdest


            子查询的提升(在上面的基础上继续优化)如利用分解的表在形成另外一个可以物化的表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(循环不变量)

物化视图最后优化的语句


     Automatic incrementalization

          1、跟新操作Update operations

           Update操作执行的频率大于Insertdelete操作

           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之后的语句:

实验

Hadoopspark上使用OptIQ

PageRank

 

反应时间和迭代次数减少

 

K-means

 

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

 

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

 

空间换时间

 

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

© 著作权归作者所有

huser_YJ
粉丝 2
博文 21
码字总数 28816
作品 0
武汉
私信 提问
Spark和MapReduce的区别

性能: Spark在内存中处理数据,而MapReduce是通过map和reduce操作在磁盘中处理数据。所以从这方面讲Spark的性能是超过MapReduce的。但是当数据量比较大,无法全部读入内存时,MapReduce就比...

无精疯
2018/04/26
0
0
MapReduce: 一个巨大的倒退

前言 databasecolumn 的数据库大牛们(其中包括PostgreSQL的最初伯克利领导:Michael Stonebraker)最近写了一篇评论当前如日中天的MapReduce技术的文章,引发剧烈的讨论。我抽空在这儿翻译一...

ddatsh
2011/11/04
4.4K
7
基于 MongoDB 分布式存储进行 MapReduce 并行查询

之前的文章中介绍了如何基于Mongodb进行关系型数据的分布式存储,有了存储就会牵扯到查询。虽然用普通的方式也可以进行查询,但今天要介绍的是如何使用MONGODB中提供的MapReduce功能进行查询...

小编辑
2010/11/25
1K
0
MongoDB Map Reduce

【mongoDB高级篇②】大数据聚集运算之mapReduce(映射化简) Map-Reduce是一种计算模型,简单的说就是将大批量的工作(数据)分解(MAP)执行,然后再将结果合并成最终结果(REDUCE)。 MongoD...

mickelfeng
2017/11/17
0
0
Storm与Spark、Hadoop框架对比

Storm与Spark、Hadoop三种框架对比 Storm与Spark、Hadoop这三种框架,各有各的优点,每个框架都有自己的最佳应用场景。所以,在不同的应用场景下,应该选择不同的框架。 1.Storm是最佳的流式...

boonya
04/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

idea下springboot 项目在static目录下添加文件不生效

idea下springboot 项目在static目录下添加文件不生效 问题描述 是这样子的,我的项目目录结构如下: 我在static目录下,创建了index.html和aaaa.jpg这两个文件。然后,启动服务访问 http://l...

wotrd
昨天
4
0
k8s1.14 一、环境

1. 4台虚拟机 (CentOS Linux release 7.2.1511 (Core) ) 192.168.130.211 master 192.168.130.212 node1 192.168.130.213 node2 192.168.130.214 node3 2. 设置服务器hostname 2.1 设置本机......

ThomasCheng
昨天
3
0
盖茨:如果我现在开创一家公司 将会专注于AI

新浪科技讯,北京时间 6 月 26 日凌晨消息,微软联合创始人比尔·盖茨(Bill Gates)在周一接受采访时表示,如果他今天从哈佛大学辍学并开创一家新公司,那么这家公司将会专注于人工智能(A...

linuxCool
昨天
1
0
聊聊feign的Retryer

序 本文主要研究一下feign的Retryer Retryer feign-core-10.2.3-sources.jar!/feign/Retryer.java public interface Retryer extends Cloneable { /** * if retry is permitted, retur......

go4it
昨天
9
0
HyperLogLog简介

  (1)HyperLogLog简介      在Redis 在 2.8.9 版本才添加了 HyperLogLog,HyperLogLog算法是用于基数统计的算法,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个...

SEOwhywhy
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部