从事SQL血缘解析一年后，谈谈我对它的理解
今天是2023年2月12日，据我上一次发表文章已经过去了半年多的时间，这篇文章主要是针对过去一年里参与解析工作的一些感悟，希望大家可以从中有所收获。
[scode type="share"]本文持续更新中[/scode]
目前博主在公司内具体研究方向为SQL解析与应用，在 BIG 产品中目前的SQL列级血缘解析在客户现场经验证已达到99%的准确率（未支持的特殊语法属于变量）。
由于讨论范围属于公司核心技术领域，本文只是稍微写一些我做解析一年多来的认识，可以给没有做过SQL血缘解析、或准备做其他解析的同学一些思路。我在2022年前3个月份发布了一些文章，那些都是我刚接触这一块时所记录的文章，现在看里面有许多错误的地方，那些文章就可以不用再看了。
SQL血缘解析所带来的价值和应用，这里就不再阐述了，这里直接上重点部分。
在此之前你可能需要先了解一些概念：
- DSL
- 词法解析，语法解析
- 抽象语法树（AST）
- 关系代数和逻辑执行计划
如果你不了解这几个概念，或者不是太熟悉，建议先在网上查阅一些资料。
那么，针对SQL的血缘解析，这里要分两个东西去看：解析 和 血缘 。当然，是 解析在前、血缘在后。
很明显，解析是血缘的基础，血缘是对解析的应用，如果把“SQL血缘解析”解释的再详细一些，那么就是“解析SQL并提取其中的血缘关系”。那么，当我们拿到血缘解析这个命题的时候，要分两步去做：
- 解析SQL
- 提取血缘
那么这里就牵出两个新的问题
- 如何解析SQL
- 如何提取血缘
当我们最早学习Mysql的时候，或多或少都有敲过它的一些语法，拿最简单的：SELECT c1 FROM t1;，如果我们把FROM不小心打成了FRPM，这个时候把命令提交给数据库引擎后就会报错，提示错误的语法等提示，那么这里需要思考的是，引擎它是怎么知道我不应该输入 FRPM，而是 FROM。
无论是SQL，还是JAVA还是其他语言，本质上都是一种DSL(domain special language)，而我们在输入某种特定的DSL时，其相应的程序第一步要做的事情就是校验你输入的语句是否符合正确的语法，简而言之就是会去解析你输入的语句。
在《编译原理》中，通常对文本的解析会包含词法分析，语法分析和语义分析，在语法分析和语义分析阶段都会产生相应的抽象语法树AST。因为对于一个文本 string ，我们对其里面的信息是无从下手的，所以我们需要将其转化成一种对象结构，就是指这里的抽象语法树AST。
（如果你对词法分析、语法分析、抽象语法树还不了解的话，需要先了解这些知识）
由此可知，我们解析一条sql，有以下两个作用：
- 判断该sql的语法是否正确
- 得到该sql的抽象语法树AST
那么我们可以通过哪些工具解析sql得到ast呢？
- Antlr
- Calcite
- Druid
- （其他类似druid手写解析器）
所以，这里建议大家可以先了解下 Antlr 和 calcite，这里有我的一个对比
我主要详细说下 Antlr 的，去年1月份写的那篇文章可能已经过期了， Antlr 的词法文件还是很全的，可以在官方社区里找到：
antlr/grammars-v4/tree/master/sql
我们可以看到主流的sql语法这里都支持了，对于其他的，例如sparkSQL，clickhouse内部也是使用的antlr，在他们对应的代码中我们也可以找到相应的g4文件。
Antlr的使用这里我也不过多赘述，起码我们解析一条sql，拿到生成的抽象语法树应该不成问题。
[scode type="green"]2023年12月19日更新[/scode]
当我们有了相应的解析树/抽象语法树（这里有两种不同的叫法，我觉得严格意义上都可以算作AST），这个时候我们可以选择从AST中去拿表表依赖关系了，只用递归遍历就好，用到的表都属于来源表，insert/create位置算输出表，应该表表血缘是最好提取，几乎不会失败。
然而列与列的依赖关系就复杂了一个量级，由于SQL本身结构的千变万化，如果直接从 AST 阶段直接分析列与列之间的依赖关系十分复杂，不同的方言之间又会造成 AST 不同，到后面只会不断地支持新语法，准确度也不了了之。
其实我们可以借鉴 Calcite，在抽象语法树之后经过校验转换到关系代数 RelNode 模型，在这一个模型上进行优化，这个模型已经和方言无关了，而且是一些数学领域的表达式，方便后续根据编排规则优化。
这里其实我建议也要设计一个方便于分析血缘的一个模型，这个模型与方言无关，突出列与列之间的依赖关系。这样你写好从该分析模型提取血缘的代码之后，之后需要补充的大多就是抽象语法树到该分析模型的代码了。
概括来说就是：
SQL ----> AST ----> AnalyzeModel ----> Result
当然我在 BIG 中所做的要更加复杂，自研的分析模型除了要满足列与列之间的依赖关系，也要有列与算子之间的依赖关系，来做到算子级的血缘，核心点就在于这个分析模型如何去设计。2023年12月15日我们公司也进行了产品发布会，作为全球首个算子级血缘的主动元数据平台，这篇文章我记了个 milestone。