Query Optimization for Massively Parallel Data Processing
ABSTRACT
MapReduce has been widely recognized as an efficient tool for large-scale data analysis. It achieves high performance by exploiting parallelism among processing nodes while providing a simple interface for upper-layer applications. Some vendors have enhanced their data warehouse systems by integrating MapReduce into the systems. However, existing MapReduce-based query processing systems, such as Hive, fall short of the query optimization and competency of conventional database systems . Given an SQL query, Hive translates the query into a set of MapReduce jobs sentence by sentence. This design assumes that the user can optimize his query before submitting it to the system. Unfortunately, manual query optimization is time consuming and difficult, even to an experienced database user or administrator.
In this paper, we propose a query optimization scheme for MapReduce-based processing systems. Specifically, we embed into Hive a query optimizer which is designed to generate an efficient query plan based on our proposed cost model. Experiments carried out on our in-house cluster con- firm the effectiveness of our query optimizer.
Keywords : MapReduce, Hive, Query Optimization, Multi-way Join
1 INTRODUCTION
MapReduce [15] has been widely recognized as an efficient tool for large-scale data analysis. It achieves high performance by exploiting parallelism among a set of nodes. Massively Parallel Processing (MPP) data warehouse systems, such as Aster [3] and Green plum [4], have recently integrated MapReduce into their systems.
Experiments in [17] show that combining MapReduce and data warehouse systems produces better performance. Besides efficiency, MapReduce simplifies the deployment of MPP systems by providing two user-friendly interfaces: map and reduce. Applications implemented through the extension of the framework are naturally parallelizable and fault-tolerant.
To build applications on MapReduce, users must transform and code them as customized map and reduce functions. One major weakness of MapReduce is its lack of high-level declarative languages. In comparison, SQL, which is supported by most DBMSs, hides implementation details (e.g., access method and plan optimization), thereby simplifying application programming. Recently, some high-level languages have been proposed for MapReduce, such as Pig [24] and Hive [28, 29]. These languages resemble SQL in many ways and are thus familiar to database users. Given a query, they automatically transform the query into a set of MapReduce jobs. Compared to the original MapReduce system, such systems are more suited for MPP data warehousing applications. Users can leverage them to process their data without having to model their application as a sequence of MapReduce operators. Although the syntax and grammar of these systems are similar to SQL, such systems interpret declarative queries procedurally and strictly follow the processing logic specified by users in generating the corresponding map and reduce operations [2, 24]. For example, consider the following Hive query for the TPC-H [5] schema:
SELECT avg(quantity), avg(totalprice), nationkey
FROM (
SELECT temp.quantity, temp.totalprice, c.nationkey
FROM (
SELECT l.quantity, o.totalprice, o.custkey
FROM lineitem l JOIN orders o
ON (l.orderkey=o.orderkey)
) temp JOIN customer c ON (temp.custkey=c.custkey)
) fifinaltable GROUP BY nationkey
As has been well recognized in conventional query processing, good plans can indeed improve query performance by orders of magnitude. In current systems, such as Pig [24] and Hive [28, 29], users submit their queries in the corresponding query language supported by the system. The query specification to a large degree fixes the specific query plans used by the underlying system to evaluate the queries. Therefore, as in conventional database systems, a query optimizer is needed to produce near-optimal query execution plans. In this paper, we propose AQUA (Automatic QUery Analyzer), a query optimization method designed for MapReduce-based MPP systems. Based on our experience of query processing in Hive, we find that the performance bottleneck of a MapReduce-based system is the cost of saving intermediate results. In MapReduce systems, to provide fine-grained fault tolerance, the results of each job are flushed back to the DFS (Distributed File System) as a backup. The consecutive job reads results of the previous job to continue with the processing. The I/O cost of DFS is significantly higher than that of the local storage system as network cost is incurred and multiple replicas are usually kept. An efficient MapReduce query plan should therefore avoid generating too many intermediate results.
To address the above requirement, AQUA adopts a two-phase query optimizer. In phase 1, the userrsquo;s query is parsed into a join graph, based on which we adaptively group the join operators. Each group may contain more than one join operator, which will be evaluated by a single MapReduce job. In this way, the total number of MapReduce jobs and the intermediate results that need to be written back to DFS are reduced. In phase 2, the intermediate results of groups are joined together to generate the final query results. We examine all plausibly good plans and select the one that minimizes processing cost. The second phase is similar to a conventional cost based query optimizer in DBMS.
To facilitate our cost estimation, we design a cost model to analyze relational operators in MapReduce jobs. Just as in traditional query optimization, the system maintains statistics about the underlying database to enable the optimizer to estimate the cost of various query plans. After a plan is selected, the expression tree is changed adaptively an
剩余内容已隐藏，支付完成后下载完整资料
面向大规模并行数据处理的查询优化
摘要
MapReduce已被广泛认为是进行大规模数据分析的有效工具。它通过利用处理节点之间的并行性来实现高性能，同时为上层应用程序提供简单的接口。一些供应商通过将MapReduce集成到系统中来增强其数据仓库系统。然而，现有的基于MapReduce的查询处理系统，如Hive，在查询优化和查询能力方面存在不足。给定一个SQL查询，配置单元逐句将该查询转换为一组MapReduce作业。此设计假设用户可以在将查询提交到系统之前对其查询进行优化。不幸的是，手动查询优化既耗时又困难，即使对于有经验的数据库用户或管理员也是如此。
本文提出了一种基于MapReduce的处理系统的查询优化方案。具体地说，我们在配置单元中嵌入了一个查询优化器，该优化器旨在根据我们提出的代价模型生成一个高效的查询计划。在我们的内部集群上进行的实验证实了我们的查询优化器的有效性。
1 简介
MapReduce[15]已被广泛认为是大规模数据分析的有效工具。它通过利用一组节点之间的并行性来实现高性能。大规模并行处理(MPP)数据仓库系统，如Aster[3]和Green Plum[4]，最近已经将MapReduce集成到他们的系统中。
在[17]中的实验表明，结合MapReduce和数据仓库系统可以产生更好的性能。除了效率之外，MapReduce还通过提供两个用户友好的界面简化了MPP系统的部署：映射和归约。通过框架扩展实现的应用程序自然是可并行化和容错的。
要在MapReduce上构建应用程序，用户必须将其转换和编码为自定义的映射和归约函数。MapReduce的一个主要缺点是缺少高级声明性语言。相比之下，大多数DBMS支持的SQL省略了实现细节(例如，访问方法和计划优化)，从而简化了应用程序编程。最近，一些高级语言被应用于MapReduce，如Pig[24]和Hive[28，29]。这些语言在许多方面与SQL相似，因此数据库用户非常熟悉。给定查询后，它们会自动将查询转换为一组MapReduce作业。与原有的MapReduce系统相比，该系统更适合于MPP数据仓库应用。用户可以利用它们来处理数据，而不必将其应用程序建模为一系列MapReduce运算符。虽然这些系统的语法和语法类似于SQL，但是这些系统对声明性查询的解释是过程化的，并且在生成相应的映射和归约操作时严格遵循用户指定的处理逻辑[2，24]。例如，考虑以下TPC-H[5]架构的配置单元查询：
SELECT avg(quantity), avg(totalprice), nationkey
FROM (
SELECT temp.quantity, temp.totalprice, c.nationkey
FROM (
SELECT l.quantity, o.totalprice, o.custkey
FROM lineitem l JOIN orders o
ON (l.orderkey=o.orderkey)
) temp JOIN customer c ON (temp.custkey=c.custkey)
) fifinaltable GROUP BY nationkey
传统查询处理中已经表明，好的计划确实可以将查询性能提高几个数量级。在诸如Pig[24]和Hive[28，29]的当前常用系统中，用户以系统支持的相应查询语言提交他们的查询。查询规范在很大程度上固定了底层系统用来评估查询的特定查询计划。因此，与传统数据库系统一样，需要查询优化器来产生接近最佳的查询执行计划。本文提出了一种基于MapReduce的MPP系统的查询优化方法AQUA(自动查询分析器)。根据我们在HIVE中查询处理的经验，我们发现基于MapReduce的系统的性能瓶颈是存储中间结果的开销。在MapReduce系统中，为了提供细粒度容错，每个作业的结果都会刷新回DFS(分布式文件系统)作为备份。连续作业读取前一作业的结果以继续处理。DFS的I/O成本明显高于本地存储系统，因为会产生网络成本，并且通常会保留多个副本。因此，高效的MapReduce查询计划应该避免生成过多的中间结果。
为了满足上述需求，AQUA采用了两阶段查询优化器。在阶段1中，用户的查询被解析为连接图，基于该连接图，我们自适应地对连接操作符进行分组。每个组可以包含多个联接操作符，这些操作符将由单个MapReduce作业进行计算。通过这种方式，减少了MapReduce作业的总数和需要写回DFS的中间结果。在阶段2中，将分组的中间结果连接在一起，以生成最终的查询结果。我们检查所有看似不错的计划，并选择处理成本最低的计划。第二阶段类似于DBMS中传统的基于成本的查询优化器。
为了方便我们的成本估算，我们设计了一个成本模型来分析MapReduce作业中的关系操作符。就像在传统的查询优化中一样，系统维护有关底层数据库的统计信息，以使优化器能够估计各种查询计划的成本。选择计划后，表达式树将自适应更改并转换为一组MapReduce作业。在当前的实现中，AQUA被设计成优化专用计算机集群上的单个查询。我们将在以后的工作中对其进行扩展，以支持并发查询优化。我们相信这是第一篇系统地探索如何将查询优化无缝嵌入MapReduce系统的论文。本文具体贡献包括：
1.设计并实现了一种针对MapReduce框架量身定做的高效、新颖的优化器。优化器识别并利用MapReduce框架的各种特征来提高查询性能。
2.设计一种降低I/O开销和MapReduce初始化开销的自适应复制连接方案。根据成本估算，将连接操作符组织到几个组中，并为每个组创建一个MapReduce作业。
3.提出了一种启发式计划生成器，以降低查询优化的成本。启发式生成器尽可能早地避免明显糟糕的方案，并采用共享扫描来提高性能。
4.在我们的内部集群上进行的大量实验表明，AQUA生成的查询计划比Hive[28]和Pig[24]更高效。
我们通过重新设计底层DFS和上层处理引擎，将AQUA作为EPIC[8][11](弹性功耗感知数据密集型云)系统的优化模块来开发，以支持各种类型的数据库应用。EPIC支持分布式索引以促进有效的查询处理[12]，以及行式和列式存储模型。EPIC中使用Aqua来支持行式引擎的查询优化，而列式引擎使用自定义设计的优化器(名为Llama[22])。我们注意到AQUA的设计独立于处理引擎。在本文中，我们使用Hadoop和Hive作为底层引擎来演示AQUA背后的思想，因为这些系统在研究界广受认可。在EPIC中，AQUA是在E3引擎之上实现的[10]。有关EPIC项目的更多信息，请参阅项目网站2。
2 相关工作
基于集群的解决方案在当前的数据仓库系统中被广泛接受，因为集中式服务器在面对数据爆炸时不能提供可扩展的性能。在基于集群的系统中，通过利用并行性来提高性能。MapReduce[15]是一个简化并行应用程序开发的新框架。在本文中，我们采用开源的MapReduce实现相关功能，使用Hadoop[1]作为我们的处理引擎。
Aster[3]和Greenplum[4]是两个集成了MapReduce框架的商业系统。在这些系统中，MapReduce被用来实现传统并行数据库系统中缺乏有效支持的自定义功能。在[17]中，Greenplum展示了如何组合MapReduce运算符和其他关系运算符以实现卓越的性能。与上述方法不同， Pig-Latin[24]和Hive[28]提供了纯MapReduce解决方案，它们定义了一种类似SQL的高级语言来处理大规模分析工作负载。用高级语言表达的查询被转换为一组MapReduce作业，提交给Hadoop[1]。所有的处理逻辑都在MapReduce框架中实现，这使得系统易于部署。在[27]中进行了性能比较，结果表明蜂巢算法比Pig算法效率更高。在蜂巢算法中，基于规则的查询优化被应用于下推选择/投影和生成地图端连接，基于规则的优化器专注于优化单个MapReduce作业的处理，而在我们的方法中，基于成本的优化器被应用来一起优化多个作业。最近，在[23]中，提出了一种针对蜂窝的工作共享框架，它将来自不同查询的作业合并到共享工作中。在AQUA中，我们采用了类似的思想，即内部查询共享来提高性能。
一般而言，AQUA遵循传统查询优化方法的原则，因为在传统数据库系统[19，9]、并行数据库系统[18]和分布式数据库系统[7]中的查询优化已经被研究了多年，并且已经提出了许多最先进的解决方案。然而，基于MapReduce系统的查询优化与传统的查询优化有三个显著不同：1)MapReduce是块操作，所有内部结果都需要物理物化；2)MapReduce采用扫描作为处理策略，不支持流水线；3)数据在映射器和还原器之间进行混洗。因此，我们提出了一个为MapReduce框架量身定做的代价模型，并在此基础上构建了一个优化器来删减 不良计划。
3 查询优化
AQUA分两个阶段执行查询优化。在第一阶段，优化器将表划分为连接组。每个联接组由单个MapReduce作业处理。在第二阶段，优化器通过组合连接组来搜索最佳计划以生成最终结果。在本节中，我们将介绍查询优化器的详细信息，成本模型将在下一节中讨论。
3.1 阶段1：选择加入策略
如前所述，通过降低HDFS中的I/O成本，复制联接可能会带来更好的性能。但是，如果查询涉及多个联接，优化器需要确定何时以及如何使用复制联接。在[6]中，所有连接被分组在一起，并且使用单个MapReduce作业来处理查询。这并不总是最佳解决方案，因为复制联接会增加混洗成本。在我们的优化器中，使用了自适应连接方法。为了简化讨论，我们定义了查询的连接图。
DEFINITION 3. Joining Graph
Given a query Q, its joining graph is defined as GQ
= (V,E),
where
If table Ti is involved in Q, we have a node ni in V that
denotes the table.
If Ti !'Ti .k=Tj .k Tj is a join operation in Q, we create an
undirected edge e = (ni, nj ) and ersquo;s label is set as k.
Figure 2: Joining Graph For TPC-H Q9
根据该定义，连接图中的所有节点都包含在覆盖集中，而只选择了一部分边。实际上，剩余的边定义了覆盖集中的子图之间的连接操作。有一个特殊的覆盖集S0，其中，|(我们用|A|表示集合A中的元素数)和。S0被用作查询优化的初始状态。
4 实施细节
在我们的系统中，计划被表示为表达式树。表达式树被转发到配置单元的分析器，分析器应用表的元数据将树转换为一组MapReduce作业。这些作业(它们的java类)被序列化为XML文件，该文件可以提交给流程引擎进行处理。
共享表扫描是通过修改配置单元生成的MapReduce作业来实现的。首先，我们修改第一个MapReduce作业的作业描述，将其键-值对替换为复合键-值对。其次，为蜂巢算法实现了两个新的算子。一个用于映射器将键值对写回HDFS，另一个用于还原器从HDFS加载键值对。这些操作符被序列化并嵌入到原始作业描述中。应用共享扫描时，会修改成本模型，其中包括将键值对写回HDFS的成本。
5 结论
本文介绍了基于MapReduce的数据仓库系统的查询优化器AQUA的设计与实现。给定一个类似SQL的查询，Aqua会生成一系列MapReduce作业，从而将查询处理成本降至最低。AQUA采用两阶段优化方案。在第一阶段，连接操作符被组织到不同的组中，并为每个组生成一个MapReduce作业。在第二阶段，采用基于成本的方案来搜索结合不同加入组结果的最优方案。为了减少这些冗余空间，AQUA应用了MapReduce框架的功能来删减搜索空间。特别是我们既考虑了左深计划，也考虑了浓密计划。此外，我们避免生成未充分利用计算资源的方案。我们通过在内部群集上运行TPC-H查询来评估我们的方法。结果验证了我们提出的查询优化器的有效性。
可编程逻辑控制器(PLC)的应用综述
摘要
随着自动化需求的显著增加，控制系统需要易于编程、灵活、可靠、稳定和高性价比。本文综述了可编程控制器(PLC)在当前市场上的应用情况。本文综述了PLC在能源研究、工程研究、工业控制应用和工厂监测等方面的应用情况。PLC确实有其自身的局
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236758]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
