SQL轉化為MapReduce的過程

轉載：http://www.cnblogs.com/yaojingang/p/5446310.html

在了解了MapReduce實現SQL基本操作之后，我們來看看Hive是如何將SQL轉化為MapReduce任務的，整個編譯過程分為六個階段：

  1. Antlr定義SQL的語法規則，完成SQL詞法，語法解析，將SQL轉化為抽象語法樹AST Tree
  2. 遍歷AST Tree，抽象出查詢的基本組成單元QueryBlock
  3. 遍歷QueryBlock，翻譯為執行操作樹OperatorTree
  4. 邏輯層優化器進行OperatorTree變換，合并不必要的ReduceSinkOperator，減少shuffle數據量
  5. 遍歷OperatorTree，翻譯為MapReduce任務
  6. 物理層優化器進行MapReduce任務的變換，生成最終的執行計劃

下面分別對這六個階段進行介紹

Phase1 - SQL詞法，語法解析

Antlr

Hive使用Antlr實現SQL的詞法和語法解析。Antlr是一種語言識別的工具，可以用來構造領域語言。
這里不詳細介紹Antlr，只需要了解使用Antlr構造特定的語言只需要編寫一個語法文件，定義詞法和語法替換規則即可，Antlr完成了詞法分析、語法分析、語義分析、中間代碼生成的過程。

Hive中語法規則的定義文件在0.10版本以前是Hive.g一個文件，隨著語法規則越來越復雜，由語法規則生成的Java解析類可能超過Java類文 件的最大上限，0.11版本將Hive.g拆成了5個文件，詞法規則HiveLexer.g和語法規則的4個文件 SelectClauseParser.g，FromClauseParser.g，IdentifiersParser.g，HiveParser.g。

抽象語法樹AST Tree

經過詞法和語法解析后，如果需要對表達式做進一步的處理，使用 Antlr 的抽象語法樹語法Abstract Syntax Tree，在語法分析的同時將輸入語句轉換成抽象語法樹，后續在遍歷語法樹時完成進一步的處理。

下面的一段語法是Hive SQL中SelectStatement的語法規則，從中可以看出，SelectStatement包含select, from, where, groupby, having, orderby等子句。
（在下面的語法規則中，箭頭表示對于原語句的改寫，改寫后會加入一些特殊詞標示特定語法，比如TOK_QUERY標示一個查詢塊)

Phase2 - SQL基本組成單元QueryBlock

AST Tree仍然非常復雜，不夠結構化，不方便直接翻譯為MapReduce程序，AST Tree轉化為QueryBlock就是將SQL進一部抽象和結構化。

QueryBlock

QueryBlock是一條SQL最基本的組成單元，包括三個部分：輸入源，計算過程，輸出。簡單來講一個QueryBlock就是一個子查詢。

下圖為Hive中QueryBlock相關對象的類圖，解釋圖中幾個重要的屬性

  • QB#aliasToSubq（表示QB類的aliasToSubq屬性）保存子查詢的QB對象，aliasToSubq key值是子查詢的別名
  • QB#qbp 即QBParseInfo保存一個基本SQL單元中的給個操作部分的AST Tree結構，QBParseInfo#nameToDest這個HashMap保存查詢單元的輸出，key的形式是inclause-i（由于Hive 支持Multi Insert語句，所以可能有多個輸出），value是對應的ASTNode節點，即TOK_DESTINATION節點。類QBParseInfo其余 HashMap屬性分別保存輸出和各個操作的ASTNode節點的對應關系。
  • QBParseInfo#JoinExpr保存TOK_JOIN節點。QB#QBJoinTree是對Join語法樹的結構化。
  • QB#qbm保存每個輸入表的元信息，比如表在HDFS上的路徑，保存表數據的文件格式等。
  • QBExpr這個對象是為了表示Union操作。

AST Tree生成QueryBlock

