1. 摘要
优化器为了产生高效的计划，许多优化器会利用数据的物理排序，这些排序有可能来自索引或者sort算子。排序是一种代价很高的操作。对排序进行优化或者避免全部排序是很重要的事情。
为了满足这个目标，这个文章描述了一些优化技术
- Joins中的sorts下推
- 最小化排序列数量
- 通过断言，索引等进行Sort消除
实现上面这些技术需要一些基础操作，这些基础操作包括从断言，唯一键，函数依赖来获取数据属性。
序言
一个优化器的好坏可以决定一个查询是几分钟或者是几小时执行完。
对于单个复杂的查询有可能会产生多个 interesting orders。interesting orders就是要求某些数据是有序的，这个有序对于
Join, Order By, Group By, or Distinct是有利的。
高效的优化器需要做以下事情：
- 需要探查索引来提供数据有序性满足interesting orders
- 如果没有排序和索引的话，需要提供排序的最佳位置
- 最小化的排序列数量
- 两个以及更多的interesting orders是否可以合并，或者只使用一个即可满足要求
上面这个过程就是排序优化。
初步看，也许基于hash的集合操作使排序优化的作用不是很明显。因为基于hash的操作是不需要输入数据一定是有序的，其实hash操作也是昂贵的。索引对于一些操作是可以提供interesting orders的。最后对于有序的操作和基于hash的操作都会注册到代价优化器进行选择。
这篇论文有两个核心贡献
- 通过使用断言和函数依赖（FD）把 interesting orders简化成符合规范的简单形式。
- 提前排序，允许将Order by这样的排序下推到join或者view中。
2. 相关工作
最经典的是System R 优化器，也是一个对于排序优化的研究。《Access path selection in a relational
database system》这篇论文创造了interesting orders这个词。在System R 中，interesting orders用来阻止包含有序数据局部代价大的关系代数被剪枝掉，这些关系代数有可能全局最优。
《Query processing in dec rdb:Major issues and future challenges》主要论述了出现在 ORDER BY, GROUP BY, DISTINCT 从句中的interesting orders进行合并，没有注重排序优化。
最近的paper是《Pratical predicate placement》包含了断言迁移，推断一个昂贵的断言是否需要下推到join中。《Performing group-by before join》和《Including group-by in query optimization》包含了group by 下推，相似的推断一个group by 是否要下推到join中。之后通过代价评估优化器进行选择最佳的计划。
概述
DB2优化器来源于Starburst优化器，《Grammar-like functional rules for
representing query optimization alternatives.》和《Extensible query processing in starburst》两篇论文描述了Starburst的优化器。
本文专注于传统的基于代价的优化器阶段，在这个阶段，输入的查询被转换为QGM(query graph
model),QGM是高层的，图结构的查询关系代数抽象。构建完QGM之后会通过启发式的规则来转换成更有效的等价关系代数，这些启发式的规则包括
- 断言下推（predicate pushdown）
- 视图合并 (view merging)
-
子查询转换成join （subquery-to-join）
最后这个计划会进行基于代价的优化，QGM会转换成QEP（query execution plan）
Simple QGM and QEP Example
QEP，可以看作是数据流转的图结构，每个节点代表了关系代数操作，每个节点消费一个或者多个输入，之后产出一个输出。
在基于代价优化阶段，DB2自底向上，逐个操作符的构建QEP，对于每一步，不同实现的等价节点会生成，代价最大的节点会被剪枝。这个过程也会尝试构建满足 interesting order属性的节点。
interesting order属性在先前的自顶向下的QGM计划阶段，Joins, Order By, Group By, Distinct关系代数会产生interesting order。
会尽可能的将interesting order下推和组合进order scan中，这样一个sort就可以满足多个interesting order，同时也让优化器可以将sort在join的任意层进行下推。
4 排序优化的基础技术操作
4.1 排序消除
排序消除是排序优化中最基础的操作，排序消除将所需的排序简化成标准形式。消除过程中会用到等价类，把所需的排序列用等价类进行替换，之后再去除多余的列。
假设interesting order为I(x, y),输入的排序为OP = (y)，推断出 I 无法通过 OP 满足，所以会在QEP中添加sort(x)操作符。假设如果关系代数中有一个 filter 条件，比如 x = 10，所以I(x, y)中x是多余的，I(x, y)可以写成I(y)，可以轻松地判断出 OP 可以满足I。
排序消除也需要考虑等价类，例如interesting order 为 I(x, z)， OP =（y, z），如果等价类中有 x = y。那么也可以推断出OP 可以满足I。
排序消除也需要考虑索引key，例如interesting order 为 I(x, y)， OP =（x, z）,如果x是一个索引key，那么interesting order 可以改写为 I(x)， OP 也可以改写为 OP =（x），y和z是多余的，因为只凭x就可唯一确定排序顺序。
索引Keys是FDS（functional dependencies）的一种特例，所以除了keys，FDS经常被用来排序消除。FDS在论文《The role of functional dependencies in query decomposition.》中有详细介绍。
排序消除的算法在图2中用伪代码展示了下
排序消除有可能把所有的排序都简化掉，比如I(x)，filter条件x = 10会产生FDS {} -> {x}，所以I(x)会简化成 I()。
4.2 排序测试
在生成QEP的时候，优化器要判断关系代数的OP(order property)，是否满足I（interesting order ），如果不满足的话需要在QEP中添加sort算子。算法如图3所示
4.3 覆盖排序
DB2优化器会尝试着合并interesting order，这样一个sort算子就可以满足多个interesting order。当两个interesting order I1和I2合并后，就产生了覆盖排序。满足覆盖排序的属性也会满足I1和I2。例如对于I1 = （x）和I2 = （x, y）的覆盖排序是 C = (x, y)。
也不总是能产生覆盖排序的，比如I1 = （y, x）和I2 = （x, y,z)。当尝试生成覆盖排序时，应该先进行排序消除，比如如果有断言x = 10,那么I1 = （y, x）和I2 = （x, y,z)就可以消除为I1 = （y,）和I2 = （y,z)，那么I1和I2就可以合并成C = y,z)，生成覆盖排序的算法如下图
4.4 均匀排序（Homogenize Order）
会尝试将interesting order下推到QGM中的scan，进行前置sort。当下推interesting order I时，会尝试替换一些排序列，这就叫均匀排序。例如如下查询：
select * from a, b where a.x = b.x order by ax, b.y
order by 算子给出了interesting order I =（a.x, b.y）,会尝试下推I到表a和表b,对于表b，可以用等价类 a.x = b.x将interesting order I =（a.x, b.y）均质化为（b.x, b.y）。
interesting order I =（a.x, b.y）不能推到表a，因为b.y只有join完才知道。但是如果a.x是一个索引key，那么通过函数依赖可知
{a.x} -> {b.y}，那么interesting order I =（a.x, b.y）可以简化为I =（a.x），这就可以下推到表a了，进行提前sort。
均质排序的算法见图5
