这一讲的内容以 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 怎样序列化表达通用的树。