(3条消息) sql 解析,编译,ast 抽象语法树 / 四六文摘

es现在几乎已经是开源搜索引擎的事实标准了，搭建简易，使用方便。不过在很多公司里(包括我司的部分部门)，并不是把它当搜索引擎来用，而是当db来用。因为本身查询/搜索原理的区别，使es在千万或者亿级的数据中进行逻辑筛选相对高效。例如一些wms、工单查询系统，单表几十个甚至上百个字段，如果在数据库里为每种类型的查询都建立合适的索引，成本比较高，更不用说索引建多了还会影响到插入速度，后期的索引优化也是比较麻烦的问题。

不过如果把es当db来使的话，始终会有一个绕不过去的坎。就是es的DSL。让所有业务开发去学习dsl的话也不是不可以，但DSL真的有点反人类(不要打我)。简单的a and b或者a or b还比较容易写，如果我要的是a and (b and (c or d) and e)的查询逻辑，那我觉得谁写都会晕。即使是用官方或者第三方提供的client，如果需求多种多样的话，想要灵活地实现`需求=>DSL`的过程还是比较痛苦。

对于业务开发来说，当然是sql更平易近人(毕竟写了这么多年CRUD)。所以还有一种歪门邪道的流派，直接把sql转成DSL。要做sql和DSL转换的工作，需要进行sql的解析，先不要怵，这个年代找一个靠谱的sql parser还是比较容易的。比如阿里开源的druid连接池里的sql模块：

https://github.com/alibaba/dru ... d/sql

因为笔者的实现是用的下面这个golang版的parser：

https://github.com/xwb1989/sqlparser

所以用这个来举例吧~

这个是其作者从youtube/vitness里提取并进行改进的一个parser，我们能用到的是一部分子集功能，只需要解析select类的sql。

先举个简单的sql的例子：

select * from x_order where userId = 1 order by id desc limit 10,1;
解析之后会变成golang的一个struct，来看看具体的定义：
&sqlparser.Select{
Comments:sqlparser.Comments(nil),
Distinct:"",
SelectExprs:sqlparser.SelectExprs{(*sqlparser.StarExpr)(0xc42000aee0)},
From:sqlparser.TableExprs{(*sqlparser.AliasedTableExpr)(0xc420016930)},
Where:(*sqlparser.Where)(0xc42000afa0),
GroupBy:sqlparser.GroupBy(nil),
Having:(*sqlparser.Where)(nil),
OrderBy:sqlparser.OrderBy{(*sqlparser.Order)(0xc42000af20)},
Limit:(*sqlparser.Limit)(0xc42000af80),
Lock:""
}


sql的select语句在被解析之后生成一个Select的结构体，如果我们不关心使用者需要的字段的话，可以先把SelectExprs/Distinct/Comments/Lock里的内容忽略掉。如果不是分组统计类的需求，也可以先把GroupBy/Having忽略掉。这里我们关心的就剩下From、Where、OrderBy和Limit。
From对应的TableExprs实际上可以认为是简单的字符串，这里的值其实就是`x_order`。

OrderBy实际上是一个元素为

type Order struct {Expr      ValExprDirection string}\

的数组。

Limit也很简单，

type Limit struct {Offset, Rowcount ValExpr}

其实就是俩数字。

那么剩下的就是这个Where结构了。where会被解析为AST(` https://en.wikipedia.org/wiki/Abstract_syntax_tree`)，中文是抽象语法树。在不说子查询之类的情况下，这个AST也不会太复杂，毕竟where后面的情况比起编译原理里的程序语言来说情况还是要少得多的。以上述的sql为例，这里解析出来的Where结构是这样的：

&sqlparser.Where{Type:"where",Expr:(*sqlparser.ComparisonExpr)(0xc420016a50)}


只有一个节点，一个ComparisonExpr表达式，这个ComparisonExpr，中文比较表达式，指代的就是我们sql里的`user_id = 1`。实际上我们可以认为这个"比较表达式"即是所有复杂AST的叶子节点。叶子结点在AST遍历的时候一般也就是递归的终点。因为这里的查询比较简单，整棵AST只有一个节点，即根节点和叶子节点都是这个ComparisonExpr。

再来一个复杂点的例子。

select * from users where user_id = 1 and product_id =2
=>
&sqlparser.Where{
Type:"where",
Expr:(*sqlparser.AndExpr)(0xc42000b020)
}
AndExpr有Left和Right两个成员，分别是：
Left:
&sqlparser.ComparisonExpr{
Operator:"=",
Left:(*sqlparser.ColName)(0xc4200709c0),
Right:sqlparser.NumVal{0x31}
}
Right:
&sqlparser.ComparisonExpr{
Operator:"=",
Left:(*sqlparser.ColName)(0xc420070a50),
Right:sqlparser.NumVal{0x32}
}


稍微有一些二叉树的样子了吧。把这棵简单的树画出来：

回到文章开头的那个复杂的例子：

a and (b and (c or d) and e)
=>
select * from user_history where user_id = 1 and (product_id = 2 and (star_num = 4 or star_num = 5) and banned = 1)


看着真够麻烦的，我们把这棵树画出来：


这样看着就直观多了。我们有了AST的结构，那要怎么对应到es的查询DSL呢？少安毋躁。
我们知道es的bool query是可以进行嵌套的，所以实际上我们可以同样可以构造出树形结构的bool query。这里把bool嵌套must和bool嵌套should简化一下，写成boolmust和boolshould：

例如a and (b and c)

query {boolmust {a,boolmust {b,c}}}


我们把query内部的第一个boolmust当作根节点，内部嵌套的a和另一个boolmust当作它的两个子节点，然后b和c又是这个boolmust的子节点。可以看出来，实际上这棵树和AST的节点可以一一对应。

再回到文章开头的例子，a and (b and (c or d) and e)：

query {boolmust {a,boolmust {b,boolshould {c,d},e}}}

和前文中ast来做个简单的结构对比~


和前文中sql的where解析后的AST树也是完全匹配的。思路来了，只要对sql解析生成的AST进行递归，即可得到这棵树。当然了，这里还可以进行一些优化，如果子节点的类型和父

节点的类型一致，例如都是and表达式或者都是or表达式，我们可以在生成dsl的时候将其作为并列的节点进行合并，这里不再赘述。

在递归中有这么几种情况：

AndExpr => bool must [{left}, {right}]OrExpr => bool should [{left}, {right}]ComparisonExpr => 一般是叶子节点ParenBoolExpr => 指代括号表达式，其实内部是上述三种节点的某一种，所以直接取出内部节点按上述方法来处理


这样问题就变成了如何处理AST的叶子节点。前面提到了叶子节点实际上就是Comparison Expression。只要简单进行一些对应即可，下面是我们的项目里的一些对应关系，仅供参考：

最后再附上demo https://github.com/cch123/elasticsql

(3条消息) sql 解析,编译,ast 抽象语法树

相关推荐