本章前五节主要介绍 SQL 引擎优化器的作用以及 OceanBase 中查询改写和查询优化框架及细节。后四节主要介绍 OceanBase 中 SQL 执行引擎的相关设计。

4.1 查询优化器简介

大家都知道 SQL 是一种描述性的语言，用户可以通过 SQL 告诉数据库我们想要一个什么样的结果。但是它并不会告诉数据库要如何去做，而决定如何去做就是优化器的事情。

优化器会枚举出所有可以完成这个 SQL 请求的执行计划，并且结合统计信息和代价模型估算出每一个执行计划的代价（这里的代价通常是用执行计划的执行时间表示）。因为不同执行计划的性能可能存在几十倍、上百倍甚至上千倍的差距。因此一个好的执行计划对于 SQL 的执行至关重要。

举一个例子进行说明，实现同一个功能，一个刚接触编程的人实现的算法的时间复杂度可能是 O(n^3)，一个正常水平的程序员实现的算法的时间复杂度可能是 O(n^2)，而一个顶尖的程序员实现的算法的时间复杂度可能只会有 O(n)。这个例子可能不是那么恰当，但是可以说明优化器对于数据库是十分重要的，可以说优化器是数据库性能非常重要的组成部分。

优化器框架介绍

目前业界最常用的优化器框架有两个：

• 以 IBM 为代表的 System-R 框架，像 Oracle 和 PG，以及 OceanBase 使用的都是这个框架。

  在这个框架中，当数据库接收到一条 SQL 后会通过 Parser 和 Resolver 把 SQL 转成一个形式化的数据结构 statement 来描述原始的 SQL。接下来优化器会以这个 statement 作为输入，对这条 SQL 进行查询改写。这里做的事情实际上就是在不断的改写这个数据结构，得到一个最终的 statement。该 statement 会经过一个基于动态规划的计划生成器来得到最终的物理执行计划

• Cascade 框架，SQL Server 使用的就是这个改写框架。

  在这个框架中，Parser 和 Resolver 结束后，直接得到的就是一个逻辑计划树，然后通过一系列的规则体系改写这个计划树来得到最终的执行计划。所以这个改写规则就包含了很多内容，比如说它既包含了通常说的一些改写规则，也包含了计划生成的一些优化规则。然后它会不断去迭代，直到收敛，或者是通过基于规则的一些控制，来保证迭代不会无限地循环下去。

上文也说过 OceanBase 的优化器使用的是 System-R 框架，整体上框架基本可以参考下图。

其中，查询改写部分有基于规则的改写和基于代价的改写，详细信息请参考 4.2 查询改写。

计划生成部分，会通过一个动态规划的算法来生成最终的执行计划，包括基表访问路径选择、连接顺序连接算法选择、其它算子分配、分布式计划优化等等。此外还有代价模型和统计信息来辅助计划的生成，代价模型和统计信息这两个是任何数据库都离不开的。详细信息请参考 4.3 查询优化。