最近在改一个SparkSQL AST解析相关的问题.
主要做一些权限管控校验重写的事情.
之前做过一版重写,现在反馈了几个问题.
一个是类似delete from table where子句的错漏.
一个是select from where not exists in (subquery)的子查询问题.
本质上其实都是同一类的设计缺陷.
因为当时并没有预期到expression的复杂性.
一般来说,不过是DDL还是DML语句,对应的AST的基本或者说主要语法要素单元是一个称之为logical plan的东西.
比如一个select语句通常对应的AST就是一个以project为root的向下由其他不同的logical plan构成的树形结构.
如果想对这个AST做一些动作,那么一个naive的approach就是针对各种logical plan做一个类似Finite State Machine的东西,递归地针对各个单元做应该做的事情.
这个的一个问题在于理论上需要穷举所有可能的logical plan实现,以保证完备性.
第二个是一个工程上的问题.
因为选取的extension point的问题,得到的AST并不是一个直接的从SQL lexer而成的.
而是经过经过了一定的rewrite/resolve rule得到的.
这就意味着有些logical plan可能并不会出现在extension point的context里.
也有可能因为其他组件系统的演化问题,一些logical plan可能,也可能没有被rewrite成另外的东西.
一个显著的例子就是代表着通常所说的表带logical plan.
parser出来结果一般是一个logical relation.
但是由于有着一些系统演化的问题,它可能会被rewrite成datasourcev2 relation,也就是较新的datasource接口的table.
也可能是hive relation,属于hive catalog范畴的表.
也可能还是一个logical relation,比如没有被以上两者涵盖的部分.
更麻烦的可能还是其中一些具体实现涉及到文件路径也需要audit的.
当然,这个相对于第一个问题来说,还不是太大的问题.
毕竟case by case能够解决.
完备性的问题在于像iceberg之类的会对语法做扩展的.
也就意味着会产生意料之外的logical plan的情况.
它的问题是本身也是一个case by case的工程性问题.
同时还有一些runtime问题.
因为它不一定在某个场景里有存在/注册,所以在runtime需要一些比较tricky的东西去发现和适配.
当然这些终究还是一个工程上的问题.
开头说的两个问题主要还是因为FSM的设计只考虑了logical plan.
没有考虑内嵌其中的expression.
某种形式来说,就是FSM的完备性的问题.
如果要在FSM的基础上继续改进的话,也就是需要把节点往下拆一层到expression.
这个一方面是需要更针对性的对每个logical plan做specialize.
本身就属于逐渐失控的一种表现.
更重要的在于expression还有自己要解决问题.
因为像not exist (subquery) 这种是一类特别的expression,内嵌一个logical plan,resolve的call site context是subquery.
也就是里面的column/attribute的上下文是跟subquery有关.
而像delete where condition的where子句的expression的call site根据具体情况可能是from table也可能是包含了not exists(subquery)子句的复合型expression.
所以当这里需要校验expression所最终引用的column来自哪里的时候就具有一定的复杂性了.
单纯递归的时候需要根据expression的形态去选择具体的callsite.
这样的话就更进一步地对FSM的完备性提出了挑战和不确定性.
再一个就是column的resolution本身也不是一件水到渠成的事情.
例如
select
column
from (
select
column + 1 as column
from (
select ...
)
)
这种复合expression加alias的形式.
intuitive地方式就逐层针对具体的expression去解析然后递归向下.
而这个递归的过程不可避免地会存在not exists(subquery)这类特殊型需要辨别call site的.
于是FSM不可避免地explosion化.
一个可能更实际一些的方式是折衷化的FSM.
大致来说,上面提到的复杂的case都是基于query context的.
那么只要不对query context的logical plan做FSM就想对来说不容易explosive.
而query如果只考虑解析column引用的话,实际上还是想对简单的.
因为容易证明,所有expression reference的attribute无非指向两处.
一个是最终table的attribute/column,也就是期望得到的结果.
一个是指向其他直接或者间接引用了attribute/column的expression.
还有一类就是literal/constant,可以忽略.
于是对于一个well form的AST的expression来说,如果它不是一个常量或者直接指向一个column,那么它就是一个indirect column.
这个indirect column必然递归地会指向上述三种情况之一.
那么实际上对expression的递归过程只需要关注是不是指向了column或者常量就行了.
而不需要naive地去解析一一对应关系,只需要关注存在性即可.
当然,这里还可以有其他一些考虑.
比如在build FSM和column resolve的时候能不能stream build/one pass地完成.
以及难度如何的问题.
粗略想了下, 它可能类似于与constexpr或者constan.template/meta programing的范畴.
或者是一个NP/NP hard的问题.
因为理论上来说给定一个input,它的output是deterministic的.
它一方面需要的是如何像traveling sales man的看是否存在一条这样的branching路径.
一方面是要看所需要的context是否能够on-demand的生成.
如果条件/问题放宽一些的话.
就是如何尽可能地lazy而又尽可能所需要的东西evaluate only once的问题了.
没有评论:
发表评论