【数据结构】树在 Amazon 中的应用(10)

这一讲的内容以 Amazon 云服务为例,来分享分布式 SQL 数据库如何使用树这样的数据结构优化 SQL 执行的。虽然我迫不及待地想和你直接深入底层技术原理,但是在讲解非常酷的技术细节之前,我们还是先回过头看一下什么是 SQL 执行优化?为什么要优化 SQL 执行?

什么是 SQL

SQL(Structured Query Language)在硅谷科技公司一般读作 sequel,其实在 1970 年代 IBM 发明 SQL 的时候它本来被称作 SEQUEL(Structured English Query Language),但后来因为 SEQUEL 作为商标已经被注册了,只能改名为 SQL。不熟悉这段历史的人有时候会读作 S-Q-L(分开三个字母读),虽然也听得懂的,但没有那么地道了!

SQL 被用来管理和查询关系型数据库。比如:

SELECT name FROM table;

这样一行 SQL 可以选取下表中所有的 name 这一列:

执行这行 SQL 指令的输出一般就是 Alex、David、Patrick。

SQL 在 20 世纪 80 年代成为了 ANSI/ISO 国际标准。但即使是国际标准,不同的关系型数据库的实现都有很多不同,比如 MySQL、PostgreSQL 对于 SQL 标准的实现就不同。更不用说在专门优化的大型分布式数据库就更不一样了,比如本文要介绍的 Amazon 云服务 AWS 里所使用的 SQL 执行引擎,就拥有很多独门秘籍的实现。

为什么要优化 SQL 的执行

我们已经了解了 SQL 最常用的用途就是查询数据。然而关系型数据库在执行 SQL 语句时必须要考虑效率,即:

  • 需要多长时间完成这条 SQL 查询?

  • 需要多少计算资源,包括 CPU、磁盘、电能去执行这条 SQL 语句?

关系型数据库具体怎样执行 SQL 语句我们称之为执行计划(Execution Plan),很不幸的是同样一条 SQL 语句的可选执行计划非常多。我们来看一个例子:

SELECT *
FROM customers c, orders o
WHERE c.id = o.cust_id AND c.creation_timestamp < 1579069516;

这个例子的 SQL 从语义上理解的话,是想要在 customers 和 orders 这两种表中,找出所有 customers 的 creation_timestamp 早于某个时间的所有数据,看起来似乎很好理解啊。其实背后的 SQL 引擎在执行它的时候是有很多纠结的,纠结什么呢?就是选择执行计划。

由于篇幅有限,在这里就不再罗列所有可能的执行计划了。但是为了阐述我的观点,以下列举了几个执行计划的例子:

  • Creation_timestamp 小于这样一个过滤条件应该在 JOIN 语句前执行呢,还是在 JOIN 语句之后执行?

  • 对于 JOIN 语句我们应该使用 merge join,还是 hash join,还是用建立的 index 使用 nested loop join 呢?

  • 如果是 hash join 或者 nested loop join 的话,我们应该是先遍历 cutomers 表然后查找对应的 orders,还是先遍历 orders 表再查找对应的 customers 呢?

  • 如果我们对于 creation_timestamp 建立有二级索引(Secondary Index)的话,我们是应该用二级索引查找 creation_timestamp 还是用主索引查找 ID 比较快?

作为数据库 SQL 引擎,这些问题的答案都是相互依赖的,也都是需要交叉考虑的。比如说如果选择 nested loop join,可能搭配使用二级索引比较好;但是如果使用 merge join 的话,可能还是使用主索引比较好。最优的执行计划还取决于我们的表有多少行,各种物理操作的相对速度,还有不同数据的存储位置和数据值的分布等,可以说要考虑的参数是非常非常的多!

所以在 Amazon AWS 这样大型的分布式 SQL 数据库中,对 SQL 的执行计划进行了大量的优化。一个简单的 SQL 执行引擎模型是这样子的:

  • 首先是 SQL 解析器(Parser),它负责把用户输入的 SQL 解析成 SQL 语法树(AST),对的,就是我们讲的树!

  • 后面的 SQL 优化器(Optimizer)接受前面解析的原生语法树,对它进行优化重写语法树和执行计划。一般优化器不仅仅会看语法树,还需要结合特定的用户数据库配置,数据实际分布进行优化。

  • 最后面的 SQL 执行器(Executor)才会去真正的执行优化重写的 SQL 语法树。

