语法解析
我们DBA平时通过SQL和数据库进行交互。SQL是一门典型的第四代语言,只用说明我要什么,而不需要写出来我要怎么做,这一点在之前的文章中讲过。
既然有查询优化器,那么一定要首先有一个翻译的地方存在,将SQL翻译成一种优化器能懂的语言。
这就是AST,所谓抽象语法树。
我认为,AST算是数据库王冠上一颗闪亮的宝石了。
下面透过RadonDB的源码,追寻一下AST的踪迹吧。
// Insert represents an INSERT or REPLACE statement.
// Per the MySQL docs, http://dev.mysql.com/doc/refman/5.7/en/replace.html
// Replace is the counterpart to `INSERT IGNORE`, and works exactly like a
// normal INSERT except if the row exists. In that case it first deletes
// the row and re-inserts with new values. For that reason we keep it as an Insert struct.
// Replaces are currently disallowed in sharded schemas because
// of the implications the deletion part may have on vindexes.
type Insert struct {
Action string
Comments Comments
Ignore string
Table TableName
Columns Columns
Rows InsertRows
OnDup OnDup
}
const (
// InsertStr represents insert action.
InsertStr = "insert"
// ReplaceStr represents replace action.
ReplaceStr = "replace"
)
// Format formats the node.
func (node *Insert) Format(buf *TrackedBuffer) {
buf.Myprintf("%s %v%sinto %v%v %v%v",
node.Action,
node.Comments, node.Ignore,
node.Table, node.Columns, node.Rows, node.OnDup)
}
// WalkSubtree walks the nodes of the subtree.
func (node *Insert) WalkSubtree(visit Visit) error {
if node == nil {
return nil
}
return Walk(
visit,
node.Comments,
node.Table,
node.Columns,
node.Rows,
node.OnDup,
)
}
// InsertRows represents the rows for an INSERT statement.
type InsertRows interface {
iInsertRows()
SQLNode
}
以上是比较简单的Insert的AST代码实现部分,从代码里看到,这个AST包括了insert和replace语法的解析,这里就定义了两个常量。
接下来的Format方法开始对Insert语句进行格式化,这里就可以观察出Insert结构体的所有域是干什么的了。但是这里我没有看到values,我觉得有点奇怪,这一点等我以后看看别的ast实现再琢磨琢磨。
WalkSubtree方法负责去构造树,采用递归的办法:
func Walk(visit Visit, nodes ...SQLNode) error {
for _, node := range nodes {
if node == nil {
continue
}
kontinue, err := visit(node)
if err != nil {
return err
}
if kontinue {
err = node.WalkSubtree(visit) //有点递归的意思了
if err != nil {
return err
}
}
}
return nil
}
这里用了递归的办法,我也不知道效率怎么样,但是我是不喜欢递归的,递归让程序变得令人迷惑。
下面看看比较复杂的select部分,也是SQL优化的重点部分。
考虑一下这个SQL:
select * from test where id = 1;
如果这样的语句构造抽象语法树,是一个什么样子呢?
说起来有点丈二和尚摸不着头脑了,那么先看看AST中的代码是怎么写And条件的:
func (node *Select) AddWhere(expr Expr) {
if _, ok := expr.(*OrExpr); ok {
expr = &ParenExpr{Expr: expr}
}
if node.Where == nil {
node.Where = &Where{
Type: WhereStr,
Expr: expr,
}
return
}
node.Where.Expr = &AndExpr{
Left: node.Where.Expr,
Right: expr,
}
}
上面那个SQL的解析到这里就会变成一个结构体:
type Where struct {
Type string
Expr Expr
}
具体说来是这样的:
{
Type:"Where"
Expr://一个具体的地址
}
现在来构造一下这颗树:
ast1不要笑,事实就是这样,只有一个where条件代表只能构造一个单节点的树。那么接下来把SQL写的复杂一点:
select * from test where id = 1 and name = 'quan';
这次会生成一个如何的结构体呢:
node.Where.Expr = &AndExpr{
Left: node.Where.Expr,
Right: expr,
}
我们姑且将所有的条件都加一个序号,从左向右递增,那么id是1,name是2,这个时候我们可以根据这段代码构造一个树:
ast2嗯,有模有样的一棵二叉树了,再把条件整的复杂一点:
select * from test where id = 1 and name = 'quan' and score > 60;
继续我们的编号准则,score的编号是3,此时的AST应该是这样的:
ast3这么看来根节点的右子树会变得非常非常大。
网友评论