SQL 物理逻辑优化，Volcano Optimizer

SQL 查询优化的目的

优化器在整个数据库系统中占据着至高无上的地位，它是数据库性能的决定因素，是所有数据库引擎中最重要的组件。

⑴使用的角度

因为SQL 是一种声明式(Declarative)的编程语言， 相比一般的编程语言描述的是程序执行的过程，这类编程语言则是描述问题或者需要的结果本身，具体的执行步骤则交由程序自己决定。SQL是一种可以被快速入手的编程语言， 主要优点就在于即使用户因并不了解数据库内部的实现细节而写出来十分糟糕的查询语句， 只要表达的意思准确清楚，数据库就可以返回结果。因此必须对SQL语句进行优化，在一定程度上将其转化为合理的执行方案。

⑵从技术的角度

通过对用户输入的查询进行优化，实现更优的执行步骤规划 数据库可以实现更快的执行和更少的 I/O 消耗，从而节约资源提高性能。

SQL 查询优化的基本原理

查询优化技术是 SQL 层面的优化，属于局部优化，有别于“数据库调优”式的全局优化。查询优化技术主要包括查询重用技术、查询重写规则技术、查询算法优化技术、并行查询的优化技术、分布式查询优化技术、其他优化技术 6 个方面的技术。“查询重写规则”和“查询算法优化” 是多数提及“数据库查询优化”时所限定的范围，也称为“狭义的数据库查询优化” 。

查询重写规则

查询重写是查询语句的一种等价转换，即对于任何相关模式的任意状态都会产生相同的结果（相同的关系替代两个表达式中相应的关系，所得到的结果是相同的） 。查询重写有两个目标：

​ ❏将查询转换为等价的、效率更高的形式，例如将效率低的谓词转换为效率高的谓词、消除重复条件等。
​ ❏尽量将查询重写为等价、简单且不受表顺序限制的形式，为物理查询优化阶段提供更多的选择，如视图的重写、子查询的合并转换等。

查询重写的依据，是关系代数,SQL 优化的本质是对关系代数的优化。关系代数的等价变换规则对查询重写提供了理论上的支持。查询重写后，查询优化器可能生成多个连接路径，可以从候选者中择优。

对查询优化技术进行分类，可有以下 4 个角度：
❏语法级:查询语言层的优化，基于语法进行优化。
❏代数级 :查询使用形式逻辑进行优化，运用关系代数的原理进行优化。
❏语义级 :根据完整性约束，对查询语句进行语义理解，推知一些可优化的操作。
❏物理级 :物理优化技术，基于代价估算模型，比较得出各种执行方式中代价最小的。

查询重写是基于语法级、代数级、语义级的优化，可以统一归属到逻辑优化的范畴：基于代价估算模型是物理优化，是从连接路径中选择代价最小的路径的过程。

逻辑查询优化

通过找出SQL等价的变换形式让 SQL 执行效率更高效，逻辑优化是基于规则的优化（ Rule-Based Optimization，RBO ），这些规则背后的原理就是关系代数的等价变换，其中典型的规则包括：列剪裁，谓词下推等,对查询进行重写。SQL 的查询重写包括了子查询优化、等价谓词重写、视图重写、条件简化、连接消除和嵌套连接消除等。各种逻辑优化技术依据关系代数和启发式规则进行。

一条 SQL 查询语句结构复杂，包含多种类型的子句，优化操作依赖于表的一些属性信息（如索引和约束等） 。可用于优化的思路包括：

​ ❏子句局部优化。每种类型子句都可能存在优化方式，这是子句局部的优化，如等价谓词重写、WHERE 和 HAVING 条件化简中的大部分情况，都属于这种子句范围内的局部优化。
​ ❏子句间关联优化。子句与子句之间关联的语义存在优化的可能，如外连接消除、连接消除、子查询优化、视图重写等都属于子句间的关联优化，因为它们的优化都需要借助其他子句、表定义或列属性等信息进行。
​ ❏局部与整体的优化。需要协同考虑局部表达式和整体的关系，如 OR 重写并集规则需要考虑 UNION 操作（UNION 是变换后的整体的形式）的花费和 OR 操作（OR 是局部表达式）的花费。
​ ❏形式变化优化。多个子句存在嵌套，可以通过形式的变化完成优化，如嵌套连接消除。
​ ❏语义优化。根据完整性约束、SQL 表达的含义等信息对语句进行语义优化。
​ ❏其他优化。根据一些规则对非 SPJ 做的其他优化、根据硬件环境进行的并行查询优化等。