AST Tree生成QueryBlock的過程是一個遞歸的過程，先序遍歷AST Tree，遇到不同的Token節點，保存到相應的屬性中，主要包含以下幾個過程

  • TOK_QUERY => 創建QB對象，循環遞歸子節點
  • TOK_FROM => 將表名語法部分保存到QB對象的TOK_INSERT => 循環遞歸子節點
  • TOK_DESTINATION => 將輸出目標的語法部分保存在QBParseInfo對象的nameToDest屬性中
  • TOK_SELECT => 分別將查詢表達式的語法部分保存在destToAggregationExprs、TOK_WHERE => 將Where部分的語法保存在QBParseInfo對象的destToWhereExpr屬性中

最終樣例SQL生成兩個QB對象，QB對象的關系如下，QB1是外層查詢，QB2是子查詢

QB1 \ QB2

Phase3 - 邏輯操作符Operator

Operator

Hive最終生成的MapReduce任務，Map階段和Reduce階段均由OperatorTree組成。邏輯操作符，就是在Map階段或者Reduce階段完成單一特定的操作。

基本的操作符包括TableScanOperator，SelectOperator，FilterOperator，JoinOperator，GroupByOperator，ReduceSinkOperator

從名字就能猜出各個操作符完成的功能，TableScanOperator從MapReduce框架的Map接口原始輸入表的數據，控制掃描表的數據行數，標記是從原表中取數據。JoinOperator完成Join操作。FilterOperator完成過濾操作

ReduceSinkOperator將Map端的字段組合序列化為Reduce Key/value, Partition Key，只可能出現在Map階段，同時也標志著Hive生成的MapReduce程序中Map階段的結束。

Phase4 - 邏輯層優化器

大部分邏輯層優化器通過變換OperatorTree，合并操作符，達到減少MapReduce Job，減少shuffle數據量的目的。

②?MapJoinProcessor

② GroupByOptimizer

① PredicatePushDown

ColumnPruner

名稱

作用

②?SimpleFetchOptimizer

優化沒有GroupBy表達式的聚合查詢

MapJoin，需要SQL中提供hint，0.11版本已不用

②?BucketMapJoinOptimizer

BucketMapJoin

Map端聚合

①?ReduceSinkDeDuplication

合并線性的OperatorTree中partition/sort key相同的reduce

謂詞前置

①?CorrelationOptimizer

利用查詢中的相關性，合并有相關性的Job，HIVE-2206

字段剪枝

表格中①的優化器均是一個Job干盡可能多的事情/合并。②的都是減少shuffle數據量，甚至不做Reduce。

CorrelationOptimizer優化器非常復雜，都能利用查詢中的相關性，合并有相關性的Job，參考?Hive Correlation Optimizer

對于樣例SQL，有兩個優化器對其進行優化。下面分別介紹這兩個優化器的作用，并補充一個優化器ReduceSinkDeDuplication的作用.

Phase5 - ?OperatorTree生成MapReduce Job的過程

OperatorTree轉化為MapReduce Job的過程分為下面幾個階段

  1. 對輸出表生成MoveTask
  2. 從OperatorTree的其中一個根節點向下深度優先遍歷
  3. ReduceSinkOperator標示Map/Reduce的界限，多個Job間的界限
  4. 遍歷其他根節點，遇過碰到JoinOperator合并MapReduceTask
  5. 生成StatTask更新元數據
  6. 剪斷Map與Reduce間的Operator的關系

Phase6 - 物理層優化器

這里不詳細介紹每個優化器的原理，單獨介紹一下MapJoin的優化器

SortMergeJoinResolver

CommonJoinResolver + MapJoinResolver

名稱

作用

Vectorizer

HIVE-4160，將在0.13中發布

與bucket配合，類似于歸并排序

SamplingOptimizer

并行order by優化器，在0.12中發布

MapJoin優化器

MapJoin原理

MapJoin簡單說就是在Map階段將小表讀入內存，順序掃描大表完成Join。

上圖是Hive MapJoin的原理圖，出自Facebook工程師Liyin Tang的一篇介紹Join優化的slice，從圖中可以看出MapJoin分為兩個階段：

  1. 通過MapReduce Local Task，將小表讀入內存，生成HashTableFiles上傳至Distributed Cache中，這里會對HashTableFiles進行壓縮。

  2. MapReduce Job在Map階段，每個Mapper從Distributed Cache讀取HashTableFiles到內存中，順序掃描大表，在Map階段直接進行Join，將數據傳遞給下一個MapReduce任務。

