本文只阐述最基本的表级别的血缘关系的实现思路，真实的血缘实现，远比文章中的场景复杂。

• 原理一  SQL解析之正则表达式

source_table_regex = re.compile(r"(?:from|join)\s+(\S*)(?:\s+|;)", re.IGNORECASE)target_table_regex = re.compile(r"insert\s+(?:into|overwrite)\s+table\s+(\S*)\s+", re.IGNORECASE)

select * --from tableAfrom tableB;

select * from tableAwhere description = "from Excel";

• 原理二 AST语法树的解析
  
  

• • 名词解释
    
    

    词法分析器：词法分析器的工作是分析量化那些本来毫无意义的字符流，将他们翻译成离散的字符组（也就是一个一个的Token），供语法分析器使用。简单说就是分析sql里每个单词该怎么组成。
    
    
    语法分析：语法分析器将把收到的Tokens组织起来，并转换成语法规则定义的所允许的结构。简单说就是研究这些单词该以怎样的结构组成一个SQL的。
    
    

    Antlr：ANTLR (ANother Tool for Language Recognition ) 是一种语言识别工具，它提供了一个框架，可以通过包含 Java, C++, 或 C# 动作（action）的语法描述来构造语言识别器，编译器和解释器。

• • Hive SQL的解析流程：
    
    

1. 1. Hive根据Antlr定义的词法、语法规则完成词法、语法分析将HQL解析为AST Tree；
      
      

   2. 遍历AST Tree，抽象出查询的基本组成单元Query Block；
      
      

   3. 遍历Query Block解析为操作树Operator Tree(即，逻辑执行计划)；
      
      

   4. 逻辑优化器进行操作树变换，合并多余的ReduceSinkOperator，减少shuffle；
      
      

   5. 遍历Operator Tree，将操作树翻译为对应的MapReduce任务；
      
      

   6. 物理优化器进行MapReduce任务变换，生成最终的执行计划。

1. 对Hive SQL进行词法分析和语法分析，获取对应的AST 原始的抽象语法树
   
   
   
2. AST语法树剪枝优化，减少遍历次数，提高语义解析的效率，具体主要做两方面的优化：
   
   
   

• • 针对token中涉及到的无效解析节点进行删除,如order by，distributedby,cluster by,sort by以及limit；
    
    
    
  • 针对token中where/having的子查询，在保证SQL语法正确性以及语义完整性的前提下，采用1=1 等价策略进行等价替换，降低了血缘关系解析的复杂性；
    
    
    通过以上两种剪枝操作，既可以减少SQL语句的复杂性，又可以降低AST语法树的层级，进一步减少了遍历AST树递归次数，降低血缘分析的复杂性，提高了语句解析效率。

3. 遍历AST获取上游表名和下游表名，在SQL语句中存在大部分SQL语句片段即CTE。由于其在血缘关系解析中不起关键作用，且对SQL解析带来很大困扰，因此血缘关系解析需对CTE类型进行识别，并进行替换与删除。

4. 免责申明：
   
   本文系转载，版权归原作者所有，如若侵权请联系我们进行删除！

   《数据治理行业实践白皮书》下载地址：https://fs80.cn/4w2atu
   
   《数栈V6.0产品白皮书》下载地址：https://fs80.cn/cw0iw1
   
   想了解或咨询更多有关袋鼠云大数据产品、行业解决方案、客户案例的朋友，浏览袋鼠云官网：https://www.dtstack.com/?src=bbs
   
   同时，欢迎对大数据开源项目有兴趣的同学加入「袋鼠云开源框架钉钉技术群」，交流最新开源技术信息，群号码：30537511，项目地址：https://github.com/DTStack