1. 目标
从70年代就有很多关于查询优化器的技术，很难用一篇短文就把这个领域的深度和广度表达出来，因此这里会列出基础技术和这个领域重要工作的采样
2. 概述
关系查询语言提供的高抽象声明的接口来访问存储的数据，慢慢的SQL成了关系查询语言的标准，对于SQL数据库系统，最重要的两个组件是查询优化器和查询执行引擎。
查询执行引擎是执行一组物理算子，算子有一个或者多个输入，一个输出。典型的物理算子有
（外部）排序-(external) sort
顺序扫描-sequential scan
索引扫描-index scan
嵌套连接- nested-loop join
排序连接-sort-merge join
对于一种执行，一个抽象表达是如图1物理算子树，图1中的边代表数据在物理算子间的数据流转。物理算子树和执行计划（简称计划）用两个术语分别表示。
执行引擎负责计划的执行和产出结果。所以查询执行器的能力取决于它支持的算子。查询执行技术可以看另外一篇论文《Query Evaluation Techniques for Large Databases》
查询优化器负责产出供执行引擎使用的计划，优化器很重要，因为对于一个查询，有可能会有很多算子计划树：
对于给定的查询有可能有很多等价的计划，比如
Join(Join(A,B),C)= Join(Join(B,C),A)
对于给定的关系代数，会有很多物理实现，比如join操作就有几种实现算法。
另外，对于这些计划的吞吐量和执行耗时会有很大不同，因此对于优化器选择一个优等的计划很重要。因此，查询优化可以看作是一个艰难的搜索问题，为了解决这个这些问题，我们需要提供
计划的搜索空间。
价估计技术，这些代价用于各个搜索空间的代价计算。
对于执行空间进行搜索的枚举算法。
一个好的优化器应该是
a. 搜索空间包含了代价低的计划，b. 代价评估是准确的，c. 搜索枚举算法是有效的，对于每一个任务都是重要的，这样就是为什么一个好的优化器是一个重大的挑战。
3. 举例：System-R 优化器
System-R的项目，显著提高了关系查询优化器的状态。《Access Path Selection in a Relational Database System》这篇论文里的设计已经被很多商业数据库使用。这里会展示Select-Project-Join(SPJ)查询的一些技术设计。
在System-R中对于SPJ查询，只支持线性Join算子，比如图2里面的a
因为结合律和交换律，以上这些join都是逻辑相等的。对于join可以使用nested loop 或者 sort-merge的实现。对于scan既可以使用索引扫描（聚簇或者非聚簇），也可以使用顺序扫描，最后断言是要尽可能早执行。
代价模型会对搜索空间的部分或者全部计划进行代价估计，也会估计算子产出的记录数，代价模型依赖于以下3点：
关系和索引的统计信息，比如关系的数据页数，索引的数据页数，基数等。
评估 predicates 选择率和 project 输出数据大小的计算公式。
评估执行计划算子的 CPU 和 I/O代价的计算公式，这些公式需要考虑输入数据的统计信息，输入数据的物理实现方法，输入数据流的可用排序顺序
代价模型使用以上的能力来自底向上的风格来计算计划，来获取以下信息：
算子数据输出流的记录数
数据输出流的新创建的排序或者传递的已有排序
评估执行算子的代价（包含累计代价）
System-R的迭代算法有两个重要的设计，动态规划和interesting orders
动态规划的本质上是，最优子结构。就是为了得到包含k个join的SPJ查询，只需要考虑k-1个join的的最优计划是哪些，之后拓展一个join，就能获得k个join的SPJ查询的最优，而不用考虑k-1个join的的最优计划的细节。动态规划是很有效的算法，从O(n!)时间复杂度减少到（ 2 的n-1次方 ）
第二个System-R优化器重要设计是interesting orders，考虑{R1, R2, R3}三个关系的join，join的条件是R1.a, R2.a, R3.a。对于{R1, R2}的join，采用nested loop的代价是x，采用sort-merge的代价是y。x<y。对于{R1, R2, R3}就不会考虑{R1, R2}使用sort-merge的计划。
假设{R1, R2}使用sort-merge join，那么join结果是根据字段a有序。这样的有序会大大减少和R3 join的代价。因此提前把{R1, R2}的sort-merge join裁剪掉会导致次优计划的产生。这个问题产生的本质是{R1, R2} sort-merge join会产生出排序，这个对于后续是有利的，但是nested loop没有这样的顺序。因此System-R会记录对于计划有意义的排序，也叫interesting orders。这个interesting orders在《The Volcano Optimizer Generator: Extensibility and Efficient Search》被称作是物理属性。物理属性不被所有的逻辑计划共有，但是可以影响子树的代价。
尽管System-R设计优雅，这个框架不太容易拓展转换规则来增大搜索空间。所以就有了更利于拓展的架构设计，代价优化，动态规划，interesting orders深深地影响了数据库优化器的发展。
4. 搜索空间
就像第二部提到的，搜索空间的大小取决于
保留相同语义的关系代数转换数量
优化器支持的物理实现算子
关系代数转换并不一定会减少代价，因此也要经过基于代价的处理器获得最优计划。
优化器在优化查询的不同阶段会使用不同的方式去表达查询。最开始会是一个查询的抽象语法树，最后是一个算子计划树，中间使用逻辑的算子树（也叫做查询树）来表达关系代数。
有些系统使用面向代数的方式来表现查询的结构，对于SPJ查询，这样的结构就是一个查询图，节点代表关系，边代表join predicates，如图3。
4.1 算子间交换（Commuting Between Operators）
有很多重要的转换类探索操作符间的可交换性
4.4.1 归纳join顺序
在很多系统中，join算子顺序的会被限制来减少搜索空间。比如在System R中，只支持线性join连接顺序，笛卡尔的操作要延迟到join之后进行。
因为join满足交换律和结合律，所以join不一定是线性 join顺序，也可以如图2b的浓密树的方式，浓密树的方式需要产生中间物化关系。浓密树有可能会降低代价，但是会增加搜索空间。
延迟操作笛卡尔积到join之后，同样会产生性能问题，比如在星型查询中，在维表之间的笛卡尔积可以大幅减少代价。
在一个可拓展的系统中，join优化迭代可以是自适应的。根据查询来限制是否使用浓密树优化，或者是否禁用笛卡尔积。
4.1.2 外部连接和连接
单侧的outer join是不对称的操作符，会保留单边关系的所有元组。对称的outer join会保留关系中的左右元组。
(R LOJ S）会保留R关系中所有元组，LOJ就是left outer join。不像自然连接，对于一系列的 outer joins 和自然连接是不能自由交换的。但是当 （R, S）根据断言自然连接。（S, T）根据断言外部连接，可以进行下面的结合：
Join(R, S LOJ T) = Join (R,S) LOJ T
如果如上的结合律可以重复执行，我们就可以在LOJ之前获自然连接的Join (R,S)，对于Join (R,S)就可以自由进行交换律。
4.1.3 Group-By 和 Join
SPJ查询在传统的执行中，一般会在Group-By之前，有一种优化技术是将Group-By下推到Join之前，这样可以大幅减少join的元组数量，因为Group-By的每个分区只会产出一行元组。对于SELECT DISTINCT语句也是有效的，因为SELECT DISTINCT是一种特殊的Group-By。下推后的Group-By如果有索引，就可以通过索引低代价执行。
4.2 合并多 Block 查询到单 Block
4.2.1 合并视图
设想链接查询，查询中使用了一个或者多个view，对于view可以进行展开来得到单Block。比如查询
query Q = Join(R,V) view V = Join(S,T)，可以展开为
Join(R, Join(S,T)
展开后可以自由进行交换律。
对于views更复杂时，就不能进行简单的展开了，比如views包含SELECT DISTINCT，需要将DISTINCT消除或者上拉，这个步骤需要注意保持数据的重复度（duplicates）。当展开后可以自由交换join 或者 Group-By进行优化。就是图4b 到 图4a。
4.2.2 合并嵌套子查询
考虑如下的子查询
如果按照元组迭代语义来响应这个查询，对于Dept关系中的每个元组，子查询都需要执行一遍。如果子查询没有引用外部的变量，即非相关子查询，那么子查询只需要执行一次就好了。如果子查询使用了外部的变量，就是相关子查询，对于上面的查询，Emp.Emp#就是这个相关变量。对于这种子查询可以解嵌套和打平（flatten）成一个查询，如下
如果子查询有quantifiers（比如 ALL, EXISTS），聚合，或者其他，解嵌套会更复杂一些。最简单的情况就是上面的情况，相同语义的转换是
Somijoin(Emp,Dept,Emp.Dept# = Dept. Dept#) =
Project(Join(Emp,Dept), Emp.*)
其中 Join (Emp, Dept) 的链接条件是 Emp.Dept# =Dopt . Dept# ，Emp.*表明要保留所有的列。
当子查询中有聚合的时候会解嵌套更复杂一些，提升聚合时要保留相同的语义，如下查询
可以转换成如下
4.3 使用类似Semijoin技术来优化Multi-Block查询
示例如下查询
对于上面的查询，对于E和D之间的连接，因为有条件
E.age <30
AND D.budget > lOOk
所以可以先进行连接，减少E.did的数量，这样group by的时候就会减少计算量，可以进行如下改造，比如首先创建部分结果partialresult
之后使用上面的 **partialresult **创建 Filter
之后根据 did Filter 和Emp连接，计算平均sal 进行限制
最后再进行查询
上面用到的技术，可以用在multi-block的包含view的查询中，主要是想避免仕途或者嵌套子查询中重复多余的计算。当然也是进行权衡，就是计算view的代价和这个view能减少的代价，哪个收益更高。
上面的转换优化可以使用Semi-Join，见论文《Cost Based Optimization for Magic: Algebra and Implementatio》，当然也有更简单的做法，就是将断言尽量下推，见论文《Query Optimization by Prcdicatc Move-Aroun》
5. 统计信息和代价估计
对于一个查询，有很多逻辑等价的关系代数表达式，遍历可能使用的关系代数空间和确定消耗最少资源的计划是复杂的问题。资源包括 CPU 时间，I/O代价，内存，通信带宽，也有可能是这些的组合。因此给定查询的算子树，能够准确和高效的评估它的代价是很重要的基础。代价估计应该是准确的，因为这决定了优化器是否准确。代价估计应该是高效的，因为再优化过程中会循环多次调用。
System-R 基础代价估计框架如下：
- 收集已存数据的统计信息摘要
- 给定算子和算子输入流的统计信息摘要，可以计算如下信息
a. 算子输出流的统计信息摘要
b. 算子执行的代价估计
第2步会迭代的探索算子树的任意深度来推导每个算子的代价，当每个算子的代价都估计出来后，就能得到整个算子树的代价。
统计信息属性和计划的代价是不一样的。统计信息属性是逻辑属性，就是对于同一个查询的不同计划是一样的。而代价是物理属性，对于同一个查询的不同计划，代价有可能是不同的。
5.1 数据的统计信息摘要
5.1.1 基础数据的统计信息**
对于每个表，必要的统计信息包含如下几部分：
- 数据流中的元组数量（据此可以估计scan，join等代价和它们的内存消耗）
- 表使用的物理页数
- 列的统计信息（估计此列断言的选择率）
基于列的数据分布信息是通过直方图提供的。直方图有等宽和等高不同的类别，对于等高直方图，会把所有的元组（n个元组）分成k个桶，每个桶的元组数相同，那么每个桶就有n/k个元组。
在论文《Improved Histograms for Selectivity Estimation of Range Predicate》中论述了这种直方图对于数据高度或者低度倾斜是有效的。
除了直方图，min-max值统计信息也很有用，实践中，次最大和次最小的值经常会用到，因为最大值最小值偏差太多。
每列的基数也是很有用的统计信息。
虽然直方图提供了单列的统计信息，但是并没有统计列之间的相关性。为了计算相关性，需要列的联合分布信息。这个分布空间会很大。因此一些系统只是提供了disctinct的值对的信息.
5.1.2 基础数据的统计估计
企业级数据库有很多库和大量的数据，准确和高效的统计信息很重要，所以就需要进行采样，挑战就是如何减少采样带来的估计错误问题。
5.1.3 统计信息的传播计算
在基础数据上进行统计信息是不够的，因为查询会包含很多算子，因此，基于统计信息在算子间进行估计很重要。
最简单的统计估计是selection算子。如果查询一张表上的A列，同时A列上有直方图统计信息，可以用直方图进行统计信息估计。在这个过程中有2点会导致误差。
- 查询A列的值是单个桶的子集，这样会有一定误差
- 列之间是有相关性的，如果对多个列进行断言过滤，就假定列之间是独立的，有的系统会选择多个列中的最大选择率的列统计信息
如果没有统计信息的话，一般按照《Access Path Selection in a Relational Database System. In Readings in Database System》论文进行估算
5.2 代价计算
代价估计阶段会计算算子代价。代价模型估计CPU，I/O，在分布式系统中还会估计通信代价。在大多的系统中会组合使用来比较等价计划。选择一组合适的指标来计算代价需要仔细斟酌。
早期的研究中除了上面这些属性来计算代价，还包含使用缓存的命中率，比如对于nested loop join的算子，如果是index scan的内存缓存可以大幅减少代价。代价估算再查询优化器中一直是很难的部分。
6. 枚举架构
对于给定的查询，枚举算法需要遍历搜索空间来选择一个廉价的执行计划。System-R的设计是只考虑线性join顺序的优化。
对于工程师来说，需要设计一种枚举计划的架构，可以优雅的添加一种转换规则或者物理实现来拓宽搜索空间。也可以优雅地调整代价模型。最近的优化器架构是可拓展的设计，拓展性的同时需要权衡高效。
介绍两种不同的设计类型的优化器，Starburst和Volcano/Cascades，尽管他们有不同的设计，他们的相同点是
- 算子会使用计算代价函数和物理属性
- 使用规则引擎来改变查询表达式或者算子
- 预留拓展点，可以改变枚举框架的行为
6.1 Starburst
使用QGM（Query Graph Model）来表示关系代数
- 查询改写阶段，使用规则把QGM转换成另外等价的QGM，在这个阶段没有代价信息
- 计划优化阶段，使用grammar-like的语言，join枚举器类似于*System-R *的自下向上的枚举框架
6.2 Volcano/Cascades
Volcano 和 Cascades拓展的架构是Exodus的衍生体。在这些系统里，规则被用来拓展搜索空间。
有两种类型的规则，转换规则和实现规则。
为了高效，Volcano 和 Cascades使用自上而下的动态规划（这个过程也叫memoization）。当执行优化任务的时候会通过逻辑和物理属性进行校验任务是否执行过。如果没执行过，有可能执行转换规则，物理实现规则，或者使用enforcer来改变数据流的属性。在优化的每一步使用promise来决定下一步要进行什么操作。
Volcano 和 Cascades框架和Starburst不同的是：
a. 这些系统没有使用两种不同的优化阶段，因为所有的转换都是关系代数和基于代价的
b. 从关系代数到物理的映射发生在单独的步骤
c. 和Starburst的通过链式执行规则不同，Volcano 和 Cascades是代价减少为目标的规则使用
7. 基础拓展
以上是优化器基础的组件。这部分描述一些高级议题。
7.1 分布式和并行数据库
分布式数据库需要引进了节点通信代价，可以通过移动数据和为中间算子选择节点来拓展搜索空间。早期的工作专注于减少通信代价。随着时间推移，分布式数据库架构衍生为副本数据库或者并行数据库来扩容。在副本数据库中保持副本间的数据一致性是一个很重要的议题。
不像分布式数据库，并行数据库的行为就像一个单独的系统，通过并行执行来降低查询响应时间。
并行处理有几个好处，比如数据的物理分布有可能根据分区或者备份至几个节点，允许独立的处理数据。并行处理可以并行处理独立的算子或者流水线（通过把生产者和消费者分布在不同节点上）。坏处就是并行需要在节点之间通信来交换数据
高效地对物理算子进行调度给优化器带来新的挑战。
7.2 用户自定义函数
存储过程（也叫用户定义函数）在关系型数据库广泛使用。提供了一种机制，可以减少客户端和服务器的通信。
随之也带来了问题，比如用户定义函数的代价评估。见《Optimization of Queries with Userdefined Predicate》
解决了用户定义函数的优化问题只是第一步，还有ADTs对于查询怎么进行优化。
7.3 物化视图
物化视图是视图的结果进行物化存储。之后被优化器使用。对于优化器的挑战是给定一部分物化视图，怎么用物化视图来改写查询和查询使用无话改写的高效性。
7.4 其他优化项
排序优化《Fundamental Techniques for Order Optimization》等
8. 结论
优化不仅仅是转换和查询等价，构建优秀的SQL转换，代价估计，枚举框架都很有挑战。核心挑战问题依然在，了解目前现有的优化技术对于未来对优化做贡献也是必要的。
