(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的例子:

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

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。

再来一个复杂点的例子。

  1. select * from users where user_id = 1 and product_id =2
  2. =>
  3. &sqlparser.Where{
  4. Type:"where",
  5. Expr:(*sqlparser.AndExpr)(0xc42000b020)
  6. }
  7. AndExpr有Left和Right两个成员,分别是:
  8. Left:
  9. &sqlparser.ComparisonExpr{
  10. Operator:"=",
  11. Left:(*sqlparser.ColName)(0xc4200709c0),
  12. Right:sqlparser.NumVal{0x31}
  13. }
  14. Right:
  15. &sqlparser.ComparisonExpr{
  16. Operator:"=",
  17. Left:(*sqlparser.ColName)(0xc420070a50),
  18. Right:sqlparser.NumVal{0x32}
  19. }

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

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

  1. a and (b and (c or d) and e)
  2. =>
  3. 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

(0)

相关推荐

  • python ast 语法分析

    ast(Abstract Syntax Trees)是python中非常有用的一个模块,我们可以通过分析python的抽象语法树来对python的代码进行分析和修改. ast作用在python代码的语 ...

  • 比开源快30倍的自研SQL Parser设计与实践

    SQL(Structured Query Language)作为一种领域语言(编程语言),最早用于关系型数据库,方便管理结构化数据:SQL由多种不同的类型的语言组成,包括数据定义语言,数据控制语言.数 ...

  • (7条消息) gcc 如何编译cpp文件啊

    文章目录 gcc 如何编译cpp文件啊 gcc编译C++程序 多个源文件生成可执行程序 源文件生成对象文件 编译预处理 生成汇编代码 创建静态库 gcc 如何编译cpp文件啊 /* hello.c * ...

  • (6条消息) python文件编译与pyc反编译

    pyc是编译py之后生成的二进制文件.当我们发布系统的时候不想让别人看到源代码,就需要将py文件编译生成pyc文件,对外只提供pyc文件.同样,如果拿到一个python程序,只有pyc文件,我们就无法 ...

  • (5条消息) MDK 的编译过程及文件类型全解

    出处:MDK 的编译过程及文件类型全解 MDK 的编译过程及文件类型全解 ------(在arm9的开发中,这些东西都是我们自己搞定的,但是在windows上,IDE帮我们做好了,了解这些对深入开发是 ...

  • (100条消息) sql语句练习50题(Mysql版)

    习题来源于网络,sql语句是自己写的,部分有参考.欢迎指正. 2019.3.29更新 写完后一年没有看过,没想到这篇文章有这么多人点击.博主工作到一半去考研了,目前已上岸某中部985,也算是比较幸运. ...

  • (59条消息) 不使用webpack 不用编译 也能使用 vue组件,单文件vue: ,那就是使用 http

    上週在 Vue 社群圈有個令人興奮的熱門新聞: CodePen 可以支援 .vue 檔案了! Check it out - you can use `.vue` files in CodePen Pr ...

  • (1条消息) VBA正则表达式深度解析

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明. 本文链接:https://blog.csdn.net/qq_25846269/article/ ...

  • (9条消息) linux下opencv4.2编译cuda的那些坑

    目录 1.编译cmake 2.配置 3. 编译 4. opencv4.2使用中的问题 1. c++11标准的支持 2. cuda支持 前言:opencv4.2版本19年12月发布,其最重要的改变是增加 ...

  • (14条消息) 使用ConfuserEx加密混淆程序以及如何脱壳反编译

    ConfuserEx是.NET下的一款开源混淆工具,功能比较强大,应用也较广泛,本文就使用ConfuserEx工具演示如何混淆及如何对其混淆的程序进行脱壳. 所需工具: 请自行百度下载如下工具: Co ...

  • (13条消息) 阿里云储道深度解析存储系统设计

    NVMe SSD的性能时常捉摸不定,为此我们需要打开SSD的神秘盒子,从各个视角分析SSD性能影响因素,并思考从存储软件的角度如何最优化使用NVMe SSD,推进数据中心闪存化进程.本文从NVMe S ...