Hive謂詞解析過程分析

where col1 = 100 and abs(col2) > 0在Hive中的處理過程

where過濾條件稱為謂詞predicate。

以上where過濾條件在經過Hive的語法解析后，生成如下的語法樹：

TOK_WHERE                   AND                      =                     TOK_TABLE_OR_COL   c1              100                >                     TOK_FUNCTION       ABS             TOK_TABLE_OR_COLc2           0

有了語法樹之后，最終的目的是生成predicate每個節點對應的ExprNodeDesc，即描述對應的節點：

  public Map<ASTNode, ExprNodeDesc> genAllExprNodeDesc(ASTNode expr, RowResolver input,TypeCheckCtx tcCtx) throws SemanticException {...Map<ASTNode, ExprNodeDesc> nodeOutputs =TypeCheckProcFactory.genExprNode(expr, tcCtx);...

生成的過程是對上述語法樹的一個深度優先遍歷的過程，Hive中大量對樹的遍歷的代碼，在遍歷過程中根據指定的規則或對語法樹進行修改，或輸出相應的結果。

Hive中有一個默認的深度優先遍歷的實現DefaultGraphWalker。

這個遍歷器的實現部分代碼如下：

  public void walk(Node nd) throws SemanticException {    // Push the node in the stackopStack.push(nd);// While there are still nodes to dispatch...while (!opStack.empty()) {Node node = opStack.peek();if (node.getChildren() == null ||getDispatchedList().containsAll(node.getChildren())) {// Dispatch current nodeif (!getDispatchedList().contains(node)) {dispatch(node, opStack);opQueue.add(node);}opStack.pop();continue;}// Add a single child and restart the loopfor (Node childNode : node.getChildren()) {if (!getDispatchedList().contains(childNode)) {opStack.push(childNode);break;}}} // end while}

先將當前節點放到待處理的棧opStack中，然后從opStack取節點出來，如果取出來的節點沒有Children，或者Children已經全部處理完畢，才對當前節點進行處理（dispatch），如果當前節點有Children且還沒有處理完，則將當前節點的Children放到棧頂，然后重新從棧中取節點進行處理。這是很基礎的深度優先遍歷的實現。

那在遍歷的過程中，如何針對不同的節點進行不同的處理呢？

在遍歷之前，先預置一些針對不同的節點不同規則的處理器，然后在遍歷過程中，通過分發器Dispatcher選擇最合適的處理器進行處理。

生成ExprNodeDesc的遍歷中一共先預置了8個規則Rule，每個規則對應一個處理器NodeProcessor：

    Map<Rule, NodeProcessor> opRules = new LinkedHashMap<Rule, NodeProcessor>();opRules.put(new RuleRegExp("R1", HiveParser.TOK_NULL + "%"),tf.getNullExprProcessor());opRules.put(new RuleRegExp("R2", HiveParser.Number + "%|" +HiveParser.TinyintLiteral + "%|" +HiveParser.SmallintLiteral + "%|" +HiveParser.BigintLiteral + "%|" +HiveParser.DecimalLiteral + "%"),tf.getNumExprProcessor());opRules.put(new RuleRegExp("R3", HiveParser.Identifier + "%|"+ HiveParser.StringLiteral + "%|" + HiveParser.TOK_CHARSETLITERAL + "%|"+ HiveParser.TOK_STRINGLITERALSEQUENCE + "%|"+ "%|" + HiveParser.KW_IF + "%|" + HiveParser.KW_CASE + "%|"+ HiveParser.KW_WHEN + "%|" + HiveParser.KW_IN + "%|"+ HiveParser.KW_ARRAY + "%|" + HiveParser.KW_MAP + "%|"+ HiveParser.KW_STRUCT + "%|" + HiveParser.KW_EXISTS + "%|"+ HiveParser.KW_GROUPING + "%|"+ HiveParser.TOK_SUBQUERY_OP_NOTIN + "%"),tf.getStrExprProcessor());opRules.put(new RuleRegExp("R4", HiveParser.KW_TRUE + "%|"+ HiveParser.KW_FALSE + "%"), tf.getBoolExprProcessor());opRules.put(new RuleRegExp("R5", HiveParser.TOK_DATELITERAL + "%|"+ HiveParser.TOK_TIMESTAMPLITERAL + "%"), tf.getDateTimeExprProcessor());opRules.put(new RuleRegExp("R6",HiveParser.TOK_INTERVAL_YEAR_MONTH_LITERAL + "%|"+ HiveParser.TOK_INTERVAL_DAY_TIME_LITERAL + "%|"+ HiveParser.TOK_INTERVAL_YEAR_LITERAL + "%|"+ HiveParser.TOK_INTERVAL_MONTH_LITERAL + "%|"+ HiveParser.TOK_INTERVAL_DAY_LITERAL + "%|"+ HiveParser.TOK_INTERVAL_HOUR_LITERAL + "%|"+ HiveParser.TOK_INTERVAL_MINUTE_LITERAL + "%|"+ HiveParser.TOK_INTERVAL_SECOND_LITERAL + "%"), tf.getIntervalExprProcessor());opRules.put(new RuleRegExp("R7", HiveParser.TOK_TABLE_OR_COL + "%"),tf.getColumnExprProcessor());opRules.put(new RuleRegExp("R8", HiveParser.TOK_SUBQUERY_OP + "%"),tf.getSubQueryExprProcessor());

這里使用的分發器Dispatcher是DefaultRuleDispatcher，DefaultRuleDispatcher選擇處理器的邏輯如下：

    // find the firing rule// find the rule from the stack specifiedRule rule = null;int minCost = Integer.MAX_VALUE;for (Rule r : procRules.keySet()) {int cost = r.cost(ndStack);if ((cost >= 0) && (cost <= minCost)) {minCost = cost;rule = r;}}NodeProcessor proc;if (rule == null) {proc = defaultProc;} else {proc = procRules.get(rule);}// Do nothing in case proc is nullif (proc != null) {// Call the process functionreturn proc.process(nd, ndStack, procCtx, nodeOutputs);} else {return null;}

遍歷所有的規則Rule，調用每個規則的cost方法計算cost，找其中cost最小的規則對應的處理器，如果沒有找到，則使用默認處理器，如果沒有設置默認處理器，則不做任何事情。

那么每個規則的cost是如何計算的？

-- 沒太看懂==|| (后續再理理)

WHERE條件語法樹每個節點對應的處理器如下：

TOK_WHERE                   AND                        --> TypeCheckProcFactory.DefaultExprProcessor=                       --> TypeCheckProcFactory.DefaultExprProcessorTOK_TABLE_OR_COL     --> TypeCheckProcFactory.ColumnExprProcessorc1                --> TypeCheckProcFactory.StrExprProcessor100                  --> TypeCheckProcFactory.NumExprProcessor>                       --> TypeCheckProcFactory.DefaultExprProcessorTOK_FUNCTION         --> TypeCheckProcFactory.DefaultExprProcessorABS               --> TypeCheckProcFactory.StrExprProcessorTOK_TABLE_OR_COL  --> TypeCheckProcFactory.ColumnExprProcessorc2             --> TypeCheckProcFactory.StrExprProcessor0                    --> TypeCheckProcFactory.NumExprProcessorTypeCheckProcFactory.StrExprProcessor 生成ExprNodeConstantDesc
TypeCheckProcFactory.ColumnExprProcessor 處理column，生成ExprNodeColumnDesc
TypeCheckProcFactory.NumExprProcessor生成ExprNodeConstantDesc
TypeCheckProcFactory.DefaultExprProcessor生成ExprNodeGenericFuncDesc

在深度優先遍歷完WHERE語法樹后，每個節點都會生成一個ExprNodeDesc，但是其實除了最頂層的AND節點生成的ExprNodeDesc有用，其他的節點生成的都是中間結果，最終都會包含在AND節點生成的ExprNodeDesc中。所以在遍歷WHERE樹后，通過AND節點生成的ExprNodeDesc構造FilterDesc：

new FilterDesc(genExprNodeDesc(condn, inputRR, useCaching), false)

有了FilterDesc后，就能夠構造出FilterOperator了，然后再將生成的FilterOperator加入到Operator樹中：

Operator<T> ret = get((Class<T>) conf.getClass());
ret.setConf(conf);

至此，where過濾條件對應的FilterOperator構造完畢。

接下來仔細看下AND生成的ExprNodeDesc，它其實是一個ExprNodeGenericFuncDesc：

  // genericUDF是GenericUDFOPAnd，就是對應AND操作符private GenericUDF genericUDF;// AND是一個二元操作符，children里存的是對應的操作符// 根據WHERE語法樹，可以知道children[0]肯定又是一個ExprNodeGenericFuncDesc，而且是一個=函   // 數，而children[1]也是一個肯定又是一個ExprNodeGenericFuncDesc，而且是一個>函數，以此類     // 推，每個ExprNodeGenericFuncDesc都有對應的childrenprivate List<ExprNodeDesc> chidren;// UDF的名字，這里是andprivate transient String funcText;/*** This class uses a writableObjectInspector rather than a TypeInfo to store* the canonical type information for this NodeDesc.*/private transient ObjectInspector writableObjectInspector;

每個ExprNodeDesc都對應有一個ExprNodeEvaluator，來對每個ExprNodeDesc進行實際的計算。看下ExprNodeEvaluator類的基本方法：

public abstract class ExprNodeEvaluator<T extends ExprNodeDesc> {// 對應的ExprNodeDescprotected final T expr;// 在經過這個Evaluator計算后，它的輸出值該如何解析的ObjectInspectorprotected ObjectInspector outputOI;.../*** Initialize should be called once and only once. Return the ObjectInspector* for the return value, given the rowInspector.* 初始化方法，傳入一個ObjectInspector，即傳入的數據應該如何解析的ObjectInspector* 而需要返回經過這個Evaluator計算后的輸出值的解析ObjectInspector*/public abstract ObjectInspector initialize(ObjectInspector rowInspector) throws HiveException;// evaluate方法，調用來對row數據進行解析public Object evaluate(Object row) throws HiveException {return evaluate(row, -1);}/*** Evaluate the expression given the row. This method should use the* rowInspector passed in from initialize to inspect the row object. The* return value will be inspected by the return value of initialize.* If this evaluator is referenced by others, store it for them*/protected Object evaluate(Object row, int version) throws HiveException {if (version < 0 || version != this.version) {this.version = version;return evaluation = _evaluate(row, version);}return evaluation;}// 由各個子類實現的方法的_evaluate方法，結合上面的evaluate方法，這里實際使用了設計模式的模板   // 方法模式protected abstract Object _evaluate(Object row, int version) throws HiveException;...
}

通過ExprNodeEvaluatorFactory獲取到每個ExprNodeDesc對應的ExprNodeEvaluator：

  public static ExprNodeEvaluator get(ExprNodeDesc desc) throws HiveException {// Constant nodeif (desc instanceof ExprNodeConstantDesc) {return new ExprNodeConstantEvaluator((ExprNodeConstantDesc) desc);}// Column-reference node, e.g. a column in the input rowif (desc instanceof ExprNodeColumnDesc) {return new ExprNodeColumnEvaluator((ExprNodeColumnDesc) desc);}// Generic Function node, e.g. CASE, an operator or a UDF nodeif (desc instanceof ExprNodeGenericFuncDesc) {return new ExprNodeGenericFuncEvaluator((ExprNodeGenericFuncDesc) desc);}// Field node, e.g. get a.myfield1 from aif (desc instanceof ExprNodeFieldDesc) {return new ExprNodeFieldEvaluator((ExprNodeFieldDesc) desc);}throw new RuntimeException("Cannot find ExprNodeEvaluator for the exprNodeDesc = " + desc);}

看下FilterOperator中如何使用ExprNodeEvaluator對數據進行過濾的。

首先在FilterOperator的initializeOp方法中，獲取到ExprNodeEvaluator：

conditionEvaluator = ExprNodeEvaluatorFactory.get(conf.getPredicate());

然后在process方法中，調用initialize方法后，調用eveluate方法獲取到整個where過濾的結果：

conditionInspector = (PrimitiveObjectInspector) conditionEvaluator.initialize(rowInspector);
...
Object condition = conditionEvaluator.evaluate(row);
...
Boolean ret = (Boolean) conditionInspector.getPrimitiveJavaObject(condition);// 如果結果是true，則forward到下一個operator繼續處理
if (Boolean.TRUE.equals(ret)) {forward(row, rowInspector);
}

再來看下GenericUDFOPAnd的evaluate方法實現：

@Overridepublic Object evaluate(DeferredObject[] arguments) throws HiveException {boolean bool_a0 = false, bool_a1 = false;Object a0 = arguments[0].get();if (a0 != null) {bool_a0 = boi0.get(a0);if (bool_a0 == false) {result.set(false);return result;}}Object a1 = arguments[1].get();if (a1 != null) {bool_a1 = boi1.get(a1);if (bool_a1 == false) {result.set(false);return result;}}if ((a0 != null && bool_a0 == true) && (a1 != null && bool_a1 == true)) {result.set(true);return result;}return null;}

從以上代碼知道，在進行AND的計算時，如果左邊條件返回false，則不會進行右邊條件的計算，所以AND的順序其實是影響實際的效率的。類似的還有OR也是一樣的，如果左邊條件返回true，則不會進行右邊條件的計算。

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

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

相關文章

算術編碼（Arithmetic Coding）源代碼

算術編碼（Arithmetic Coding）源代碼

Ian H. Witten、Radford M. Neal和John G. Cleary在1987年發表了一篇啟發性的論文。論文中描述了一種基于整數運算的通用算術編碼器&#xff0c;而且還給出了由計算錯誤導致的效率低下的分析。以下源代碼來自于這篇論文&#xff1a;《基于算術編碼的數據壓縮》&#xff08;Arit…
閱讀更多...
pandas讀寫各種類型數據

pandas讀寫各種類型數據

read_X()通常是pandas模塊下的&#xff0c;to_X()是dataframe的方法 CSV 讀取 使用pandas.read_csv()方法&#xff0c;返回的是一個dataframe csv默認是以"&#xff0c;"分割的 csv文件內容 1、read_csv()默認以第一行數據作為標題 2、調用dataframe的head()方法…
閱讀更多...
python 類裝飾器

python 類裝飾器

1 裝飾器無參數 class tracer: def __init__(self,func): self.calls 0 self.func func def __call__(self,*args): self.calls 1 print(call %s to %s %(self.calls, self.func.__name__)) self.func(*args) tracer def spam(a, b, c): print(a b c) …
閱讀更多...
【數據分析】使用pandas和numpy分析美國大選獻金項目

【數據分析】使用pandas和numpy分析美國大選獻金項目

1. 數據載入與總覽 1.1 數據加載 #繪圖工具 import matplotlib.pyplot as plt %matplotlib inline #數據處理工具 import numpy as np import pandas as pd from pandas import Series,DataFrame#數據路徑自己指定&#xff0c;本案例數據路徑就在當前文件夾下面子文件夾usa_e…
閱讀更多...
《容器技術系列》一1.4　Docker運行案例分析

《容器技術系列》一1.4　Docker運行案例分析

本節書摘來華章計算機《容器技術系列》一書中的第1章 &#xff0c;第1.4節&#xff0c;孫宏亮　著, 更多章節內容可以訪問云棲社區“華章計算機”公眾號查看。 1.4　Docker運行案例分析 1.3節著重介紹了Docker架構中各個模塊的功能&#xff0c;學完后我們可以對Docker的架構有一…
閱讀更多...
算術編碼的原理與分析

算術編碼的原理與分析

轉自&#xff1a;http://kulasuki115.blogcn.com/diary,201492702.shtml 前言 人類已進入信息時代&#xff0c;信息時代的重要特征是信息的數字化&#xff0c;人們越來越依靠計算機獲取和利用信息&#xff0c;這就需要對信息的表示、存儲、傳輸和處理等關鍵技術進行研究。我們…
閱讀更多...
3月22日AM

3月22日AM

看了思維章節精講視頻課&#xff0c;并且總結了部分思維章節內容轉載于:https://www.cnblogs.com/bgd140206102/p/6601440.html
閱讀更多...
阿里巴巴Dubbo實現的源碼分析

阿里巴巴Dubbo實現的源碼分析

Dubbo概述Dubbo是阿里巴巴開源出來的一個分布式服務框架&#xff0c;致力于提供高性能和透明化的RPC遠程服務調用方案&#xff0c;以及作為SOA服務治理的方案。它的核心功能包括&#xff1a; remoting:遠程通訊基礎&#xff0c;提供對多種NIO框架抽象封裝&#xff0c;包括“同步…
閱讀更多...
POJ 2106-Boolean Expressions，雙棧運用類似表達式求值！

POJ 2106-Boolean Expressions，雙棧運用類似表達式求值！

Boolean Expressions 首先聲明此題后臺可能極水&#xff08;畢竟這種數據不好造&#xff01;&#xff09;。昨天寫了一天卻總是找不到bug&#xff0c;討論區各種數據都過了&#xff0c;甚至懷疑輸入有問題&#xff0c;但看到gets也可以過&#xff0c;難道是思路錯了&#xff1f…
閱讀更多...
H264 CAVLC 研究

H264 CAVLC 研究

目錄 1 CAVLC概念 2 CAVLC原理 3 CAVLC編碼流程 4 CAVLC解碼流程 展開全部 1 CAVLC概念 2 CAVLC原理 3 CAVLC編碼流程 4 CAVLC解碼流程 收起 摘要糾錯編輯摘要 CAVLC即基于上下文的自適應變長編碼。H.264標準中使用CAVLC對4*4模塊的亮度和色度殘差數據進行編碼。 CAVLC-CAVLC…
閱讀更多...
【MySQL 】學習筆記千行總結

【MySQL 】學習筆記千行總結

/* Windows服務 */ -- 啟動MySQLnet start mysql -- 創建Windows服務sc create mysql binPath mysqld_bin_path(注意&#xff1a;等號與值之間有空格)/* 連接與斷開服務器 */ mysql -h 地址 -P 端口 -u 用戶名 -p 密碼SHOW PROCESSLIST -- 顯示哪些線程正在運行 SHOW VARIABLES…
閱讀更多...
CCCC 連續因子

CCCC 連續因子

題意&#xff1a; 一個正整數N的因子中可能存在若干連續的數字。例如630可以分解為3*5*6*7&#xff0c;其中5、6、7就是3個連續的數字。給定任一正整數N&#xff0c;要求編寫程序求出最長連續因子的個數&#xff0c;并輸出最小的連續因子序列。 輸入格式&#xff1a; 輸入在一行…
閱讀更多...
Mybatis怎么能看是否執行了sql語句

Mybatis怎么能看是否執行了sql語句

項目需要學習mybatis中&#xff0c;本來mybatis也不是什么新技術&#xff0c;無奈之前沒接觸過。 驗證緩存機制時&#xff0c;需要能看到是否sql被執行了。這就需要增加日志的打印 配置如下 在pom中增加如下依賴&#xff1a; <dependency> <groupId>org.bgee.log4j…
閱讀更多...
定時備份 MySQL 并上傳到七牛

定時備份 MySQL 并上傳到七牛

定時備份 MySQL 并上傳到七牛 多數應用場景下&#xff0c;我們需要對重要數據進行備份、并放置到一個安全的地方&#xff0c;以備不時之需。 常見的 MySQL 數據備份方式有&#xff0c;直接打包復制對應的數據庫或表文件(物理備份)、mysqldump 全量邏輯備份、xtrabackup 增量邏輯…
閱讀更多...
vue_props div賦值props定義變量 templete獲取

vue_props div賦值props定義變量 templete獲取

vue_props div賦值props定義變量 templete獲取 <div id"app"> <add v-bind:btn"h"></add> </div> <script> var vm new Vue({ el: #app, data: { h: "hello" }, components: { "add": { …
閱讀更多...
H.264句法和語法總結 句法元素的分層結構

H.264句法和語法總結 句法元素的分層結構

在 H.264 定義的碼流中&#xff0c;句法元素被組織成有層次的結構&#xff0c;分別描述各個層次的信息&#xff0c;如下圖所示 在H.264 中&#xff0c;句法元素共被組織成 序列、圖像、片、宏塊、子宏塊五個層次。 在這樣的結構中&#xff0c;每一層的頭部和它的數據部分形成管…
閱讀更多...
instanceof 的運用

instanceof 的運用

2019獨角獸企業重金招聘Python工程師標準>>> Java 中的instanceof 運算符是用來在運行時指出對象是否是特定類的一個實例。instanceof通過返回一個布爾值來指出&#xff0c;這個對象是否是這個特定類或者是它的子類的一個實例。 用法&#xff1a; result object i…
閱讀更多...
R 腳本讀取匯總 Excel 表格數據

R 腳本讀取匯總 Excel 表格數據

主要用到了 xlsx 和 rJava 包&#xff0c;打開 Excel 文件&#xff0c;讀取各表格數據&#xff0c;再寫入到匯總表。 下圖為處理前的原始數據表格&#xff1a; 下圖為處理后的數據&#xff1a; 代碼實現 安裝&加載包的函數實現。installed.packages() 函數獲取所有已安裝…
閱讀更多...
[Grid Layout] Place grid items on a grid using grid-column and grid-row

[Grid Layout] Place grid items on a grid using grid-column and grid-row

It’s possible to position a grid item anywhere on a grid track. To do this, let’s specify some grid-template-columns and grid-template-rows, and to the grid items, we’ll pass grid-column and grid-row some numeric values. <!DOCTYPE html> <html l…
閱讀更多...
【大數據】最新大數據學習路線（完整詳細版，含整套教程）

【大數據】最新大數據學習路線（完整詳細版，含整套教程）

大數據學習路線 java(Java se,javaweb) Linux(shell,高并發架構,lucene,solr) Hadoop(Hadoop,HDFS,Mapreduce,yarn,hive,hbase,sqoop,zookeeper,flume) 機器學習(R,mahout) Storm(Storm,kafka,redis) Spark(scala,spark,spark core,spark sql,spark streaming,spark mllib,spa…
閱讀更多...
最新文章

Copyright @ 2022~2023