这是一篇1996年的老paper了，主要讲解了IBM DB2如何针对query当中的有序性进行优化。但对于后续physical property的优化有较为深远的影响，由于DB2的优化器起源于System-R以及其后续演进的starburst，因此延续了system-R中的interesting order和order property的概念。关于system-R的介绍请看之前的文章。
order这种physical property并不只限于order by算子，基于有序的group by/distinct等，都会利用到数据的排序操作，而排序本身就是比较昂贵的计算，因此应该对其做尽可能的优化。
这篇paper系统化的提出了对于有序性进行优化的框架，并描述了一些DB2内部相关的工程实现。
DB2优化器
DB2 optimizer是基于starburst的后继，其思路与system-R一脉相承，优化过程分为了若干个阶段：
- query进入parser解析后，会生成QGM (query graph model)，也就是AST，用来描述逻辑关系运算，之后应有一系列启发式规则做查询变换，生成等价但更为高效的QGM。
- 基于生成的QGM，做cost based优化，生成物理执行plan即QEP(query execution plan)。
右侧是物理plan，可以看到物理算子间的箭头表示data stream，每个data stream会具有若干的属性(property)。
每个output stream的property，是由其对应算子的物理操作特性，和输入stream的property决定的。
在开始做CBO之前，优化器会top-down的遍历QGM，针对不同算子可能的有序性需求（join/group by/distinct/order by），建立算子的interesting order，这个过程称为对QGM的order scan。
在order san的过程中所生成的interesting order，会尽可能下推到下层算子中(sort-ahead)，以尽早满足order属性要求。此外如果一个算子具有多个interesting order，会尝试将他们合并，这样一个排序就可以满足多个order属性的需求。
在优化过程中，DB2采用了类似system-R的bottom-up物理优化，在选择每个算子的物理算法时，也会产生对应的property，每个算子都会产生多种可能的输出属性，并基于等价属性做pruning。在这期间，物理算子的interesting order会被考虑并与下层算子的output order property进行测试（判断其输出是否可以满足interesting order的要求）如果无法满足则加入sorting操作，并相应增大代价。
Order优化算法
本质上，order的优化有3个目标：
- sorting的消除
如果data stream的order property能够满足interesting order，则不需要加sort操作
- 最小化排序的列
同时对order property和interesting order都要做reduce，将其尽量化简为最简形式
- order的下推，尝试提前做掉
为了能够尝试sort-ahead，会在初始阶段，将interesting order尽量尝试下推
相关的操作及对应算法有如下3个
Reduce Order
比如一个order {c1,c2..cn},如果应用过谓词c1=5，则order就可以化简掉c1变成{c2..cn}
如果应用过 c2=b 这样的等值谓词，可以归一化为 {b .. cn}
如果c1是主键(key)，则利用functional dependency(FD)，直接去掉了c2...cn，变为{c1}
以上这些，本质上都是利用FD，无论是key还是const值，都是FD的特殊形式而已。
算法：
给定一个Order的描述，希望化简为统一的最简形式，算法其实很简单
- 根据应用等值谓词，用等价列中的head，替换对应列（所谓等价列就是具有等值关系的列集合，类似于MySQL中MEP的head）
- 对于{c1 ... cn}的规格，从后往前遍历，如果Cj，可以被C1...Cj-1唯一决定(具有FD)，则Cj是冗余的，消掉
Test Order
测试一个算子的output order property(OP)是否满足interesting order需求，算法非常简单
只要interesting order的排序列是output OP 排序列的前缀即可，注意interesting order和output OP都要先做reduce来达成统一形式，且最小化比较的列数。
Cover Order
前面已经提到，在做top-down order scan时，会尝试将2个interesting order合并。
注意仍然要先做reduce来形成统一描述，再考虑是否一个interesting order是另一个的前缀。
Homogenize Order
也就是将前面提到的，将interesting order尽量下推，使sort ahead成为可能。
为了能够下推到比如join的某一个表，目标是将{c1...cn}这样的规格，可以描述为{t1.a, t1.b..}这样的列形式，因此也需要类似reduce的过程，但不一样的是，不一定要用已应用谓词做替换，因为这里只是要求在bottom->up的过程中，逐渐应用谓词后可以满足interesting order，因此可以用到目标算子（提出interesting order的算子）前的所有谓词来尝试reduce。
例如查询
select * from a, b where a.x = b.x order by a.x, b.y;
初始的interesting order I = (a.x, b.y)，如果想把I推导b表的scan上，则需要利用a.x = b.x，转换为 (b.x, b.y)的形式。
注意上述算法仍然要先对I做reduce，如果上例中有FD : a.x是a表的key且join后仍是join result的key，则有 {a.x} -> {b.y}，整个I被reduce为 (a.x)，可以下推到表a，而不是表b。
DB2的order优化框架
有了以上的基础算法后，我们看下DB2的一些实现细节
Order Scan
这个操作发生在实际的优化阶段之前，相当于做一些优化前的预处理。相对于上面的理论，实现中增加了order requirement这个概念，与interesting order不同，order requirement是必须要满足的order属性要求，例如每个算子的输出必须如何有序，算子的输入必须具有什么样的顺序。
例如order by的输出一定要求有序，而group by的输入也要求一定有序（在使用流式group by的前提下）。论文中没有详细说明order requirement和interesting order有何区别，我的理解是，到算子的实际执行处就是requirement，而由于有可能做sort-ahead，但不强制做，因此在远离实际算子时用interesting order描述。
概念上order scan分为4个阶段：
- 决定每个算子的input / output order requirement
- 决定distinct算子的interesting order
- 决定merge join/subquery的interesting order
- top-down遍历QGM，尝试pushdown interesting order，并做homogenize order + cover order
这里有个问题，由于order scan是在优化之前，其实是无法确定到达一个算子时，所应用的谓词以及FD的（这些都是优化过程中产生的物理属性信息）。问题的解决方法是乐观假设，认为一个算子下原始的所有谓词都已应用，如果interesting order无法homogenize到某个特定的input stream，则将I转换为可以最大化homogenize的前缀，然后在优化阶段，检测这些假设是否依然成立（不成立的interesting order消除掉）。
基于property的优化
CBO阶段，采用bottom-up依次处理每个逻辑算子。算子内做各种可能形式的枚举，产生不同的数据流和对应的不同属性，最终基于代价选出最优的，对于每个算子，也有各个候选plan的合并+剪枝操作（参考system-R )。这时，data stream的properties就起到了作用。
剪枝的基本思路就是，对于任意两个subplan1、subplan2，如果1的代价更小，且在属性上更”通用“（用
表示），则2可以被剪枝掉。所以针对每种property，都有一个比较谁更通用的描述。
针对order的优化这个问题，主要涉及如下一些属性
- order property: 描述了output stream的order属性
- predicate property: 积累从算子树的最底层到当前，已应用谓词集合
- key property: data stream中unique keys的集合
- FD property: data stream中functional dependency的集合
针对每种属性，都有相同的几个问题需要考虑
- 属性从哪产生？
- 属性如何跨算子传播，在哪终止？
- 属性间如何比较？
下面依次看下
Order Property
- 只能由ordered index scan / sorting 产生
- 对于一个OP{c1...cn}，如果投影去掉了其中某列cj，则只有{c1...cj-1}这个前缀仍保持有序性。对于join操作，如果是NL/SMJ，则外表的有序性可以传播，如果是HS，有序性都不可以传播（可能有spill操作）
- 两个OP，通过Test Order算法就可以比较。完成reduce后，如果OP1是OP2的前缀，则OP2比OP1更通用
Predicate Property
- 只要一个算子apply了某个谓词，这个谓词就加入到data stream的已应用谓词集合中
- 这个没有终止一说
- 如果一个谓词集合，是另一个的超集，则更大的一方，更具有通用性
Key Property
KP可能包含有多个unique keys，是一个集合的概念，本质上，Key只是FD的一个特例。
- base table自带的基本约束，此外通过group by/distinct之后也可以产生
- 如果有投影去掉了key中的某列，key的唯一性约束不再保证；如果join是n:1的，则左表的唯一性可以传播，反之如果是1:n的，右表的唯一性可以传播，否则唯一性终止；但join之后，可以产生新的唯一key： left_key+right_key 连接起来，形成新的唯一key
- 对于K1, K2，各自进行reduce后，如果K1是K2的子集，则说明用更少的列，就可以唯一决定一行，那么对于KP2中的每个K2，都存在KP1中的K1，能够决定K2，则KP1整体更具有通用性
FD Property
FP是FD的集合，可能会包含下层传递上来的多个FD。
- 当key无法传播过join时，就退化形成FD {c1} -> {c2..cn} （它仍然可以决定属于自己表的部分列）。因此在join时左右两边data stream的key property合并成了一个，同时那些无法传播的Key Property，加入到FD集合中
- 当遇到投影时，对于FD: A -> B，如果减掉A中的列，则FD不再成立，如果减掉B中的列，则FD仍然成立
- 对于FD1 A1 -> B1， FD2 A2 -> B2。如果A1是A2的子集，B1却是B2的超集，则FD1 可以推导出FD2，FD1更具有通用性；如果FP2中每个FD2，都可以被FP1中某个FD1，推导出来，则FP1整体，更具有通用性
一个栗子
paper中给出了一个便于理解的示例
select a.x, a.y, b.y, sum(c.z) from a, b, c where a.x = b.x and b.x = c.x group by a.x, a.y, b.y order by a.x;
这个例子中，order by的interesting order (a.x) 会在早期下推并与group by的interesting order做cover，形成(a.x, a.y, b.y)。然后再进一步下推到join，与merge join的interesting order做homogenize，建立(b.x)。
由b.x这个key形成的FD : {b.x} -> {b.y}，以及join形成的FD : {a.x} -> {b.x}，可以用来reduce group by的interesting order，变为{a.x, a.y}。因此在table a上基于(a.x, a.y)做排序就可以满足所有顺序属性。当table a的数据量较小时，很可能这是一个最优的计划。
总结
本paper提出的思想并不复杂但却十分有用，影响深远。尤其是这种基于functional dependency做reduce的思想，后续又扩展到了除了order外的其他属性中。另外提一句，在PolarDB的并行优化中，也借鉴了一些这种思路，不过由于场景不同，实现有所区别。