如果Join的兩張表一張表是臨時表，就會生成一個ConditionalTask，在運行期間判斷是否使用MapJoin

CommonJoinResolver優化器

CommonJoinResolver優化器就是將CommonJoin轉化為MapJoin，轉化過程如下

  1. 深度優先遍歷Task Tree
  2. 找到JoinOperator，判斷左右表數據量大小
  3. 對與小表 + 大表 => MapJoinTask，對于小/大表 + 中間表 => ConditionalTask

遍歷上一個階段生成的MapReduce任務，發現JOIN[8]中有一張表為臨時表，先對Stage-2進行深度拷貝（由于需要保留原始執行計劃為Backup
Plan，所以這里將執行計劃拷貝了一份），生成一個MapJoinOperator替代JoinOperator，然后生成一個MapReduceLocalWork讀取小表生成HashTableFiles上傳至DistributedCache中。

Operator在Map Reduce階段之間的數據傳遞都是一個流式的過程。每一個Operator對一行數據完成操作后之后將數據傳遞給childOperator計算。

Operator類的主要屬性和方法如下

    • RowSchema表示Operator的輸出字段
    • InputObjInspector outputObjInspector解析輸入和輸出字段
    • processOp接收父Operator傳遞的數據，forward將處理好的數據傳遞給子Operator處理
    • Hive每一行數據經過一個Operator處理之后，會對字段重新編號，colExprMap記錄每個表達式經過當前Operator處理前后的名稱對應關系，在下一個階段邏輯優化階段用來回溯字段名
    • 由 于Hive的MapReduce程序是一個動態的程序，即不確定一個MapReduce Job會進行什么運算，可能是Join，也可能是GroupBy，所以Operator將所有運行時需要的參數保存在OperatorDesc 中，OperatorDesc在提交任務前序列化到HDFS上，在MapReduce任務執行前從HDFS讀取并反序列化。Map階段 OperatorTree在HDFS上的位置在Job.getConf(“hive.exec.plan”)
      + “/map.xml”

    • QueryBlock生成Operator Tree

      QueryBlock生成Operator Tree就是遍歷上一個過程中生成的QB和QBParseInfo對象的保存語法的屬性，包含如下幾個步驟：

      • QB#aliasToSubq => 有子查詢，遞歸調用
      • QB#aliasToTabs => TableScanOperator
      • QBParseInfo#joinExpr => QBJoinTree => ReduceSinkOperator + JoinOperator
      • QBParseInfo#destToWhereExpr => FilterOperator
      • QBParseInfo#destToGroupby => ReduceSinkOperator + GroupByOperator
      • QBParseInfo#destToOrderby => ReduceSinkOperator + ExtractOperator

      由于Join/GroupBy/OrderBy均需要在Reduce階段完成，所以在生成相應操作的Operator之前都會先生成一個ReduceSinkOperator，將字段組合并序列化為Reduce Key/value, Partition Key

      接下來詳細分析樣例SQL生成OperatorTree的過程

      先序遍歷上一個階段生成的QB對象

轉載于:https://www.cnblogs.com/yyy-blog/p/7077748.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/392320.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/392320.shtml
英文地址，請注明出處：http://en.pswp.cn/news/392320.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

使用集合映射和關聯關系映射_使用R進行基因ID映射

使用集合映射和關聯關系映射_使用R進行基因ID映射

使用集合映射和關聯關系映射Inter-conversion of gene ID’s is the most important aspect enabling genomic and proteomic data analysis. There are multiple tools available each with its own drawbacks. While performing enrichment analysis on Mass Spectrometry da…
閱讀更多...
leetcode 1018. 可被 5 整除的二進制前綴

leetcode 1018. 可被 5 整除的二進制前綴

