学习RadonDB源码（八）

语法解析

我们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://一个具体的地址
}

现在来构造一下这颗树：

不要笑，事实就是这样，只有一个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，这个时候我们可以根据这段代码构造一个树：

嗯，有模有样的一棵二叉树了，再把条件整的复杂一点：

select * from test where id = 1 and name = 'quan' and score > 60;

继续我们的编号准则，score的编号是3，此时的AST应该是这样的：

这么看来根节点的右子树会变得非常非常大。