逻辑优化的目标至少有两个：1) 变换算子表达式，得到开销最小的算子表达式；2) 消除相关子查询。后者可以通过检查AST的节点属性判断，当发现一个嵌套子查询引用外部关系的属性，可以判断为相关子查询。

相关子查询:子查询的执行依赖于外层父查询的一些属性值。子查询因依赖于父查询的参数，当父查询的参数改变时，子查询需要根据新参数值重新执行（查询优化器对相关子查询进行优化有一定意义）

物理查询优化

物理优化是基于代价的优化(Cost-Based Optimizer，CBO)，物理优化主要根据数据读取、表连接方式、表连接顺序、排序等技术对查询进行优化。“查询算法优化”属于物理优化方式，运用了基于代价估算的多表连接算法求解最小花费的技术。将一棵逻辑算子树转换成一棵物理算子树（PhysicalPlan Tree）。这棵物理算子树就是我们说的物理执行计划。物理优化的主要工作是：(1)选择算子实现算法;(2）处理算子之间的连接

查询代价估算基于 CPU 代价和 IO 代价，所以代价模型可以用以下计算公式表示：
总代价 = IO 代价 + CPU 代价

根据表的不同，又分为单表扫描算法，两表连接算法，多表连接算法。每种算法对应的代价估算公式不同。

对 SQL 查询进行优化，既要在原先逻辑算子的基础上进行变换， 又要考虑物理实现的特性，这就是为什么很多查询系统存在逻辑方案和物理方案的区别的原因。 在优化时，往往存在一个从逻辑方案到物理方案进行转变的阶段。

查询优化策略

查询优化目的就是生成最好的查询计划。生成最好的查询计划的策略通常有两个：基于规则的优化器(Rule-Based Optimizer，RBO) 和基于代价的优化器(Cost-Based Optimizer，CBO) ：

• 基于规则的优化器(Rule-Based Optimizer，RBO)

根据优化规则对关系表达式进行转换，这里的转换是说一个关系表达式经过优化规则后会变成另外一个关系表达式，同时原有表达式会被裁剪掉，经过一系列转换后生成最终的执行计划。

RBO中包含了一套有着严格顺序的优化规则，同样一条SQL，无论读取的表中数据是怎么样的，最后生成的执行计划都是一样的。同时，在RBO中SQL写法的不同很有可能影响最终的执行计划，从而影响脚本性能。

• 基于代价的优化器(Cost-Based Optimizer，CBO)

根据优化规则对关系表达式进行转换，这里的转换是说一个关系表达式经过优化规则后会生成另外一个关系表达式，同时原有表达式也会保留，经过一系列转换后会生成多个执行计划，然后CBO会根据统计信息和代价模型(Cost Model)计算每个执行计划的Cost，从中挑选Cost最小的执行计划。由上可知，CBO中有两个依赖：统计信息和代价模型。统计信息的准确与否、代价模型的合理与否都会影响CBO选择最优计划。尽管被称为基于成本的方法，这类算法仍然往往要结合规则进行方案的探索。也就是说， 基于成本的方法其实是通过不断的应用规则进行变换得到新的执行方案， 然后对比方案的成本优劣进行最终选择。

从上述描述可知，CBO是优于RBO的，原因是RBO是一种只认规则，对数据不敏感的呆板的优化器，而在实际过程中，数据往往是有变化的，通过RBO生成的执行计划很有可能不是最优的。

事实上目前各大数据库和大数据计算引擎都倾向于使用CBO

• CBO查询优化主要包含三个步骤：

1）Exploration
根据优化规则进行等价转换，生成等价关系表达式，此时原有关系表达式会被保留。
2）Build Physical Plan
决定各个Operator的具体实现。
3）Find Best Plan
根据统计信息计算各个执行计划的Cost，选择Cost最小的执行计划。

Volcano Optimizer

Volcano Optimizer 是一种基于成本的优化算法，其目的是基于一些假设和工程算法的实现， 在获得成本较优的执行方案的同时，可以通过剪枝和缓存中间结果(动态规划)的方法降低计算消耗。提供了一套sql解析与执行接口，包含sql查询和执行相关任务的执行代码，只需将数据模型插入到sql解析工具Calcite中，就可以得到SQL查询能力。Volcano重点关注的是扩展性和并行性。扩展性的意思是，查询引擎可以比较容易的应用在不同的数据库系统里面，通过简单的修改就可以适配新数据类型，新算法，新算子。并行性的意思是不同的算子可以很方便的并行运行，不同的数据分片可以很方便的被并行处理。

在Volcano模型中，所有的代数运算符(operator)都被看成是一个迭代器，它们都提供一组简单的接口：open()—next()—close()，查询计划树由一个个这样的关系运算符组成，每一次的next()调用，运算符就返回一行(Row)，每一个运算符的next()都有自己的流控逻辑，数据通过运算符自上而下的next()嵌套调用而被动的进行拉取。

1. Volcano Optimizer 使用两阶段的优化，使用 “Logical Algebra” 来表示各种关系代数算子，而使用 “Physical Algebra” 来表示各种关系代数算子的实现算法。Logical Algebra 之间使用 Transformation 来完成变换，而 Logical Algebra 到 Physical Algebra 之间的转换使用基于代价的（ cost-based ）选择。
2. Volcano Optimizer 中的变化都使用 Rule 来描述。例如 Logical Algebra 之间的变化使用 Transformation Rule ；而 Logical Algebra 到 Physical Algebra 之间的转换使用 Implementation Rule。
3. Volcano Optimizer 中各个算子、表达式的结果使用 Property 来表示。Logical Propery 可以从 Logical Algebra 中提取，主要包括算子的 Schema、统计信息等； Physical Property 可以从 Physical Algebra 中提取，表示算子所产生的数的具有的物理属性，比如按照某个 Key 排序、按照某个 Key 分布在集群中等。
4. Volcano Optimizer 的搜索采用自顶向下的动态规划算法（记忆化搜索）

成本最优假设

成本最优假设是理解 Volcano Optimizer 实现的要点之一。这一假设认为， 在最优的方案当中，取局部的结构来看其方案也是最优的。

成本最优假设利用了贪心算法的思想，在计算的过程中， 如果一个方案是由几个局部区域组合而成，那么在计算总成本时， 我们只考虑每个局部目前已知的最优方案和成本即可。

动态规划算法与等价集合

由于引入了成本最优假设，在优化过程中我们就可以对任意子树目前已知的最优方案和最优成本进行缓存。 此后在计算的过程中，如果需要利用这一子树，可以直接使用之前缓存的结果。这里应用了动态规划算法的思想。

要实现这一算法，只需要建立缓存结果到子树双向映射即可。在 Calcite 的实现当中，一颗子树使用其根结点作为代表。 某一棵子树所有可能的变换方案组成的集合被称为等价集合(Equivalent Set)， 等价集合将会维护自身元素当中具有最优成本的方案。

Volcano Optimizer 采取了自顶向下的计算方法，在计算开始， 每棵子树先按照原先的样子计算成本并作为初始结果。在不断应用规则的过程中，如果出现一种新的结构被加入到当前的等价集合中， 且这种等价集合具有更优的成本，这时需要向上冒泡到所有依赖这一子集合的父亲等价集合， 更新集合里每个元素的成本并得到新的最优成本和方案。

值得注意的是，在向上冒泡的过程中需要遍历父亲集合内的每一个方案，这是因为不同方案对于 Input 成本变化的敏感性不同，不能假设之前的最优方案仍然是最优的。

自顶向下的方法尽管解决了一些问题，但是也带来了对关系代数节点操作十分繁琐、 要不断维护父子等价集合的关系等问题，实现相对比较复杂。