給定由若干 0 和 1 組成的數組 A。我們定義 N_i：從 A[0] 到 A[i] 的第 i 個子數組被解釋為一個二進制數（從最高有效位到最低有效位）。 返回布爾值列表 answer，只有當 N_i 可以被 5 整除時，答案 answer[i] 為 true&…
閱讀更多...
純java應用搭建,16、BoneCp純java項目使用

純java應用搭建,16、BoneCp純java項目使用

2、代碼實現 package com.study;import com.jolbox.bonecp.BoneCP;import com.jolbox.bonecp.BoneCPConfig;import com.jolbox.bonecp.BoneCPDataSource;import org.slf4j.Logger;import org.slf4j.LoggerFactory;import java.sql.*;/*** Boncp 純java處理* CreateTime 2018/3/…
閱讀更多...
數據結構與算法深入學習_我最喜歡的免費課程，用于深入學習數據結構和算法...

數據結構與算法深入學習_我最喜歡的免費課程，用于深入學習數據結構和算法...

數據結構與算法深入學習by javinpaul由javinpaul Data structures and algorithms are some of the most essential topics for programmers, both to get a job and to do well on a job. Good knowledge of data structures and algorithms is the foundation of writing go…
閱讀更多...
RabbitMQ學習系列（一）: 介紹

RabbitMQ學習系列（一）: 介紹

1、介紹 RabbitMQ是一個由erlang開發的基于AMQP（Advanced Message Queue ）協議的開源實現。用于在分布式系統中存儲轉發消息，在易用性、擴展性、高可用性等方面都非常的優秀。是當前最主流的消息中間件之一。 RabbitMQ的官網：http…
閱讀更多...
詳盡kmp_詳盡的分步指南，用于數據準備

詳盡kmp_詳盡的分步指南，用于數據準備

詳盡kmp表中的內容 (Table of Content) Introduction 介紹 What is Data Preparation 什么是數據準備 Exploratory Data Analysis (EDA) 探索性數據分析(EDA) Data Preprocessing 數據預處理 Data Splitting 數據分割 介紹 (Introduction) Before we get into this, I want to …
閱讀更多...
leetcode 947. 移除最多的同行或同列石頭（dfs）

leetcode 947. 移除最多的同行或同列石頭（dfs）

n 塊石頭放置在二維平面中的一些整數坐標點上。每個坐標點上最多只能有一塊石頭。 如果一塊石頭的 同行或者同列 上有其他石頭存在，那么就可以移除這塊石頭。 給你一個長度為 n 的數組 stones ，其中 stones[i] [xi, yi] 表示第 i 塊石頭的位置&#x…
閱讀更多...
matlab距離保護程序,基于MATLAB的距離保護仿真.doc

matlab距離保護程序,基于MATLAB的距離保護仿真.doc

基于MATLAB的距離保護仿真摘要：本文闡述了如何利用Matlab中的Simulink及SPS工具箱建立線路的距離保護仿真模型，并用S函數編制相間距離保護和接地距離保護算法程序，構建相應的保護模塊，實現了三段式距離保護。仿真結果表明&#xf…
閱讀更多...
ZOJ3385 - Hanami Party （貪心）

ZOJ3385 - Hanami Party （貪心）

題目鏈接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode3385 題目大意： 妖夢要準備一個party，所以需要許多食物，初始化妖夢的烹飪技能為L，每天妖夢有兩種選擇，一是選擇當天做L個食物&am…
閱讀更多...
sklearn.fit_兩個小時后仍在運行嗎？ 如何控制您的sklearn.fit。

sklearn.fit_兩個小時后仍在運行嗎？ 如何控制您的sklearn.fit。

sklearn.fitby Nathan Toubiana內森圖比亞納(Nathan Toubiana) 兩個小時后仍在運行嗎？ 如何控制您的sklearn.fit (Two hours later and still running? How to keep your sklearn.fit under control) Written by Gabriel Lerner and Nathan Toubiana加布里埃爾勒納…
閱讀更多...
RabbitMQ學習系列（二）: RabbitMQ安裝與配置

RabbitMQ學習系列（二）: RabbitMQ安裝與配置

1．安裝 Rabbit MQ 是建立在強大的Erlang OTP平臺上，因此安裝RabbitMQ之前要先安裝Erlang。 erlang：http://www.erlang.org/download.html rabbitmq：http://www.rabbitmq.com/download.html 注意： 1.現在先別裝最新的 3…
閱讀更多...
帝國CMS淺淺滴談一下——博客園老牛大講堂

帝國CMS淺淺滴談一下——博客園老牛大講堂

封筆多月之后，工作中遇到了很多很多的問題，也解決了一些問題，下面我把一些得出的經驗，分享給大家！ 會帝國cms的請離開，這篇文章對你沒什么用 1、什么是帝國CMS？---博客園老牛大講堂 多月之前&am…
閱讀更多...
matlab cdf,Matlab 簡單計算PDF和CDF | 學步園

matlab cdf,Matlab 簡單計算PDF和CDF | 學步園

通信的魅力就是在于隨機性中蘊含的確定性，這也就是為什么你隨便拿出一本通信方面的教材，前面幾章都會大篇幅的講解隨機過程，隨機過程也是研究生必須深入了解的一門課，特別是對于信號處理以及通信專業的學生。在實際工作中&#xf…
閱讀更多...
leetcode 1232. 綴點成線

leetcode 1232. 綴點成線

在一個 XY 坐標系中有一些點，我們用數組 coordinates 來分別記錄它們的坐標，其中 coordinates[i] [x, y] 表示橫坐標為 x、縱坐標為 y 的點。 請你來判斷，這些點是否在該坐標系中屬于同一條直線上，是則返回 true，否則…
閱讀更多...
mysql常用操作（一）

mysql常用操作（一）

【數據庫設計的三大范式】1、第一范式（1NF）：數據表中的每一列，必須是不可拆分的最小單元。也就是確保每一列的原子性。 例如：userInfo:山東省煙臺市 18865518189 應拆分成 userAds山東省煙臺市 userTel188655181892、第…
閱讀更多...
pmp 成本估算準確高_如何更準確地估算JavaScript中文章的閱讀時間

pmp 成本估算準確高_如何更準確地估算JavaScript中文章的閱讀時間

pmp 成本估算準確高by Pritish Vaidya通過Pritish Vaidya 準確估算JavaScript中篇文章的閱讀時間 (Accurate estimation of read time for Medium articles in JavaScript) 介紹 (Introduction) Read Time Estimate is the estimation of the time taken by the reader to rea…
閱讀更多...
Android數據適配-ExpandableListView

Android數據適配-ExpandableListView

Android中ListView的用法基本上學的時候都會使用，其中可以使用ArrayAdapter，SimpleAdapter，BaseAdapter去實現，這次主要使用的ExpandableListView展示一種兩層的效果，ExpandableListView是android中可以實現下拉list的…
閱讀更多...
JavaWeb 命名規則

JavaWeb 命名規則

命名規范命名規范命名規范命名規范 本規范主要針對java開發制定的規范項目命名項目命名項目命名項目命名 項目創建，名稱所有字母均小寫，組合方式為：com.company.projectName.component.hiberarchy。1. projectName：項目名稱2. com…
閱讀更多...
多元概率密度_利用多元論把握事件概率

多元概率密度_利用多元論把握事件概率

多元概率密度Humans have plenty of cognitive strengths, but one area that most of us struggle with is estimating, explaining and preparing for improbable events. This theme underpins two of Nassim Taleb’s major works: Fooled by Randomness and The Black Swa…
閱讀更多...
nginx php訪問日志配置,nginx php-fpm 輸出php錯誤日志的配置方法

nginx php訪問日志配置,nginx php-fpm 輸出php錯誤日志的配置方法

由于nginx僅是一個web服務器，因此nginx的access日志只有對訪問頁面的記錄，不會有php 的 error log信息。nginx把對php的請求發給php-fpm fastcgi進程來處理，默認的php-fpm只會輸出php-fpm的錯誤信息，在php-fpm的errors log里也看不…
閱讀更多...
最新文章

Copyright @ 2022~2023