SQL 语法树是个什么树

AST(Abstract Syntax Tree)即语法树,在计算机科学中是用树来表达源代码的一种方式。我们理解的编译器很大一部分工作就是把源码表示成语法树。不过在这里不展开语法树的讲解,因为这实在是一个巨大深奥的计算机科学主题,这一讲会专注在理解 SQL 这个语言的 AST 表达上。

我们来看一个很简单的例子:

SELECT name FROM table;

还是在我们刚才表中选取 name 这一列。

如果用语法树表达的话会是下面图中的样子,这个树的根是 SELECT 节点,在下面左子树是 name,右子树是 FROM 节点为根的子树。FROM 节点下面是 table 叶子节点。

在用 AST 表达 SQL 语句时,SQL 操作符永远是子树的根,而树的叶子则是比如这里的 name 或者 table。

用 AST 解析 SQL 语句之后,我们对于 SQL 语句的分析和优化就变得更为直接了。你可以很快找出这个 SQL 语句的操作就是 SELECT 和 FROM,他们都是子树的根节点。每一个 SQL 语句中的 token 在语法书中都拥有了语义上的含义,比如 from 和 name 不仅仅是单词不一样,他们在语义上是不同的含义,from 是操作,而 name 是一张表中的列名称。

我们可以根据解析后的语法树对这棵树做进一步的修改,比如在 FROM 下面的子节点我们知道是一个表的名字,可以把表的完整路径解析出来;再比如我们知道 SELECT 下面的左子树是一个表的列名称,可以把完整的表名称解析出来。在做完这些名字的解析之后,这个 SQL 语法树就变成了如下图所示的样子。

我们可以看到,原来的 name 节点变成了 schema.table.name,而原来的 table 节点变成了 schema.table,这些名称的解析只需要通过操作树的节点就可以了,是不是很方便啊!

树的序列化和 S-expression

我们已经知道了在大型分布式树的数据库中,SQL 的语法树解析是整个 SQL 引擎的第一步。那么在后续的优化器和执行器中我们是怎样传递这棵树的呢?要知道,在 Amazon 分布式数据库中,众多系统不仅仅是几个简单的函数而已,往往是好几个不同的服务器组合而成,在不同的服务器 RPC 之间传递树,我们需要把树序列化成可以在网络中传输解析的格式。

这就是 S-expression 了,S-expression 有时候也简称为 sexp,最初是由 Lisp 语言发明并被人们广泛使用。现在的 S-expression 已经有很多变种,常见的 S-expression 被定义为:

  • 一个不可分的元素(atom)

  • 或者是 “(x y)”,左括号,x,y,右括号的形式,其中 x 和 y 都是 S-expression

其实从这个定义来看的话,也和我们树的定义非常像,都是递归式定义。我们来看看刚才 SQL 语法树用 S-expression 怎样表示?还记得我们 SQL 语法树的根是一个 SELECT 节点嘛,下面还有一个以 FROM 为根节点的子树。你也许想到了我们可能需要一个嵌套的 S-expression,的确如此,正是像下面这样:

(SELECT schema.table.name (FROM schema.table))

 我们需要有一个嵌套的括号,在这里,括号的第一个 token 被定义成这个括号表达的子树的根,每一个嵌套的括号就是一个子树。

S-expression 的反序列化也很简单,只需要把每一个括号展开成一个子树就可以了!这样你就可以在系统中的不同服务之间用 RPC 传递这样的 S-expression。把一些中间计算的树传递给之后的系统服务。

总结

这一讲我们学习了树在 Amazon 这样的超大型分布式数据库系统中是如何应用的。首先了解了为什么超大型分布式数据库需要对 SQL 引擎进行优化;然后分析了怎么解析 SQL 语法树,怎样用树表达一个 SQL 语句,为什么树的表达能给我们处理 SQL 语句带来便利;最后学习了 S-expression 怎样序列化表达通用的树。

标签